JDK 7 HashMap 并发情况下的死锁问题

链表的头插法，了解一下这个博客

• 问题描述
• 详细解释

问题描述

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

总结

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

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