JDK1.7中HashMap的底层是由数组+单向链表这两种数据结构组合而成的,而在JDK1.8中HashMap是由数组+单向链表+红黑树三种数据结构组合而成的。
初始化有固定的大小长度,有顺序的下标(下标从0开始),图1只是示例。
由每个节点组成,每个节点包含一个data(存储数据)和指向下一个节点地址的next,如图二。
(1)每个节点或者是黑色,或者是红色。
(2)根节点是黑色。
(3)每个叶子节点(NIL)是黑色。 注意:这里叶子节点,是指为空(NIL或NULL)的叶子节点!
(4)如果一个节点是红色的,则它的子节点必须是黑色的。
(5)从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
介绍完三种基本结构后,我们再来看看hashmap的数据结构图,如图4。
图5是我截自JDK1.8的HashMap底层源码。
数组、栈 、队列、链表、树、堆 、图、散列表 。
1:数组是计算机编程语言上,对于“Array”的中文称呼,是用于储存多个相同类型数据的集合。
2:栈是限定仅在表尾进行插入和删除操作的线性表,栈者,存储货物或供旅客住宿的地方,可引申为仓库、中转站,引入到计算机领域里,就是指数据暂时存储的地方,所以才有进栈、出栈的说法。
3:一种特殊的线性表,它只允许在表的前端进行删除操作,而在表的后端进行插入操作。
4:链表,一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
5:哈希表,是根据关键码值而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。