多线程环境下，HashMap 为什么会出现死循环？

Sam_Deep_Thinking

489人浏览 · 2026-06-17 09:48:33

Sam_Deep_Thinking · 2026-06-17 09:48:33 发布

概述

年轻的时候看过陈皓大神的JAVA HASHMAP的死循环,当时对HashMap多线程死循环问题印象深刻。那会儿用的还是JDK 7,确实会死循环。

但现在是2026年了,项目中用的JDK 17,还会死循环吗?答案是:不会了，不过光知道结论不够,我们还是得看一下open sdk 17的源码,看看到底改了啥。

重要提示:虽然不会死循环了,HashMap在并发环境下依然不安全,会有数据丢失、覆盖等问题。该用ConcurrentHashMap还得用ConcurrentHashMap。

更好的算法：尾插法

JDK 7用头插法扩容会把链表反转,JDK 17改成尾插法保持原序。这个改动直接杜绝了死循环问题。

对比一下:

JDK 7: 新元素插入链表头部 → 扩容时链表顺序反转 → 并发时两个线程互掐形成环
JDK 17: 新元素追加到链表尾部 → 扩容时顺序不变 → 最多数据覆盖,不会成环

用图对比一下两种插入方式:

添加图片注释，不超过 140 字（可选）

看一下JDK 17 源代码

HashMap的数据结构长啥样

JDK 17的HashMap底层是数组+链表+红黑树的组合:

数组:Node<K,V>[] table — 主体骨架
链表:hash冲突时用next指针串起来
红黑树:链表太长(>8)就转树,避免性能退化

// JDK 17 HashMap的节点定义
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;  // 指向链表下一个节点
    
    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
}

JDK 17的resize扩容源码

