hashMap是程序员最常使用的一种数据结构,广泛用于各种需要键值对处理的场景:分组、缓存等等。hashMap的api使用非常简单,但是在使用的时候我们还是会有一些疑惑:
- 为什么阿里的编码规范建议在初始化hashMap时尽量传入预估需要存储的数据的数量(其实基本所有的容器初始化时都建议这么做)
- 为什么jdk1.8之前的hashMap在多线程环境下会死循环。当然有人会说,hashMap不是线程安全的,不能在多线程下使用,偏要用出现死循环了怪谁。但是带着这些问题,能让我们多思考,源码为什么要这么设计
- 在扩容的时候还需要再计算元素的hash位置吗
- 当然还有最基本的为什么key要复写hashCode和equals方法就不再赘述了
为什么我会强调jdk1.8,就是因为jdk1.8里面的hashMap做了一些优化,本文也会从jdk1.7和jdk1.8的区别来分析下hashMap的实现原理。
参数
hashMap采用的是数组+链表+红黑数(jdk1.8增加)的方式来存储数据。
Node<K,V>[] table; int threshold; float loadFactor; int modCount; int size; //map中键值对个数 复制代码
Node[]table就是最重要的存储数据的结构,很明显是一个数组链表,也叫哈希桶。很明显这个数组的大小非常关键,如何在减少hash冲突的同时,减少map所占用的内存,还要减少resize()发生。
table初始大小设定
在初始化时指定map大小,可以有效降低map扩容带来的性能损耗,查看指定map大小的代码,发现会将你指定的大小转换为一个最接近你指定的cap的2的n次方的值。为什么要这样在后面解析put源码时解释。
/**
* Returns a power of two size for the given target capacity.
*/
int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
复制代码
threshold与loadFactor
loadFactor为负载因子,thresHold = table.length * loadFactor,也就是当size > thresHold时候,要对map进行扩容。默认值负载因子取0.75。
确定桶位置
在put和get时都要查找key值应该落在哪个hash桶里面。因为数组长度n都是2的m次方,那么与n-1进行&运算就相当于取哈希值的低m位,也就是哈希值对n取模(%),效率更高。这也就是为什么数组的长度必须为2的整数次方。
n= table.length(); //数组长度 table[h&(n-1)] //获取首节点 复制代码
get put流程
这个相信大家已经非常熟悉
V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; //初始化tab if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; //如果桶位置为空,直接生成node放入即可 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; //桶的链表首节点与key相同,先暂存在变量e中 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //如果桶里面是红黑树结构,采用红黑树方法 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { //没有相同的key,生成node放在链表尾部 p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) //存在相同key的节点,还是暂存在e中 break; p = e; } } if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) //!onlyIfAbsent将旧value值覆盖 e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; //如果size超过了负载阈值,则要扩容 if (++size > threshold) resize(); afterNodeInsertion(evict); return null; } 复制代码
扩容优化
jdk1.7之所以在多线程环境下可能导致死循环,就是在扩容的时候可能会让链表形成环路。原因是会重新计算元素在新的table里面桶的位置,而且还会将链表翻转过来。这里有很多文章详细分析了,如果产生链表环路从而造成死循环的,我也不再赘述。直接看jdk1.8是如何避免了死循环问题的。
Node<K,V>[] resize() { //这儿是计算newCap(变为之前两倍)和threshold的地方,有一些边界值的判断,其实很简单 //但是占用篇幅比较大,忽略掉 threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; if (e.next == null) newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // preserve order Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; //只需要计算一个bit的值就能确定桶的位置 if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; } 复制代码
if ((e.hash & oldCap) == 0),只需要判断一个位是否为0就能确定元素在新桶的位置。
- 记住计算桶位置方法为h&(n-1),n是2的m次方
- 比如扩容之前比如长度为n=16,m=4; n的二进制为10000;n-1的二进制为1111
可以看到只是多了一个高位bit来进行&值,而hash在这个高位bit位要么是0,要么是1;
- 如果hash值在M+1位是0,那么h&(n-1)还是原值
- 如果hash值在m+1为是1,那么h&(n-1)还是就是原值加上2的m次方,也就是原长度n
如下图所示:

而且链表不再翻转,这样也不会产生多线程下死循环了,当然还是不能在多线程下使用,有太多的地方会产生竞争条件了,会造成数据丢失。
原文
https://juejin.im/post/5ef4aaa6f265da22dc3fccaf
本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » JDK1.8 hashMap优化