【Java】JDK 7 HashMap 头插法在并发情况下的成环问题

问题描述

JDK 7 的 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;。

最后 e=e0;，这时问题便发生了，e0.next=newTable1[i];，这时的 newTable1[i] 就是 e1，所以此时 e0 指向了 e1，而 e1 还指向 e0，这时就成环了。

总结

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

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

Reference

1. cnblogs：青石路：HashMap 链表插入方式 → 头插为何改成尾插 ?
2. CSDN：乐乐Java路漫漫：jdk1.7下HashMap的头插法问题
3. 腾讯云：名字是乱打的：HashMap的为啥用尾插法?
4. 有了：闫先森：JDK8 的 HashMap 修改头插法为尾插法，为什么？讲一下具体原理。？