最近几天,一直在学习HashMap的底层实现,发现关于HashMap实现的博客文章还是很多的,对比了一些,都没有一个很全面的文章来做总结,本篇文章也断断续续结合源码写了一下,如果有理解不当之处,欢迎指正!
01、摘要
在集合系列的第一章,咱们了解到,Map的实现类有HashMap、LinkedHashMap、TreeMap、IdentityHashMap、WeakHashMap、Hashtable、Properties等等。
关于HashMap,一直都是一个非常热门的话题,只要你出去面试,我保证一定少不了它!
本文主要结合JDK1.7和JDK1.8的区别,就HashMap的数据结构和实现功能,进行深入探讨,废话也不多说了,直奔主题!
02、简介
在程序编程的时候,HashMap是一个使用非常频繁的容器类,它允许键值都放入null元素。除该类方法未实现同步外,其余跟Hashtable大致相同,但跟TreeMap不同,该容器不保证元素顺序,根据需要该容器可能会对元素重新哈希,元素的顺序也会被重新打散,因此不同时间迭代同一个HashMap的顺序可能会不同。
HashMap容器,实质还是一个哈希数组结构,但是在元素插入的时候,存在发生hash冲突的可能性;
对于发生Hash冲突的情况,冲突有两种实现方式,一种开放地址方式(当发生hash冲突时,就继续以此继续寻找,直到找到没有冲突的hash值),另一种是拉链方式(将冲突的元素放入链表)。Java HashMap采用的就是第二种方式,拉链法。
在jdk1.7中,HashMap主要是由数组+链表组成,当发生hash冲突的时候,就将冲突的元素放入链表中。
从jdk1.8开始,HashMap主要是由数组+链表+红黑树实现的,相比jdk1.7而言,多了一个红黑树实现。当链表长度超过8的时候,就将链表变成红黑树,如图所示。
关于红黑树的实现,因为篇幅太长,在《集合系列》文章中红黑树设计,也有所介绍,这里就不在详细介绍了。
03、源码解析
直接打开HashMap的源码分析,可以看到,主要有5个关键参数:
-
threshold:表示容器所能容纳的key-value对极限。
-
loadFactor:负载因子。
-
modCount:记录修改次数。
-
size:表示实际存在的键值对数量。
-
table:一个哈希桶数组,键值对就存放在里面。
1 |
|
接着来看看Node
这个类,Node
是HashMap
的一个内部类,实现了Map.Entry
接口,本质是就是一个映射(键值对)
1 |
|
在HashMap的数据结构中,有两个参数可以影响HashMap的性能:初始容量(inital capacity)和负载因子(load factor)。
初始容量(inital capacity)是指table的初始长度length(默认值是16);
负载因子(load factor)用指自动扩容的临界值(默认值是0.75);
threshold
是HashMap
所能容纳的最大数据量的Node
(键值对)个数,计算公式threshold = capacity * Load factor
。当entry的数量超过capacity*load_factor
时,容器将自动扩容并重新哈希,扩容后的HashMap
容量是之前容量的两倍,所以数组的长度总是2的n次方。
初始容量和负载因子也可以修改,具体实现方式,可以在对象初始化的时候,指定参数,比如:
1 |
|
但是,默认的负载因子0.75是对空间和时间效率的一个平衡选择,建议大家不要修改,除非在时间和空间比较特殊的情况下,如果内存空间很多而又对时间效率要求很高,可以降低负载因子Load factor的值;相反,如果内存空间紧张而对时间效率要求不高,可以增加负载因子loadFactor的值,这个值可以大于1。 同时,对于插入元素较多的场景,可以将初始容量设大,减少重新哈希的次数。
HashMap的内部功能实现有很多,本文主要从以下几点,进行逐步分析。
-
通过K获取数组下标;
-
put方法的详细执行;
-
resize扩容过程;
-
get方法获取参数值;
-
remove删除元素;
3.1、通过K获取数组下标
不管增加、删除还是查找键值对,定位到数组的位置都是很关键的第一步,打开hashMap的任意一个增加、删除、查找方法,从源码可以看出,通过key
获取数组下标,主要做了3步操作,其中length
指的是容器数组的大小。
源码部分:
1 |
|
3.2、put方法的详细执行
put(K key, V value)方法是将指定的key, value对添加到map里。该方法首先会对map做一次查找,看是否包含该K,如果已经包含则直接返回;如果没有找到,则将元素插入容器。具体插入过程如下:
具体执行步骤
-
1、判断键值对数组table[i]是否为空或为null,否则执行resize()进行扩容;
-
2、根据键值key计算hash值得到插入的数组索引i,如果table[i]==null,直接新建节点添加;
-
3、当table[i]不为空,判断table[i]的首个元素是否和传入的key一样,如果相同直接覆盖value;
-
4、判断table[i] 是否为treeNode,即table[i] 是否是红黑树,如果是红黑树,则直接在树中插入键值对;
-
5、遍历table[i],判断链表长度是否大于8,大于8的话把链表转换为红黑树,在红黑树中执行插入操作,否则进行链表的插入操作;遍历过程中若发现key已经存在直接覆盖value即可;
-
6、插入成功后,判断实际存在的键值对数量size是否超多了最大容量threshold,如果超过,进行扩容操作;
put方法源码部分
1 |
|
插入元素方法
1 |
|
其中,与jdk1.7有区别的地方,第4步新增了红黑树插入方法,源码部分:
1 |
|
3.3、resize扩容过程
在说jdk1.8的HashMap动态扩容之前,我们先来了解一下jdk1.7的HashMap扩容实现,因为jdk1.8代码实现比Java1.7复杂了不止一倍,主要是Java1.8引入了红黑树设计,但是实现思想大同小异!
3.3.1、jdk1.7的扩容实现
源码部分
1 |
|
transfer复制数组方法,源码部分:
1 |
|
jdk1.7扩容总结: newTable[i]的引用赋给了e.next,也就是使用了单链表的头插入方式,同一位置上新元素总会被放在链表的头部位置;这样先放在一个索引上的元素终会被放到Entry链的尾部(如果发生了hash冲突的话),这一点和Jdk1.8有区别。在旧数组中同一条Entry链上的元素,通过重新计算索引位置后,有可能被放到了新数组的不同位置上。
3.3.2、jdk1.8的扩容实现
源码如下
1 |
|
1.7与1.8处理逻辑大同小异,区别主要还是在树节点的分裂((TreeNode<K,V>)e).split()
这个方法上
1 |
|
untreeify
方法,将树转变为单向链表
1 |
|
treeify
方法,将链表转换为红黑树,会根据红黑树特性进行颜色转换、左旋、右旋等
1 |
|
jdk1.8在进行重新扩容之后,会重新计算hash值,因为n变为2倍,假设初始 tableSize = 4 要扩容到 8 来说就是 0100 到 1000 的变化(左移一位就是 2 倍),在扩容中只用判断原来的 hash 值与左移动的一位(newtable 的值)按位与操作是 0 或 1 就行,0 的话索引就不变,1 的话索引变成原索引 + oldCap;
其实现如下流程图所示:
可以看见,因为 hash 值本来就是随机性的,所以 hash 按位与上 newTable 得到的 0(扩容前的索引位置)和 1(扩容前索引位置加上扩容前数组长度的数值索引处)就是随机的,所以扩容的过程就能把之前哈希冲突的元素再随机的分布到不同的索引去,这算是 JDK1.8 的一个优化点。
此外,JDK1.7中rehash的时候,旧链表迁移新链表的时候,如果在新表的数组索引位置相同,则链表元素会倒置,但是从上图可以看出,JDK1.8不会倒置。
同时,由于 JDK1.7 中发生哈希冲突时仅仅采用了链表结构存储冲突元素,所以扩容时仅仅是重新计算其存储位置而已。而 JDK1.8 中为了性能在同一索引处发生哈希冲突到一定程度时,链表结构会转换为红黑数结构存储冲突元素,故在扩容时如果当前索引中元素结构是红黑树且元素个数小于链表还原阈值时就会把树形结构缩小或直接还原为链表结构(其实现就是上面代码片段中的 split() 方法)。
3.4、get方法获取参数值
get(Object key)方法根据指定的key值返回对应的value,getNode(hash(key), key))
得到相应的Node对象e,然后返回e.value。因此getNode()是算法的核心。
get方法源码部分:
1 |
|
通过hash值和key获取节点Node方法,源码部分:
1 |
|
在红黑树中找到指定k的TreeNode,源码部分:
1 |
|
get方法,首先通过hash()函数得到对应数组下标,然后依次判断。
-
1、判断第一个元素与key是否匹配,如果匹配就返回参数值;
-
2、判断链表是否红黑树,如果是红黑树,就进入红黑树方法获取参数值;
-
3、如果不是红黑树结构,直接循环判断,直到获取参数为止;
3.5、remove删除元素
remove(Object key)的作用是删除key值对应的Node,该方法的具体逻辑是在removeNode(hash(key), key, null, false, true)
里实现的。
remove方法,源码部分:
1 |
|
通过key移除Node节点方法,源码部分:
1 |
|
removeTreeNode移除红黑树节点方法,源码部分:
1 |
|
jdk1.8的删除逻辑实现比较复杂,相比jdk1.7而言,多了红黑树节点删除和调整:
-
1、默认判断链表第一个元素是否是要删除的元素;
-
2、如果第一个不是,就继续判断当前冲突链表是否是红黑树,如果是,就进入红黑树里面去找;
-
3、如果当前冲突链表不是红黑树,就直接在链表中循环判断,直到找到为止;
-
4、将找到的节点,删除掉,如果是红黑树结构,会进行颜色转换、左旋、右旋调整,直到满足红黑树特性为止;
04、总结
1、如果key是一个对象,记得在对象实体类里面,要重写equals和hashCode方法,不然在查询的时候,无法通过对象key来获取参数值!
2、相比JDK1.7,JDK1.8引入红黑树设计,当链表长度大于8的时候,链表会转化为红黑树结构,发生冲突的链表如果很长,红黑树的实现很大程度优化了HashMap的性能,使查询效率比JDK1.7要快一倍!
3、对于大数组的情况,可以提前给Map初始化一个容量,避免在插入的时候,频繁的扩容,因为扩容本身就比较消耗性能!
05、参考
1、JDK1.7&JDK1.8 源码