问题描述

JDK7的 HashMap 解决冲突用的是链表,在插入链表的时候用的是头插法,每次在链表的头部插入新元素。resize() 的时候用的依然是头插,头插的话,如果某个下标中的链表在新的 table 中依然索引到同一个下标中,那么原链表的顺序会反转。因为链表是顺序访问的,那么每次访问一个节点,会把当前节点插到新 table 链表的头部,这样原链表的最后一个元素在 resize() 后,就变成新链表的头部了(如果它们索引到新 table 的同一个下标中)。这在并发的情况下可能产生环。

详细解释

resize()的代码

 for (Entry<K,V> e : table) { // e 是每一个链表的头节点
            while(null != e) {
                Entry<K,V> next = e.next; // 当前节点 e 的下一个节点 next
                int i = indexFor(e.hash, newCapacity); // i 是 e 在新 table 中的索引
                e.next = newTable[i]; // 头插法,当前节点的 next 是当前新 table 对应索引的头节点
                newTable[i] = e; // 更新 新 table 对应索引的头节点
                e = next; // 旧 table 当前链表的下一个节点
            }
        }

​ map 当前处于扩容边缘,再添加一个 Entry 就得扩容。现在有两个线程,Thread1 要 put,Thread2 也要 put,那么如果没有锁,就可能会出现环。

Thread1 先扩容,执行到 e=e0;next=e1; 的时候,Thread2 开始执行扩容,Thread2 完成扩容之后,Thread1 继续执行,即下图中的前两格。那么当前出现了一个现象,e1 的 next 变成 e0 了,e0 的 next 变成 null 了。

​ 然后 Thread1 继续执行,e0 的 next 变成 null,newTable1[i]=e0; 并且此时 e1 指向 e0。next 没有变,还是最开始指向的 next=e1;

继续下一次循环,这时 e=e1; 重点 :next=e0;,继续执行,可以得到 e1 指向 e0,newTable1[i]=e1; 的结果,如果不继续循环这就是对的,但是 此时 next=e0;。
JDK 7 HashMap 并发情况下的死锁问题-LMLPHP

总结

会出现环就是因为头插在扩容的时候会反转原链表,使得有出现环的可能。换成尾插,原来是什么顺序,扩容之后还是什么顺序,就不会出现一个线程抢先之后 e1 指向 e0 的情况,依旧时 e0 指向 e1,就不会出现环。

即使 JDK8 改成 尾插,但是并发情况下,同时修改同一个 key 的值 或者 同时删除+修改同一个 key 等都会出现其他并发问题,所以并发情况下不要用 HashMap,建议用带锁的 ConcurrentHashMap。

03-09 18:22