1.7死循环问题处理

一、问题背景

JDK1.7及之前的HashMap底层采用数组+链表结构，扩容时采用头插法迁移链表节点。在多线程并发扩容场景下，可能会出现链表循环引用，导致CPU死循环。

二、死循环产生原理

1. 头插法扩容逻辑

JDK1.7的transfer方法中，扩容迁移链表时采用头插法：

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;
            // 计算新下标
            int i = indexFor(e.hash, newCapacity);
            // 头插法：将当前节点插入到新链表头部
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

头插法会导致扩容后链表顺序与原链表相反（原顺序A→B，扩容后变为B→A）。

2. 多线程场景复现

1. 线程1和线程2同时触发HashMap扩容，读取到同一个链表（A→B）
2. 线程2先完成扩容，将链表通过头插法迁移为B→A，此时B的next指向A
3. 线程1继续执行扩容，迁移A节点后，再迁移B节点时，B的next仍指向A，最终形成B→A→B的循环引用
4. 后续操作遍历该链表时，会陷入无限循环，导致CPU占用100%

三、JDK1.8的解决方案

1. 改为尾插法：扩容时不再将节点插入链表头部，而是保持原链表顺序插入尾部，避免链表反转导致的循环引用
2. 引入红黑树：当链表长度≥8且数组长度≥64时，链表转为红黑树，减少长链表场景下的循环引用风险
3. 注意：JDK1.8的HashMap仍非线程安全，只是解决了扩容死循环问题，并发场景仍需使用ConcurrentHashMap

四、面试高频问题解析

1. 问：JDK1.7的HashMap为什么会出现死循环？答： 因为JDK1.7的HashMap扩容时采用头插法，多线程并发扩容时，链表反转会导致节点间形成循环引用，遍历链表时会陷入死循环。

2. 问：JDK1.8如何解决了这个问题？答： JDK1.8将扩容时的链表插入方式改为尾插法，保持原链表顺序，避免了链表反转导致的循环引用，从而解决了死循环问题。

3. 问：解决死循环问题后，JDK1.8的HashMap就是线程安全的吗？答： 不是。JDK1.8的HashMap仍未解决并发场景下的其他问题（如数据丢失、覆盖），并发场景仍需使用ConcurrentHashMap。

4. 问：为什么头插法会导致链表反转？答： 头插法每次将新节点插入链表头部，原链表A→B→C，扩容时依次插入A、B、C，最终新链表会变为C→B→A，导致链表顺序反转。