直接看实现,我删掉了一些边界检查和异常处理,留下最关键的扩容逻辑:

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // ... 计算新容量 newCap ...
    
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;  // 直接替换为新数组
    
    if (oldTab != null) {
        // 遍历旧数组的每个桶
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                
                if (e.next == null)
                    // 只有一个节点,直接放到新位置
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    // 红黑树的拆分逻辑(这里不展开)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else {
                    // ====== 关键!链表的rehash逻辑 ======
                    Node<K,V> loHead = null, loTail = null;  // 低位链表
                    Node<K,V> hiHead = null, hiTail = null;  // 高位链表
                    Node<K,V> next;
                    
                    do {
                        next = e.next;
                        // 通过 (e.hash & oldCap) 判断节点去向
                        if ((e.hash & oldCap) == 0) {
                            // 留在原位置
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;  // 尾插法!
                            loTail = e;
                        }
                        else {
                            // 移到 原位置+oldCap
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;  // 尾插法!
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    
                    // 处理尾节点
                    if (loTail != null) {
                        loTail.next = null;  // 斩断旧链接
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;  // 斩断旧链接
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

关键点就两个:

尾插法: loTail.next = e 这行代码,始终往链表尾巴接,顺序天然不会乱；
把链断掉: loTail.next = null 最关键的一部操作，强制把尾节点next设为null,物理上不可能成环；

JDK 7是怎么死循环的

先看旧代码(头插法)

// JDK 7的rehash代码(简化版)
void transfer(Entry[] newTable) {
    Entry[] src = table;
    for (int j = 0; j < src.length; j++) {
        Entry<K,V> e = src[j];
        if (e != null) {
            src[j] = null;
            do {
                Entry<K,V> next = e.next;
                int i = indexFor(e.hash, newTable.length);
                
                e.next = newTable[i];  // 头插法!新节点指向旧头
                newTable[i] = e;       // 新节点变成新头
                
                e = next;
            } while (e != null);
        }
    }
}

问题出在哪? 看到 e.next = newTable[i] 这行没?每次都把新节点插到链表头,结果就是整个链表被反转了!

并发下怎么形成环的

假设有个容量为2的HashMap,里面已经有key 3、7、5三个节点,都落在同一个桶(index=1),链表是这样的:

table[1] → [3|next] → [7|next] → [5|null]

现在有两个线程thread1和thread2同时要扩容(容量从2扩到4),问题来了:

第一步，线程1刚执行到这里就被操作系统挂起了:

Entry<K,V> e = table[1];      // e指向节点3  
Entry<K,V> next = e.next;     // next指向节点7  
// 线程1挂起!

此时线程1手里的局部变量:

e 指向节点3
next 指向节点7

第二步，线程2没被挂起,顺利把扩容做完了(假设3、7、5在新数组里还是冲突,都落在index=3):

因为是头插法,链表被反转了:

newTable[3] → [5|next] → [7|next] → [3|null]

第三步，线程1终于恢复执行了,但要命的是,此时链表已经被线程2反转了，节点3的next已经是null,节点7的next指向节点3。

线程1继续它的扩容操作:

// 第1次循环: 处理节点3
e = 节点3  (但此时3.next已经被线程2改成null)
next = 节点7
e.next = newTable[3];  // 节点3.next指向null
newTable[3] = 节点3;
e = next;  // e指向节点7

// 第2次循环: 处理节点7
next = e.next;  // 节点7.next现在指向节点3!(线程2改的)
e.next = newTable[3];  // 节点7.next指向节点3
newTable[3] = 节点7;
e = next;  // e指向节点3

// 第3次循环: 再次处理节点3
next = e.next;  // 节点3.next现在指向节点7!(刚才改的)
e.next = newTable[3];  // 节点3.next指向节点7
newTable[3] = 节点3;
// 死循环形成! 节点3 ⇄ 节点7 互相指向

这时候如果有个map.get()操作刚好落到这个桶,遍历链表就会在3和7之间无限循环,CPU直接100%,程序卡死。

这个bug当年坑了不少人,尤其是生产环境并发高的时候,偶尔会复现,查起来还挺费劲的。

JDK 17为啥不会死循环了，详细分析

尾插法天生不会反转

// JDK 17的插入逻辑
if (loTail == null)
    loHead = e;
else
    loTail.next = e;  // 接在尾部
loTail = e;           // 更新尾指针

即使两个线程同时扩容,最多是一个线程的修改被另一个覆盖掉,但链表的方向不会变。这是本质区别。

每次resize都是全新数组

Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;  // 直接替换引用

每个线程创建的都是新数组newTab,最后谁的table = newTab生效看线程调度,但不会搞乱链表结构。

显式把尾节点next置null

loTail.next = null;  
hiTail.next = null;

这两行代码保证链表肯定有终点,从物理结构上就杜绝了成环的可能。

实测:真的不会死循环了吗

写一个测试跑一下。10个线程疯狂往HashMap里塞数据,每个线程插1万条,初始容量只设了2,肯定会触发大量扩容:

package org.example;

import java.util.HashMap;
import java.util.concurrent.CountDownLatch;

/**
 * JDK 17 HashMap 并发测试
 * 用于验证 JDK 17 中 HashMap 在并发环境下是否还会产生死循环
 *
 * 测试结论: JDK 17 不会产生死循环,但会有数据丢失问题
 */
public class HashMapConcurrencyTest {

    /**
     * 测试: 尝试复现死循环(JDK 17 中不会发生)
     */
    public static void testDeadLoop() {
        final HashMap<Integer, Integer> map = new HashMap<>(2);

        // 线程数量
        int threadCount = 10;
        CountDownLatch latch = new CountDownLatch(threadCount);

        // 用于检测是否卡死
        Thread monitorThread = new Thread(() -> {
            try {
                Thread.sleep(5000); // 等待5秒
                System.out.println("5秒后检查: 程序仍在运行,未发生死循环");
                System.out.println("最终 map 大小: " + map.size());
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        });
        monitorThread.setDaemon(true);
        monitorThread.start();

        // 多线程并发 put,触发扩容
        for (int i = 0; i < threadCount; i++) {
            final int threadNum = i;
            new Thread(() -> {
                try {
                    // 每个线程插入大量数据,触发多次扩容
                    for (int j = 0; j < 10000; j++) {
                        map.put(threadNum * 10000 + j, j);
                    }
                } finally {
                    latch.countDown();
                }
            }, "Thread-" + i).start();
        }

        try {
            latch.await();
            System.out.println("所有线程执行完毕,未发生死循环!");
            System.out.println("理论应插入: " + (threadCount * 10000) + " 个元素");
            System.out.println("实际插入了: " + map.size() + " 个元素");

            // 尝试 get 操作,看是否会卡死
            for (int i = 0; i < 100; i++) {
                map.get(i);
            }
            System.out.println("get 操作正常,未发生死循环");

        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }

    public static void main(String[] args) {
        System.out.println("JDK 版本: " + System.getProperty("java.version"));
        System.out.println("\n开始测试 HashMap 并发问题...\n");

        testDeadLoop();

        System.out.println("\n结论: JDK 17 的 HashMap 不会产生死循环,但仍有数据丢失问题!");
    }
}

跑出来的结果:

JDK 版本: 17.0.12

开始测试 HashMap 并发问题...

所有线程执行完毕,未发生死循环!
理论应插入: 100000 个元素
实际插入了: 66339 个元素
get 操作正常,未发生死循环

结论: JDK 17 的 HashMap 不会产生死循环,但仍有数据丢失问题!

进程已结束，退出代码为 0