本文主要是介绍HashMap多线程扩容导致死循环解析(JDK1.7),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
前言
前一篇 HashMap底层结构与实现原理 遗留了一个问题:JDK1.7中的HashMap在多线程情况下扩容可能会导致死循环。本篇就这个问题进行讲解。
扩容死循环
前一篇深入的讲解了HashMap1.7扩容的过程,这里回顾一下在扩容过程中,单链表的表现,相关的代码如下
void transfer(Entry[] newTable, boolean rehash) {int newCapacity = newTable.length;// 外层循环遍历数组槽(slot)for (Entry<K,V> e : table) {// 内层循环遍历单链表while(null != e) {// 记录当前节点的next节点Entry<K,V> next = e.next;if (rehash) {e.hash = null == e.key ? 0 : hash(e.key);}// 找到元素在新数组中的槽(slot)int i = indexFor(e.hash, newCapacity);// 用头插法将元素插入新的数组e.next = newTable[i];newTable[i] = e;// 遍历下一个节点e = next;}}
}
在单线程情况下,假设A、B、C三个节点处在一个链表上,扩容后依然处在一个链表上,代码执行过程如下:
需要注意的几点是
- 单链表在转移的过程中会被反转
table
是线程共享的,而newTable
是不共享的- 执行
table = newTable
后,其他线程就可以看到转移线程转移后的结果了
理解了单线程下链表在扩容时的行为,再来看多线程的情况就比较容易了
此处感谢评论区
@伤神v
同学的指点,以下多线程扩容图是修正后的图。
还是关注transfer
方法这段代码
void transfer(Entry[] newTable, boolean rehash) {int newCapacity = newTable.length;for (Entry<K,V> e : table) {while(null != e) {Entry<K,V> next = e.next;if (rehash) {e.hash = null == e.key ? 0 : hash(e.key);}int i = indexFor(e.hash, newCapacity);e.next = newTable[i];newTable[i] = e; // *线程1在这行暂停(尚未执行)e = next;}}
}
- 线程1执行
newTable[i] = e
时暂停(未执行) - 线程2直接扩容完成
- 线程1继续执行,此时线程1可以看到线程2扩容后的结果
图中已经画出了每一行代码执行后,HashMap
的结构图,仔细观察图中的结构变化,就能理解为什么会死循环。
由此,完完整整的解释了为什么多线程情况下,JDK1.7版本的HashMap
扩容有可能出现死循环。
JDK1.8改进
JDK1.8中扩容的方法是resize
,对应的代码是(HashMap中第715行至第742行):
// 低位链表头节点,尾结点
// 低位链表就是扩容前后,所处的槽(slot)的下标不变
// 如果扩容前处于table[n],扩容后还是处于table[n]
Node<K,V> loHead = null, loTail = null;
// 高位链表头节点,尾结点
// 高位链表就是扩容后所处槽(slot)的下标 = 原来的下标 + 新容量的一半
// 如果扩容前处于table[n],扩容后处于table[n + newCapacity / 2]
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {next = e.next;if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.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;
}
注意第12行的代码(e.hash & oldCap) == 0
就可以判断,当前槽上的链表在扩容前和扩容后,所在的槽(slot)下标是否一致。举个例子:
假如一个key的hash值为1001 1100
,转换成十进制就是156,数组长度为1000
,转换成十进制就是8。
1001 1100
& 0000 1000
--------------0000 1000
也就是(e.hash & oldCap) != 0
,很容易计算出,扩容前这个key的下标是4(156 % 8 = 4
),扩容后下标是12(156 % 16 = 12
)即:12 = 4 + 16 / 2
,满足n = n + newCapacity / 2
,由此可以看出这种计算方式非常巧妙。至于第12行之后的代码就是基本的单链表操作了,只是一个单链表同时具有头指针和尾指针,等到链表被分成高位链表和低位链表后,再一次性转移到新的table
。这样就完成了单链表在扩容过程中的转移,使用两条链表的好处就是转移前后的链表不会倒置,更不会因为多线程扩容而导致死循环。
总结
本篇主要通过图解的方式,解释了为什么JDK1.7中的HashMap在多线程情况下扩容可能死循环,也解释了JDK1.8如何解决这个问题。不得不说,画图是个很好的分析方式,根据代码,一步一步把结构图画出来,比对着代码瞎琢磨效果好多了。
以上就是本篇文章的全部内容。
这篇关于HashMap多线程扩容导致死循环解析(JDK1.7)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!