知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 07 - HashMap 的线程安全问题 > 导读:用一问一答的方式,讲清 HashMap 在多线程下的三类问题(JDK 7 死循环、数据丢失、size 不准),以及 ConcurrentHashMap 在 JDK 7 与 JDK 8 的架构差异和 put 流程里的关键设计取舍。适合需要评估并发容器选型的 Java 后端读者。 ## 一、先建立全局认知 ### Q:这道题的面试原题是什么?HashMap 到底哪里不安全? A:面试官通常这样问: > "HashMap 在多线程下有什么问题?ConcurrentHashMap 是如何解决的?" 先说结论:`HashMap` 的设计目标就是单线程使用,它没有为并发做任何同步。多线程同时读写会引发三类问题,按严重程度排序是——**JDK 7 的扩容死循环(CPU 100%)> 数据丢失 > size 统计不准**。理解这三类问题,才能理解 `ConcurrentHashMap` 每个设计的动机。 ### Q:问题一:JDK 7 的头插法为什么会造成死循环? A:这是最经典也最致命的一个坑: ```text JDK 7 的 HashMap 扩容时使用头插法,多线程下可能形成环形链表 场景: 线程 A 和线程 B 同时触发扩容 线程 A 执行到一半被挂起 线程 B 完成扩容,链表顺序变为 B → A 线程 A 恢复执行,按旧顺序插入,形成 A → B → A 的环 后果: get() 时遍历链表,陷入死循环,CPU 100% JDK 8 改为尾插法,解决了死循环问题 但仍然存在数据丢失问题 ``` **为什么这样写**:JDK 7 的 `transfer`(扩容迁移)采用头插法把旧链表节点逐个搬到新桶,头插法本身没问题,问题在于迁移过程没有同步保护:线程 A 迁移到一半被挂起,此时它持有的"下一个节点"引用已经被线程 B 改过,A 恢复后就会把节点接成环。之后任何一次 `get` 命中这个桶,遍历链表就会无限循环。 **代价与结论**:JDK 8 改为尾插法(保持链表原有相对顺序),从根上消除了成环的可能。但要注意——**尾插法只解决了死循环,没解决线程安全**,并发 put 依然会丢数据。 ### Q:问题二:为什么并发 put 会丢数据? A:因为"判断桶为空"和"写入桶"这两步不是原子的: ```java // 两个线程同时 put,且 key 的 hash 相同(落在同一个桶) // 线程 A: if (table[i] == null) { // 判断为 null // 被挂起 // 线程 B: if (table[i] == null) { // 也判断为 null table[i] = new Entry(key2, value2); // 写入 // 线程 A 恢复: table[i] = new Entry(key1, value1); // 覆盖了线程 B 的数据! // 线程 B 的数据丢失 ``` **取舍分析**:这是典型的竞态条件(race condition)——两个线程都通过了 `table[i] == null` 的检查,然后各自写入,后写的直接覆盖先写的,没有任何"检测到冲突并重试"的机制。这类问题在 JDK 8 的 `HashMap` 里依旧存在,也是为什么"多线程环境不能直接用 HashMap"的核心理由。 ### Q:问题三:size 为什么会算不准? A:因为 `size++`(读取-加一-写回)不是原子操作。 ```text 多线程同时 put 时,size++ 不是原子操作 可能导致 size 比实际元素数量小 ``` 两个线程可能同时读到 `size = 5`,各自加一后都写回 `6`,实际放了两个元素却只增加了 1。这个问题的危害比前两个小(只影响遍历/统计,不影响数据),但这也解释了为什么 `ConcurrentHashMap` 要用一套专门的计数机制(后文详解)。 ## 二、理解核心机制 ### Q:ConcurrentHashMap 在 JDK 7 和 JDK 8 的实现有什么本质区别? A:一句话概括:**JDK 7 是分段锁,JDK 8 是桶级别锁 + CAS**。 ```text JDK 7:Segment 数组(分段锁) 每个 Segment 是一个小 HashMap,有独立的锁 并发度 = Segment 数量(默认 16) JDK 8:Node 数组 + 链表/红黑树 + CAS + synchronized 更细粒度的锁:只锁链表/树的头节点 并发度 = 数组长度(最大并发数更高) ``` **取舍分析**: - JDK 7 用一个 `Segment`(继承自 `ReentrantLock`)锁住一段桶,把并发度从"全局 1"提升到"默认 16";代价是并发度被 Segment 数量写死,扩容也是一个 Segment 一个 Segment 地做。 - JDK 8 放弃 Segment,直接在**桶的头节点**上加 `synchronized`,锁粒度进一步细化;并发度受数组长度限制,容量越大并发度越高;同时在桶为空时用 CAS 无锁写入。数据结构上还引入了红黑树,防止哈希碰撞严重时链表退化成 O(n)。 - 代价是:JDK 8 的实现更复杂,但对开发者透明——接口层面几乎没有变化。 ### Q:JDK 8 的 put 流程具体是怎样的? A:下面是简化版源码逻辑,已经能覆盖主要分支: ```java // 简化版 put 逻辑 final V putVal(K key, V value) { int hash = spread(key.hashCode()); // 计算 hash for (Node<K,V>[] tab = table;;) { Node<K,V> f; int n, i, fh; if (tab == null || (n = tab.length) == 0) { tab = initTable(); // 懒初始化,CAS 保证只初始化一次 } else if ((f = tabAt(tab, i = (n-1) & hash)) == null) { // 桶为空,CAS 直接插入(无锁) if (casTabAt(tab, i, null, new Node<>(hash, key, value))) break; } else if ((fh = f.hash) == MOVED) { // 正在扩容,帮助迁移 tab = helpTransfer(tab, f); } else { // 桶不为空,锁住头节点 synchronized (f) { if (tabAt(tab, i) == f) { if (fh >= 0) { // 链表插入 } else if (f instanceof TreeBin) { // 红黑树插入 } } } // 链表长度 >= 8 时转为红黑树 if (binCount >= TREEIFY_THRESHOLD) treeifyBin(tab, i); } } addCount(1L, binCount); // 更新 size(LongAdder 思想) return null; } ``` 这段分支走向(懒初始化 → 空桶 CAS → 扩容协助 → 锁头节点插入)可以用下面这张流程图串起来:  [编辑 Excalidraw 源图](/images/java-interview-copy/concurrent/07-hashmap-thread-safe-hashmap-thread-safe-concurrent-hashmap-put-diagram.excalidraw) ### Q:这段 put 代码里最关键的几处设计是什么? A:原文总结了五条,逐条看它们解决了前面哪个问题: ```text 1. 懒初始化: 第一次 put 时才初始化数组,用 CAS 保证只有一个线程初始化 2. 桶为空时 CAS 插入(无锁): 不需要加锁,直接 CAS 写入,失败则重试 3. 桶不为空时 synchronized 锁头节点: 只锁当前桶的头节点,不同桶的操作完全并行 锁粒度比 JDK 7 的 Segment 更细 4. size 统计(LongAdder 思想): 用 baseCount + CounterCell[] 分段累加 避免高并发下 size++ 的竞争 5. 扩容时多线程协助: 扩容时其他线程 put 会帮助迁移数据(helpTransfer) 加速扩容完成 ``` **取舍分析(这五条为什么这样设计)**: - **懒初始化 + CAS**:避免构造时就分配大数组浪费内存;用 CAS 而不是加锁,保证"初始化只做一次"的同时不阻塞其他路径。 - **空桶 CAS、非空桶 synchronized**:这是并发度提升的关键——大部分桶在大多数时刻是空的或冲突不严重,空桶直接 CAS 无需加锁;只有真正发生哈希冲突、需要操作链表/树时才锁**头节点**。锁的是头节点而不是整张表,所以不同桶可以完全并行。 - **`MOVED` 与 `helpTransfer`**:扩容时其他线程来 put,发现头节点是 `MOVED` 转发节点,就顺手帮忙迁移一段,把扩容成本摊给所有写线程,减少单线程迁移的长时间停顿。 - **`LongAdder` 思想的计数**:`baseCount` 先 CAS 累加,冲突激烈时再分散到 `CounterCell[]` 数组的不同槽上分别累加,最后求和。这直接解决了前面"size 不准"的问题——不是让 `size++` 变原子,而是用空间换竞争。 - **链表转红黑树(`TREEIFY_THRESHOLD`)**:防止哈希碰撞攻击或极端分布下链表过长,把最坏查找从 O(n) 压到 O(log n)。阈值相关的默认值随 JDK 版本有过微调,如需精确值请结合所用版本确认。 ## 三、放进真实场景 ### Q:线程安全的 Map 有哪几种选择?该怎么选? A:JDK 提供了多种方案,选择取决于"并发量"和"是否需要有序": ```text HashMap:非线程安全,单线程或外部同步时使用 Hashtable:所有方法加 synchronized,性能差,已过时 Collections.synchronizedMap(map): 包装 HashMap,所有操作加同一把锁 性能比 Hashtable 稍好,但仍是全局锁 ConcurrentHashMap: 分段锁(JDK 7)/ 桶级别锁(JDK 8) 读操作无锁(volatile 保证可见性) 高并发场景首选 ConcurrentSkipListMap: 有序的线程安全 Map(基于跳表) 需要有序遍历时使用 ``` **取舍分析**: - `Collections.synchronizedMap` 与 `Hashtable` 都是"一把全局锁",实现简单但高并发下会成为瓶颈;`Hashtable` 还额外禁止了 `null` 键值,属于历史遗留,新代码不应再用。 - `ConcurrentHashMap` 是绝大多数并发场景的默认选择:高并发下性能优势明显。 - 但要注意:`ConcurrentHashMap` **不保证有序**,也不保证多个操作之间的原子性(见下)。如果需要按 key 有序遍历,用 `ConcurrentSkipListMap`(基于跳表实现,查找/插入为 O(log n) 量级)。 ## 四、总结与自测 ### Q:ConcurrentHashMap 的 get 操作需要加锁吗? A:不需要。`Node` 的 `val` 和 `next` 字段用 `volatile` 修饰,保证可见性。get 操作只读不写,不需要加锁,性能很高。 补充一句取舍:正因如此,get 看到的是"某个时刻的稳定视图",不保证能读到正在进行中的 put 的结果——这是并发容器"高吞吐优先于强一致"的典型权衡。 ### Q:ConcurrentHashMap 能保证复合操作的原子性吗? A:不能。单个 put/get 是线程安全的,但复合操作(如"不存在才插入")不是原子的。典型反例是"先 get 判断为空,再 put"——两步之间其他线程可能已经插入了。正确做法是用 `putIfAbsent()`、`computeIfAbsent()` 这类原子方法,而不是先 get 再 put。 再延伸一点:`size()` 在 `ConcurrentHashMap` 里也不是强一致的精确值(它由 `baseCount` 与 `CounterCell[]` 汇总而来),并发写入期间可能略有偏差,只适合做近似统计,不要用它做业务上的精确判断。 ### Q:面试里怎么答这道题? A:建议按"问题 → 方案 → 取舍"三步作答: 1. **先说 HashMap 的三类问题**:JDK 7 头插法扩容可能成环导致 get 死循环、CPU 100%;并发 put 因"检查-写入"非原子而丢数据(JDK 8 依然存在);`size++` 非原子导致统计不准。 2. **再说 ConcurrentHashMap 的演进**:JDK 7 用 Segment 分段锁;JDK 8 改为"Node 数组 + 链表/红黑树 + CAS + synchronized 锁头节点",并发度受数组长度限制、更高。 3. **最后补关键细节**:懒初始化用 CAS、空桶 CAS 无锁写、非空桶锁头节点、`MOVED` 转发节点与 helpTransfer 协助扩容、`LongAdder` 思想做计数、链表转红黑树的阈值;以及 get 无锁(volatile)、复合操作仍需 `putIfAbsent`/`computeIfAbsent`。 --- ## 自测 1. 为什么说 JDK 8 改成尾插法只是"解决了死循环",却没有解决线程安全? 2. ConcurrentHashMap 在 JDK 8 里把锁加在哪?为什么这样比 JDK 7 的 Segment 并发度更高? 3. `ConcurrentHashMap` 的 "先 get 再 put" 为什么仍然不安全?应该改成什么?
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入