Appearance
2.2-2 ConcurrentHashMap(JDK 7 / 8)
所属:02 Java 运行时 / 2.2 集合 分级:A 状态:◐ 初稿 关联:2.2-1、2.2-5、2.2-6、2.4-3、2.4-5
题型:原理 / 对比
一句话结论:ConcurrentHashMap 用“CAS + 桶级锁 + volatile”实现高并发:JDK 7 是 Segment 分段锁,JDK 8 细化到单个桶;读基本无锁,写只锁冲突桶,扩容支持多线程协助,size 用
baseCount + CounterCell分散计数;它保证单个 key 已完成更新的可见性,但不提供多 key 快照一致性。分层要点:
- JDK 7 分段锁:结构是
Segment[],每个 Segment 继承ReentrantLock,内部再挂HashEntry[];默认concurrencyLevel=16,段数向上取 2 的幂,用segmentFor(hash)定位段。get不加锁,靠HashEntry.value的 volatile 读;put先scanAndLockForPut自旋,再锁住整个 Segment,段内rehash。不同 Segment 的写可以并行,同一 Segment 串行;并发度上限由段数决定。 - JDK 8 结构与读:放弃 Segment,改成
Node[] table,桶内是链表或TreeBin红黑树;spread(h) = (h ^ (h >>> 16)) & HASH_BITS(HASH_BITS=0x7fffffff),再用(n-1) & hash定位。get完全不加锁:tabAt是 volatile 读,先比 hash 再比 key;如果桶头 hash 小于 0,说明是特殊节点——ForwardingNode(MOVED=-1,去nextTable找)、TreeBin(TREEBIN=-2,走find)或ReservationNode(RESERVED=-3,find返回 null),调用它们的find。get不加锁但 volatile 读写提供 happens-before:某个 key 已完成的put,后续get能看到;它不保证多 key 快照一致性,迭代器/批量操作才是弱一致。 - JDK 8 写:
putVal先检查 null;表未初始化就initTable()(CASsizeCtl到 -1;竞争失败Thread.yield();分配Node[n],阈值设为n - (n >>> 2));目标桶为空用casTabAt直接放新 Node;桶头是MOVED就helpTransfer帮扩容;否则synchronized (f)锁住桶头,锁内再确认tabAt(tab, i) == f,然后链表遍历:key 已存在就按onlyIfAbsent更新/返回,否则尾插;树桶走TreeBin.putTreeVal;遇到ReservationNode说明有人在computeIfAbsent/compute/merge:JDK 8 的putVal没有显式分支,binCount保持 0、会重试(同线程递归时可能自旋卡住);JDK 9+ 才抛IllegalStateException("Recursive update"),不要依赖 JDK 8 的递归更新行为。binCount >= 8(插入第 9 个节点)时调treeifyBin:n < 64先tryPresize(n << 1)扩容,n >= 64才把链表包成TreeNode、new TreeBin(hd)。最后addCount,必要时触发或协助transfer。空桶用 CAS,非空桶用synchronized:非空桶要改next/树结构和计数,单个 CAS 保护不了整个桶,锁桶头更简单。 - 扩容与计数:
transfer把旧表分成多个区间,线程通过 CAStransferIndex领取任务(stride 默认至少 16 个桶),迁移完的桶放ForwardingNode,其他写线程遇到它会helpTransfer一起搬。链表迁移先找lastRun(最后一段hash & n相同的连续后缀的起点),复用后缀、只克隆前面的节点到 lo/hi;树桶按hash & n拆 lo/hi:某侧<= 6就untreeify,否则若另一侧非空则new TreeBin,另一侧为空则复用原TreeBin。sizeCtl用负数表示初始化/扩容:高 16 位是resizeStamp(n),低 16 位是「参与线程数 + 1」,RESIZE_STAMP_SHIFT=16;正数是下一次扩容阈值。计数用baseCount+CounterCell[]:低竞争时 CASbaseCount,冲突时按线程探针分散到CounterCell(@Contended防伪共享);冲突严重时走fullAddCount,它用cellsBusy自旋锁完成counterCells的初始化和扩容。size()/mappingCount()通过sumCount()求和,都是弱一致;addCount发现size >= sizeCtl时会触发或协助扩容。 - 边界与选型:CHM 不允许 null key/value,因为
get返回 null 无法区分“不存在”和“值为 null”;get+put不是原子操作,要用putIfAbsent、computeIfAbsent、merge、replace等复合 API;remove/replace走replaceNode锁桶头,树桶删除可能untreeify;迭代器是弱一致的,不抛ConcurrentModificationException,但也不是快照。和Hashtable、Collections.synchronizedMap相比,CHM 读不加锁、写锁桶,并发度高得多;单线程小数据则 HashMap 更轻。
- JDK 7 分段锁:结构是
图/流程:
text
putVal(key, value)
hash = spread(key.hashCode()) = (h ^ h >>> 16) & 0x7fffffff
i = (n - 1) & hash
├─ table 未初始化 → initTable():CAS sizeCtl 到 -1
├─ 桶为空 → casTabAt 放新 Node
├─ 桶头 hash == MOVED(-1) → helpTransfer()
└─ 否则 synchronized (桶头 f)
├─ 再检查 tabAt(tab, i) == f
├─ key 已存在 → 按 onlyIfAbsent 更新/返回
├─ 链表 → 尾插;TreeBin(-2) → putTreeVal
├─ ReservationNode(-3) → JDK 8 重试 / JDK 9+ 异常
└─ binCount >= 8 → treeifyBin
├─ n < 64 → tryPresize(n << 1)
└─ n >= 64 → TreeNode → new TreeBin(hd)
addCount(1, binCount)
├─ CAS baseCount
├─ 冲突 → CounterCell[] 分散 / fullAddCount
└─ size >= sizeCtl → transfer / helpTransfer
transfer:
CAS transferIndex 领区间 → 迁移桶 → 放 ForwardingNode
链表:找 lastRun,复用后缀,前缀拆 lo/hi
树桶:拆 lo/hi,某侧 <= 6 → untreeify;否则另一侧非空才 new TreeBin,否则复用原树版本/源码锚点:
- JDK 7:
Segment、HashEntry、scanAndLockForPut、segmentFor、rehash;concurrencyLevel默认 16。 - JDK 8:
Node、TreeBin、ForwardingNode、ReservationNode;putVal、initTable、transfer、helpTransfer、addCount、sumCount;sizeCtl、transferIndex。 - JDK 8 常量:
HASH_BITS=0x7fffffff、MOVED=-1、TREEBIN=-2、RESERVED=-3、MIN_TREEIFY_CAPACITY=64、MIN_TRANSFER_STRIDE=16、RESIZE_STAMP_SHIFT=16。 - JDK 8 方法补充:
tryPresize、replaceNode、TreeBin.removeTreeNode、fullAddCount、sumCount。 - JDK 17/21:结构与 JDK 8 基本一致;CHM 仍主要使用
jdk.internal.misc.Unsafe的getObjectVolatile/compareAndSetObject等,未整体迁移到VarHandle。
- JDK 7:
对比表:
| 节点 | hash | 作用 |
|---|---|---|
Node | >= 0 | 普通链表节点 |
ForwardingNode | MOVED = -1 | 扩容迁移占位;find 去 nextTable |
TreeBin | TREEBIN = -2 | 红黑树桶头;find 用 lockState 协调读 |
ReservationNode | RESERVED = -3 | computeIfAbsent/compute/merge 占位;find 返回 null;JDK 9+ putVal 抛 Recursive update |
JDK 8 sizeCtl | 含义 |
|---|---|
0 | 未初始化 |
-1 | 正在初始化 |
| 正数 | 下一次扩容阈值(约 0.75n) |
| 其他负数 | 扩容中:高 16 位 resizeStamp(n),低 16 位「参与线程数 + 1」 |
| 维度 | JDK 7 | JDK 8 |
|---|---|---|
| 锁粒度 | Segment,默认 16 段 | 桶头节点 |
| 结构 | Segment[] + HashEntry[] | Node[] + 链表/红黑树 |
| 读 | 无锁,volatile | 无锁,volatile |
| 写 | 锁整个 Segment | 空桶 CAS,非空桶 synchronized |
| 并发度 | 受段数限制 | 接近桶数 |
| 扩容 | 段内 rehash | 多线程协助 transfer |
| size | 两次统计,必要时锁全段 | baseCount + CounterCell |
| 树化 | 无 | 有 |
| 方案 | 锁范围 | 读并发 | 写并发 | 备注 |
|---|---|---|---|---|
| HashMap | 无 | 不安全 | 不安全 | 单线程/只读 |
Collections.synchronizedMap | 整张表 | 串行 | 串行 | 简单但并发度低 |
| Hashtable | 整张表 | 串行 | 串行 | 老类,不推荐 |
| ConcurrentHashMap | 单个桶 | 基本无锁 | 桶级并行 | 高并发首选 |
追问链:
- CHM 的读为什么不用加锁? →
tabAt和节点的val/next是 volatile,读路径只做指针遍历;某个 key 已完成的put对后续get可见,但多 key 之间没有快照一致性。 - JDK 8 为什么放弃 Segment? → Segment 数量固定、锁粒度粗,热点段仍会串行;桶级锁 + 空桶 CAS 把并发度细化到桶,内存开销也更低。
size()为什么可能不准? → 计数分散在baseCount和多个CounterCell里,求和时其他线程还在更新;它是估计值,业务判断用mappingCount()或自己维护计数。- 扩容时其他线程在做什么? → 通过
ForwardingNode感知迁移,helpTransfer加入搬运;transferIndex把旧表分段认领,避免所有线程挤在同一段。 sizeCtl有哪些状态? → 0 未初始化;-1 正在初始化;其他负数表示扩容中(带 stamp 和参与线程数);正数是下一次扩容阈值。- 为什么 CHM 不允许 null? →
get返回 null 时无法区分“key 不存在”和“value 就是 null”;HashMap 允许 null,所以没有这个歧义。 get后再put是原子的吗? → 不是;两个线程都可能先get到 null 再各自put。用putIfAbsent、computeIfAbsent、merge,它们对单个桶是原子的。computeIfAbsent有什么坑? → mapping function 在桶锁内执行,长耗时或阻塞会卡住该桶;函数里递归修改同一个 map,JDK 9+ 会抛IllegalStateException("Recursive update"),JDK 8 不要依赖该行为,应保持纯计算。- CHM 的迭代器会抛 CME 吗? → 不会;它是弱一致迭代器,不保证看到全部更新,也不保证是某一时刻的快照。
TreeBin是什么? → 桶内红黑树的容器,用lockState维护WRITER=1/WAITER=2/READER=4和waiter,读者 CAS 加计数;有写者或写者等待时find退化为链表遍历;节点数减少到阈值以下会untreeify。- CHM 和 Hashtable 怎么选? → 新代码用 CHM;Hashtable 和
synchronizedMap都是整表锁,读也串行,只在维护老代码时见到。 spread为什么要& HASH_BITS? → 清除符号位,保证普通节点 hash 非负;负数留给特殊节点(MOVED/TREEBIN/RESERVED),这样fh >= 0就能区分普通桶。treeifyBin为什么先判断 64? → 小表碰撞多通常是容量不足,先tryPresize(n << 1)扩容比建树便宜,也避免频繁树化/退化;达到 64 才转TreeBin。transfer的lastRun是什么? → 链表迁移时找最后一段hash & n相同的连续后缀的起点,复用这段后缀,只克隆前面的节点,减少节点分配。TreeBin的lockState怎么工作? →WRITER=1/WAITER=2/READER=4;写者独占,读者用 CAS 加读计数;有写者或写者等待时find退化为链表遍历,避免阻塞在树重平衡上。- 为什么非空桶用
synchronized而不是 CAS? → 非空桶要改next/树结构和计数,单个 CAS 保护不了整个桶;synchronized锁桶头简单、可重入,空桶 CAS 是快路径。 addCount什么时候触发扩容? →size >= sizeCtl时;先 CASsizeCtl进入transfer,其他线程通过helpTransfer协助。sizeCtl的负数怎么读? → 高 16 位resizeStamp(n),低 16 位参与线程数 + 1;-1是初始化,其他负数才是扩容。ReservationNode是干什么的? →computeIfAbsent/compute/merge在空桶上先放占位节点,防止其他线程并发插入;find返回 null。JDK 8 的putVal没有显式检查,JDK 9+ 遇到它才抛IllegalStateException("Recursive update")。put已存在的 key 会覆盖吗? → 会;putVal遍历到相同 key 时按onlyIfAbsent更新/返回旧值,putIfAbsent不覆盖。
- CHM 的读为什么不用加锁? →
生产案例/取舍(示例,替换成你的项目):
- 本地缓存用
computeIfAbsent回源数据库,mapping function 里做了一次 2 秒的 RPC,结果同一桶的其他 key 全被阻塞;改成先get,未命中再异步加载并putIfAbsent,避免长事务占着桶锁。 - 监控面板直接读
CHM.size()做精确告警,导致误报;改成mappingCount()并接受弱一致,或用业务侧计数器。 - 路由表、会话表、黑名单这类“读多写少、按 key 分散”的场景,CHM 很合适;如果是全局计数,
LongAdder比CHM<String, Long>更合适。 - 取舍:CHM 读快、写并发高,但内存比 HashMap 大、弱一致、复合操作要选对 API;单线程或只读场景没必要上 CHM。
- 本地缓存用
易错点:
- 对 null key/value 调
put/get,直接 NPE。 - 把
size()当精确值,或用它做“达到 N 就触发”的业务判断。 - 用
get+put实现“不存在才放入”,并发下重复写入。 - 在
computeIfAbsent的 mapping function 里递归改同一个 map,或做长耗时阻塞操作。 - 认为 CHM 的迭代器是快照,边遍历边依赖一致性。
- 用 CHM 存可变对象,误以为对象内部状态也线程安全。
- 认为 JDK 8 的 CHM 还有 Segment 分段锁——运行时已改成桶级锁。
- 把
ConcurrentHashMap当分布式缓存,忽略它只在单 JVM 内有效。 - 认为
get一定读不到刚写入的值——已完成的put对后续get可见;弱一致指的是多 key 快照和进行中的写。 - 认为 CHM 的
treeifyBin和 HashMap 一样直接resize()——CHM 是tryPresize,且n < 64只扩容不建树。 - 认为
TreeBin用ReentrantReadWriteLock——它用lockState+waiter的 CAS/自旋。 - 认为 JDK 17/21 的 CHM 已经改用
VarHandle——仍主要是Unsafe。 - 认为 JDK 8 的
computeIfAbsent递归更新一定会抛Recursive update——显式检查是 JDK 9+ 才加的,JDK 8 可能自旋或行为不确定。
- 对 null key/value 调
30 秒口述稿:
ConcurrentHashMap 是并发哈希表。JDK 7 用 Segment 分段锁,默认 16 段,每段一个 ReentrantLock,读不加锁靠 volatile;JDK 8 放弃 Segment,改成 Node 数组,空桶 CAS 插入,非空桶 synchronized 锁桶头,读仍然无锁;扩容时用 ForwardingNode 和 transferIndex 让多个线程协助迁移;size 用 baseCount 加 CounterCell 分散计数,所以是弱一致。它不允许 null key/value,get 加 put 不是原子的,要用 computeIfAbsent、merge、putIfAbsent 这些复合 API。
- 3 分钟展开顺序:结论 → JDK 7 分段锁与并发度上限 → JDK 8 的 Node 数组、spread/特殊 hash 和读路径 → 写路径(CAS 空桶、锁桶头、treeify 64、helpTransfer)→ 扩容(lastRun/树桶拆分)与计数 → JDK 7/8 对比及与 Hashtable 对比 → null、弱一致、复合操作等边界 → 生产案例。