JDK1.8中的HashMap底层数据结构的图解

HashMap的基本介绍：

hashmap是java开发最常用的一种数据模型，hashmap属于map接口的一种实现。以key-value的这种形式存储数据，其中key是不允许重复的但是允许为空，value是可以重复或为空的。其中key只能使用基本数据类型（int，double...）的封装类（interger，double。。。。）。

JAVA中初始化一个HashMap：

HashMap<Integer,String> map = new HashMap<Integer,String>()；

Map<Integer,String> map = new HashMap<Integer,String>()；

HashMap的底层知识的介绍：

JDK1.7中HashMap的底层是由数组+单向链表这两种数据结构组合而成的，而在JDK1.8中HashMap是由数组+单向链表+红黑树三种数据结构组合而成的。

数组结构（图1）：

初始化有固定的大小长度，有顺序的下标（下标从0开始），图1只是示例。

图1

单向链表结构（图2）：

由每个节点组成，每个节点包含一个data（存储数据）和指向下一个节点地址的next，如图二。

图2

红黑树结构（图3）：

（1）每个节点或者是黑色，或者是红色。

（2）根节点是黑色。

（3）每个叶子节点（NIL）是黑色。 注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！

（4）如果一个节点是红色的，则它的子节点必须是黑色的。

（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

图3

介绍完三种基本结构后，我们再来看看hashmap的数据结构图，如图4。

图4

图解：HashMap的本质就是一个复合结构，它其实就是有一个一个Node节点组成的一个Node数组。在初始化一个HashMap的时候，会规定这个数组容量为16（2的4次方），下标从0-15；数组的最大容量（扩容后）为2的30次方，而数组的扩容因素为0.75，即当每次数组实际用到的容量达到当前数组最大容量的0.75时，这个数组就会整体扩容一倍（乘以2）；而每个Node算出数组下标是根据该Node的hashcode（哈希值）除以16取余后的数字再进行一系类的计算得出，但是会出现计算出来的数值相同（即数组下标相同的Node节点出现），这时候就出现了所谓的哈希冲突。为了解决这一问题，引入了单向链表的操作，当算出数组下标相同的Node节点出现，就会以单向链表的数据结构形式，纵向的向下排，当向下排的Node节点达到8个节点。为了解决性能问题，（接下来是JDK1.8的内容）这时候引入了红黑树这个数据结构，程序会将之前的单向链表通过算法将其变成红黑树，而当这个红黑树里面的叶子节点数小于6的时候，程序又会将其由红黑树转换成单向链表结构。

图5

图5是我截自JDK1.8的HashMap底层源码。

图中：

DEFAULT_INITIAL_CAPACITY        为HashMap初始化的数组容量（长度）-16

MAXIMUM_CAPACITY       为HashMap的数组最大容量       ------  2的30次方

DEFAULT_LOAD_FACTOR    为HashMap扩容因子

TREEIFY_THRESHOLD    为链表的阀值（超过这个值链表转化成红黑树结构）

UNTREEIFY_THRESHOLD  为红黑树的阀值（红黑树叶子节点到6时，就会转化成链表结构）