前言

HashMap 存在并发死循环的问题，在1.7版本之前是因为多线程并发调用 put 方法容易产生环状链表，之后如果再调用get方法，如果刚好命中环状链表所在的槽位，则会用导致死循环，使得 CPU 占用率飙升.
在JDK 1.8 之后，这一问题得到了修复，但是仍旧在某些特殊的情况下会发生另外一种死循环。
这里就这两种情况逐一进行分析.

链表的插入方式

在分析之前，我们先了解一下链表的两种插入方式：

• 头插法
• 尾插法

头插法

头插法顾名思义就是插入链表节点时，从链表的头部插入：

代码的实现如下：

Node node = null;

for (int i = 1; i <= 10; i++) {
    Node newNode = new Node();
    newNode.data = i;
    newNode.next = node;
    node = newNode;
}

我们发现链表的插入顺序与读取的顺序是相反的，如果将上面的链表打印，会看到 data 是从 10->1.

尾插法

就是插入链表节点时，从链表的尾部插入：

代码实现如下：

Node node = null;
Node last = null;
for (int i = 1; i <= 10; i++) {

    Node newNode = new Node();
    newNode.data = i;
    newNode.next = null;

    if (Objects.isNull(node)) {
        node = newNode;
        last = newNode;
    } else {
        last.next = newNode;
        last = newNode;
    }
}

JDK 1.8之前死循环问题的分析

假设我们目前有一个 HashMap 的结构如下:

• A、B、C 三个 Node 正好 Hash 冲突，在同一个槽位 3，在同一个链表上
• 此时新增一个 Node：D, 正好达到了扩容阈值，数组的大小从 4 扩容到 8.
• 扩容后，重新计算 Hash, A、B、C 碰巧又 Hash 冲突，被分配到了同一个槽位 6 上.

因为遍历原来链表，重新添加到新的链表，使用的是尾插法，所以可以看到新的链表的顺序与原先的正好是相反的。

JDK，1.7 中相应的代码如下：

这段代码的意思就是将老的数组里的每个链表的数据，采用头插法的方式转移到新的数组.

/**
 * Transfers all entries from current table to newTable.
 */
void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    // 遍历目前的数组(扩容前的数组，老数组)
    for (Entry<K,V> e : table) {
        
        // 遍历每个槽位里的链表
        while(null != e) {
            // 取出链表当前节点的 next 节点
            Entry<K,V> next = e.next;
            // 是否需要重新 hash，计算新的槽位位置
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            // 找到新数组的槽位
            int i = indexFor(e.hash, newCapacity);
            // 将当前节点指向新数组槽位链表的头部
            e.next = newTable[i];
            // 更新链表头部为当前节点
            newTable[i] = e;
            // 继续读取老链表的下一个节点
            e = next;
        }
    }
}

下面我们来分析一下并发是如何导致死循环的：

• 第一步，假设线程 T1 和 T2 刚开始执行，此时 e = A, e.next = B,
  如果继续执行，下一步将会采用尾插法插入新的数组，然后 B 的指针指向 A.
  但是此时，T2 线程的时间片用完，进入休眠，T1继续执行

• 第二步，线程T1一直执行到链表反转完成，此时 B 指向 A.

• 第三步，线程 T2 此时获取了执行权，继续执行，
  此时 e 指向 A，
  e.next = newTable[i]; 即将 A 指向链表头部，也就是 D
  newTable[i] = e; 即将链表头部设置为 A，
  e = next; 将 e 设置为 B.
  执行结束后链表结构如下图所示, 可以发现此时已经发生了循环.