简单总结jdk1.7HashMap扩容死循环和jdk1.8优化
网上很多关于jdk1.7HashMap扩容死循环的博客, 但是很多都是贴了大量的代码和图, 这里只进行简单概括总结, 详细的还是需要自己看源码.
jdk1.7 HashMap死循环原因
首先贴代码 (这个必要的还是要贴)
void resize(int newCapacity) {
....
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
...
}
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; //1. 先获取当前节点的下个节点
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);//2. 获取扩容后新数组的下标
e.next = newTable[i]; //3. 把当前节点的下个节点指向新坐标的链表头部
newTable[i] = e; //4. 把新坐标,即链表头部换成当前节点
e = next; //5. 把下个节点投入循环
}
}
}
我们知道HashMap是数组+链表, 假设这里有个HashMap, 哈希冲突都坐落在下标3的位置形成了a-b-c的链表
扩容步骤
简单再结合看上面的transfer方法, 可以看出做了5步:
1. 遍历链表, 这里e就是a, next就是b
2. 获取扩容后的新下标, 假设[3]上面的abc的新下标是7,newTable[7]
3. 把a的next指向 newTable[7] 的链表头部, 这里是null, a → null
4. 把 newTable[7] 赋值为a
5. 将next, 即b作为下次循环
第二次循环:
1. e就是b, next就是c
2. 新下标, newTable[7]
3. b的next指向newTable[7] 的链表头部, 即a. 变成 b → a → null
4. newTable[7] 的链表头部变成b
5. c投入下次循环
也就是虽然遍历的时候是从链表头往后面, 但是每次放的位置都放在新链表的头部, 最后颠倒
最后变成 c → b → a.
死循环
知道了扩容是链表颠倒后, 这里假设有两个线程同时触发了扩容操作.
线程2运行到第1步, 即Entry<K,V> next = e.next;
得到 e = a, next = b
此时线程1运行, 并且完成了扩容, 那么新链表newTable[7]上就是 c → b → a
线程2继续执行, 它也会开辟一个新扩容数组. 接着上面的步骤
- 把a的next指向 newTable[7] 的链表头部, 这里是null, a → null
- 把 newTable[7] 赋值为a
- 将next, 即b作为下次循环
现在情况如图
但是到了下个循环的时候,
e是b, next却取到了由线程1扩容排列后的新顺序, 拿到了a, 继续执行
- b的next指向newTable[7] 的链表头部, 即a. 变成 b → a → null
- newTable[7] 的链表头部变成b
- a投入下次循环
下次循环, e是a, next是null
- 把a的next指向 newTable[7] 的链表头部, 这里是b, a → b → a
就是这一步形成了闭环- 把 newTable[7] 赋值为a
- 将next, 即null作为下次循环, 但是null作为条件判断不在继续循环
最后结果是这样
总结
形成死循环的原因:
- jdk1.7是头插法, 即遍历旧链表, 插入新链表的头部, 导致
顺序颠倒 - 多线程下, 其中一个线程颠倒了顺序, 另一个线程不知情, 循环中保持了原顺序的2个节点, 在头插法的时候就会多出一条闭环的指向
- 在get查询的时候, 遍历链表就出现了死循环
jdk1.8的改进
代码
1 final Node<K,V>[] resize() {
2 .....省略
31 @SuppressWarnings({"rawtypes"，"unchecked"})
32 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
33 table = newTab;
34 if (oldTab != null) {
35 // 把旧数组的每个下标遍历,迁移
36 for (int j = 0; j < oldCap; ++j) {
37 Node<K,V> e;
38 if ((e = oldTab[j]) != null) {
39 oldTab[j] = null;
40 if (e.next == null) //如果此位置就只有一个元素, 直接放到新坐标
41 newTab[e.hash & (newCap - 1)] = e;
42 else if (e instanceof TreeNode) //如果是红黑树
43 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
44 else { // 如果是链表
45 Node<K,V> loHead = null, loTail = null;
46 Node<K,V> hiHead = null, hiTail = null;
47 Node<K,V> next;
48 do {
49 next = e.next;
50 // 这里是判断最高位是否为0,如果是0,表示扩容未对其造成影响(因为length-1 的二进制全是1, 扩容2倍只变化了最高位多了个1 )
51 if ((e.hash & oldCap) == 0) {
52 if (loTail == null)
53 loHead = e;
54 else
55 loTail.next = e;
56 loTail = e;
57 }
58 // 这里表示收到影响, 新下标索引=原索引+oldCap
59 else {
60 if (hiTail == null)
61 hiHead = e;
62 else
//关键 从尾部添加元素
63 hiTail.next = e;
64 hiTail = e;
65 }
66 } while ((e = next) != null);
67 // 原索引放到bucket里
68 if (loTail != null) {
69 loTail.next = null;
70 newTab[j] = loHead;
71 }
72 // 原索引+oldCap放到bucket里
73 if (hiTail != null) {
74 hiTail.next = null;
75 newTab[j + oldCap] = hiHead;
76 }
77 }
78 }
79 }
80 }
81 return newTab;
82 }
从63行看出, jdk1.8是从尾部添加元素的. 也就是新下标的链表和旧数组下标的链表顺序是一致的. 所以不会因为顺序颠倒导致一个闭环的指向
jdk1.8仍然存在的问题
jdk1.8的HashMap仍然是线程不安全的, 扩容的话虽然从尾部添加元素, 但是两个线程同时操作的话, 可能会导致其中一个线程的扩容新链表被覆盖.
其次jdk1.8也存在死循环问题.
- jdk8在PutTreeValue时可能死循环 死循环在hashMap的1816行或2229行， java version “1.8.0_111”
- jstack发现可能卡在 at java.util.HashMap$TreeNode.balanceInsertion(HashMap.java:2229)
- 也有可能卡在 at java.util.HashMap$TreeNode.root(HashMap.java:1816)
原因是因为多线程操作同一个对象, 属性被修改的原因
比如下面这里, 如果两个 node 的parent是彼此, 就形成了死循环
实践证明，JDK8中HashMap依然会死循环
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p; //1816行
}
}