JDK源码系列(集合)--HashMap源码分析

简介

HashMap采用key/value存储结构,每个key对应唯一的value,查询和修改的速度都很快,能达到O(1)的平均时间复杂度。它是非线程安全的,且不保证元素存储的顺序。

继承体系

image.png
HashMap实现了Cloneable,可以被克隆。

HashMap实现了Serializable,可以被序列化。

HashMap继承自AbstractMap,实现了Map接口,具有Map的所有功能。

存储结构

image.png
在Java中,HashMap的实现采用了(数组 + 链表 + 红黑树)的复杂结构,数组的一个元素又称作桶。

在添加元素时,会根据hash值算出元素在数组中的位置,如果该位置没有元素,则直接把元素放置在此处,如果该位置有元素了,则把元素以链表的形式放置在链表的尾部。

当一个链表的元素个数达到一定的数量(且数组的长度达到一定的长度)后,则把链表转化为红黑树,从而提高效率。

数组的查询效率为O(1),链表的查询效率是O(k),红黑树的查询效率是O(log k),k为桶中的元素个数,所以当元素数量非常多的时候,转化为红黑树能极大地提高效率。

源码解析

属性

image.png
image.png
(1)容量

容量为数组的长度,亦即桶的个数,默认为16,最大为2的30次方,当容量达到64时才可以树化。

(2)装载因子

装载因子用来计算容量达到多少时才进行扩容,默认装载因子为0.75。

(3)树化

树化,当容量达到64且链表的长度达到8时进行树化,当链表的长度小于6时反树化。

Node内部类

Node是一个典型的单链表节点,其中,hash用来存储key计算得来的hash值。
image.png

TreeNode内部类

这是一个神奇的类,它继承自LinkedHashMap中的Entry类,关于LInkedHashMap.Entry这个类我们后面再讲。

TreeNode是一个典型的树型节点,其中,prev是链表中的节点,用于在删除元素的时候可以快速找到它的前置节点。
image.png

HashMap()构造方法

空参构造方法,全部使用默认值。
image.png

HashMap(int initialCapacity)构造方法

调用HashMap(int initialCapacity, float loadFactor)构造方法,传入默认装载因子。
image.png

HashMap(int initialCapacity)构造方法

判断传入的初始容量和装载因子是否合法,并计算扩容门槛,扩容门槛为传入的初始容量往上取最近的2的n次方。
image.png

put(K key, V value)方法

添加元素的入口。
image.png
image.png
image.png
(1)计算key的hash值;

(2)如果桶(数组)数量为0,则初始化桶;

(3)如果key所在的桶没有元素,则直接插入;

(4)如果key所在的桶中的第一个元素的key与待插入的key相同,说明找到了元素,转后续流程(9)处理;

(5)如果第一个元素是树节点,则调用树节点的putTreeVal()寻找元素或插入树节点;

(6)如果不是以上三种情况,则遍历桶对应的链表查找key是否存在于链表中;

(7)如果找到了对应key的元素,则转后续流程(9)处理;

(8)如果没找到对应key的元素,则在链表最后插入一个新节点并判断是否需要树化;

(9)如果找到了对应key的元素,则判断是否需要替换旧值,并直接返回旧值;

(10)如果插入了元素,则数量加1并判断是否需要扩容;

resize()方法

扩容方法。
image.png
image.png
image.png
(1)如果使用是默认构造方法,则第一次插入元素时初始化为默认值,容量为16,扩容门槛为12;

(2)如果使用的是非默认构造方法,则第一次插入元素时初始化容量等于扩容门槛,扩容门槛在构造方法里等于传入容量向上最近的2的n次方;

(3)如果旧容量大于0,则新容量等于旧容量的2倍,但不超过最大容量2的30次方,新扩容门槛为旧扩容门槛的2倍;

(4)创建一个新容量的桶;

(5)搬移元素,原链表分化成两个链表,低位链表存储在原来桶的位置,高位链表搬移到原来桶的位置加旧容量的位置;

TreeNode.putTreeVal(...)方法

插入元素到红黑树中的方法。
image.png
image.png
(1)寻找根节点;

(2)从根节点开始查找;

(3)比较hash值及key值,如果都相同,直接返回,在putVal()方法中决定是否要替换value值;

(4)根据hash值及key值确定在树的左子树还是右子树查找,找到了直接返回;

(5)如果最后没有找到则在树的相应位置插入元素,并做平衡;

treeifyBin()方法

如果插入元素后链表的长度大于等于8则判断是否需要树化。
image.png

TreeNode.treeify()方法

真正树化的方法。
image.png
(1)从链表的第一个元素开始遍历;

(2)将第一个元素作为根节点;

(3)其它元素依次插入到红黑树中,再做平衡;

(4)将根节点移到链表第一元素的位置(因为平衡的时候根节点会改变);

get(Object key)方法

image.png
(1)计算key的hash值;

(2)找到key所在的桶及其第一个元素;

(3)如果第一个元素的key等于待查找的key,直接返回;

(4)如果第一个元素是树节点就按树的方式来查找,否则按链表方式查找;

TreeNode.getTreeNode(int h, Object k)方法

image.png
经典二叉查找树的查找过程,先根据hash值比较,再根据key值比较决定是查左子树还是右子树。

remove(Object key)方法

image.png
image.png
(1)先查找元素所在的节点;

(2)如果找到的节点是树节点,则按树的移除节点处理;

(3)如果找到的节点是桶中的第一个节点,则把第二个节点移到第一的位置;

(4)否则按链表删除节点处理;

(5)修改size,调用移除节点后置处理等;

TreeNode.removeTreeNode(...)方法

image.png
image.png
image.png
(1)TreeNode本身既是链表节点也是红黑树节点;

(2)先删除链表节点;

(3)再删除红黑树节点并做平衡;
总结

(1)HashMap是一种散列表,采用(数组 + 链表 + 红黑树)的存储结构;

(2)HashMap的默认初始容量为16(1<<4),默认装载因子为0.75f,容量总是2的n次方;

(3)HashMap扩容时每次容量变为原来的两倍;

(4)当桶的数量小于64时不会进行树化,只会扩容;

(5)当桶的数量大于64且单个桶中元素的数量大于8时,进行树化;

(6)当单个桶中元素数量小于6时,进行反树化;

(7)HashMap是非线程安全的容器;

(8)HashMap查找添加元素的时间复杂度都为O(1);
带详细注释的源码地址

https://gitee.com/alan-tang-tt/yuan/blob/master/%E6%AD%BB%E7%A3%95%20java%E9%9B%86%E5%90%88%E7%B3%BB%E5%88%97/code/HashMap.java
彩蛋

红黑树知多少?

红黑树具有以下5种性质:

(1)节点是红色或黑色。

(2)根节点是黑色。

(3)每个叶节点(NIL节点,空节点)是黑色的。

(4)每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

(5)从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

红黑树的时间复杂度为O(log n),与树的高度成正比。

红黑树每次的插入、删除操作都需要做平衡,平衡时有可能会改变根节点的位置,颜色转换,左旋,右旋等。

文章来自公众号"彤哥读源码",已得到作者同意转载