简单总结jdk1.7HashMap扩容死循环和jdk1.8优化

• • jdk1.7 HashMap死循环原因
  • • 扩容步骤
    • 死循环
    • 总结
  • jdk1.8的改进
  • • jdk1.8仍然存在的问题

网上很多关于jdk1.7HashMap扩容死循环的博客, 但是很多都是贴了大量的代码和图, 这里只进行简单概括总结, 详细的还是需要自己看源码.

首先贴代码 (这个必要的还是要贴)

    void resize(int newCapacity) {
		....
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        table = newTable;
		...
    }
    
    void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry e : table) {
            while(null != e) {
                Entry 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 next = e.next;
得到 e = a, next = b

此时线程1运行, 并且完成了扩容, 那么新链表newTable[7]上就是 c → b → a

线程2继续执行, 它也会开辟一个新扩容数组. 接着上面的步骤

3. 把a的next指向 newTable[7] 的链表头部, 这里是null, a → null
4. 把 newTable[7] 赋值为a
5. 将next, 即b作为下次循环

现在情况如图

但是到了下个循环的时候,
e是b, next却取到了由线程1扩容排列后的新顺序, 拿到了a, 继续执行

3. b的next指向newTable[7] 的链表头部, 即a. 变成 b → a → null
4. newTable[7] 的链表头部变成b
5. a投入下次循环

下次循环, e是a, next是null

3. 把a的next指向 newTable[7] 的链表头部, 这里是b, a → b → a 就是这一步形成了闭环
4. 把 newTable[7] 赋值为a
5. 将next, 即null作为下次循环, 但是null作为条件判断不在继续循环

最后结果是这样

形成死循环的原因:

1. jdk1.7是头插法, 即遍历旧链表, 插入新链表的头部, 导致顺序颠倒
2. 多线程下, 其中一个线程颠倒了顺序, 另一个线程不知情, 循环中保持了原顺序的2个节点, 在头插法的时候就会多出一条闭环的指向
3. 在get查询的时候, 遍历链表就出现了死循环

代码

 1 final Node[] resize() {
 2    .....省略
31     @SuppressWarnings({"rawtypes"，"unchecked"})
32         Node[] newTab = (Node[])new Node[newCap];
33     table = newTab;
34     if (oldTab != null) {
35         // 把旧数组的每个下标遍历,迁移
36         for (int j = 0; j < oldCap; ++j) {
37             Node 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)e).split(this, newTab, j, oldCap);
44                 else { // 如果是链表
45                     Node loHead = null, loTail = null;
46                     Node hiHead = null, hiTail = null;
47                     Node 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的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 root() {
            for (TreeNode r = this, p;;) {
                if ((p = r.parent) == null)
                    return r;
                r = p;   //1816行
            }
        }