JDK7中HashMap使用头插法导致死循环的原因分析

JDK7中HashMap使用头插法导致死循环的原因分析

引用

CSDN

1.

https://blog.csdn.net/qq_66908247/article/details/144090365

在JDK7中，HashMap的实现存在一个有趣的问题：为什么使用头插法会在多线程环境下导致死循环？本文将通过详细的图解和代码分析，帮助读者理解这一复杂的技术问题。

什么是头插法？

在讨论死循环问题之前，我们先来了解一下什么是头插法。这里仅以HashMap底层实现为例进行说明。

假设HashMap底层数组长度为6，并且来了三个键值对的节点，它们的key计算出的hash值都一样（为了简化说明，实际默认长度为16）。

当第一个元素（节点1）需要插入时，HashMap会将其放置在计算出的数组位置上：

当第二个元素（节点2）到来时，由于发生了hash冲突，需要使用链表存储。根据头插法，节点2的next指针会指向链表的头节点（节点1），然后让节点2变成新的头节点：

按照这个流程，后续的节点（节点3）也会采用相同的方式插入：

为什么会发生死循环？

JDK7中的HashMap发生死循环的问题主要发生在多线程环境下的扩容操作中。在单线程环境下，扩容过程不会出现问题。我们先来看一下JDK7中HashMap的扩容函数：

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

单线程扩容

假设扩容后计算出的hash值仍然相同。当需要扩容时，HashMap会遍历数组和链表，重新计算每个元素的位置并插入新数组。这个过程在单线程环境下是安全的。

多线程扩容

问题出现在多线程环境下。假设两个线程同时触发扩容操作，并在以下代码处阻塞：

if (rehash) {
    e.hash = null == e.key ? 0 : hash(e.key);
}

此时，两个线程（线程1和线程2）都在处理同一个链表。假设线程2被阻塞，线程1继续执行并完成扩容。当线程2被唤醒时，它会继续执行扩容操作，但由于线程1已经改变了HashMap的状态，线程2的局部变量（e和next）仍然指向旧的状态。

具体来说，线程2会执行以下步骤：

1. e.next = newTable[i];：此时e指向3，next指向2
2. newTable[i] = e;：此时e指向3，next指向2
3. e = next;：此时e指向2，next指向3
4. newTable[i] = e;：此时e指向3，next指向null
5. e.next = newTable[i];：此时e指向3，next指向null

由于线程1已经改变了链表结构，线程2的next指针仍然指向旧的节点（3），这会导致链表出现循环，从而引发死循环。

这个例子展示了在多线程环境下，即使简单的链表操作也可能导致复杂的问题。这也是为什么JDK8对HashMap的实现进行了重大改进，引入了红黑树和更复杂的锁机制，以避免这类问题。