HashMap 在并发环境下的死循环问题

因为 HashMap 是非线程安全的，在并发环境下应避免使用，改为 ConcurrentHashMap。

虽然在 jdk8 修复了该问题，但仍然还存在其他并发问题。

其产生的主要原因是扩容时元素的循环引用，在这里简单描述下。

// jdk7 中造成问题的核心代码
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);
                e.next = newTable[i]; // 2
                newTable[i] = e;
                e = next;
            }
        }
    }

1. 例如 HashMap 中有A, B两个元素，并且哈希值都相等，同处于下标为 0 的链表中，顺序为 A -> B -> null。

2. 此时添加元素C将触发扩容操作，但由于有两个线程同时添加了元素，所以将同时触发两次扩容操作。

3. 假设 线程1 先进行了扩容操作，但是由于某种原因，在 代码 1 位置处代码执行完被阻塞了，此时 e = A，next = B。

4. 接着 线程2 顺利的进行了扩容操作，由于重组方式采用的是头插法 (代码 2)，所以新的链表顺序为 B -> A -> null，将B的next设置为A。

5. 当线程2结束后 线程1 也恢复了扩容操作，由于当时现场的e = A，next = B，并且 线程2 将 B 的next 设置为了A，所以相比线程2的扩容将多进行一次 A -> B的操作，这样就造成了 A -> B -> A -> ... 的环路。

6. 当获取一个下标相同但不存在的key时，将发生死循环现象。

用大白话来说，就是你在一堆抽完又放回的扑克牌中取一张不存在的牌。

参考: https://tech.meituan.com/java_hashmap.html