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