Skip to content

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 快照一致性。

  • 分层要点:

    1. JDK 7 分段锁:结构是 Segment[],每个 Segment 继承 ReentrantLock,内部再挂 HashEntry[];默认 concurrencyLevel=16,段数向上取 2 的幂,用 segmentFor(hash) 定位段。get 不加锁,靠 HashEntry.value 的 volatile 读;put 先 scanAndLockForPut 自旋,再锁住整个 Segment,段内 rehash。不同 Segment 的写可以并行,同一 Segment 串行;并发度上限由段数决定。
    2. 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 快照一致性,迭代器/批量操作才是弱一致。
    3. JDK 8 写:putVal 先检查 null;表未初始化就 initTable()(CAS sizeCtl 到 -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 保护不了整个桶,锁桶头更简单。
    4. 扩容与计数:transfer 把旧表分成多个区间,线程通过 CAS transferIndex 领取任务(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[]:低竞争时 CAS baseCount,冲突时按线程探针分散到 CounterCell(@Contended 防伪共享);冲突严重时走 fullAddCount,它用 cellsBusy 自旋锁完成 counterCells 的初始化和扩容。size()/mappingCount() 通过 sumCount() 求和,都是弱一致;addCount 发现 size >= sizeCtl 时会触发或协助扩容。
    5. 边界与选型:CHM 不允许 null key/value,因为 get 返回 null 无法区分“不存在”和“值为 null”;get + put 不是原子操作,要用 putIfAbsent、computeIfAbsent、merge、replace 等复合 API;remove/replace 走 replaceNode 锁桶头,树桶删除可能 untreeify;迭代器是弱一致的,不抛 ConcurrentModificationException,但也不是快照。和 Hashtable、Collections.synchronizedMap 相比,CHM 读不加锁、写锁桶,并发度高得多;单线程小数据则 HashMap 更轻。
  • 图/流程:

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。
  • 对比表:

节点hash作用
Node>= 0普通链表节点
ForwardingNodeMOVED = -1扩容迁移占位;find 去 nextTable
TreeBinTREEBIN = -2红黑树桶头;find 用 lockState 协调读
ReservationNodeRESERVED = -3computeIfAbsent/compute/merge 占位;find 返回 null;JDK 9+ putVal 抛 Recursive update
JDK 8 sizeCtl含义
0未初始化
-1正在初始化
正数下一次扩容阈值(约 0.75n)
其他负数扩容中:高 16 位 resizeStamp(n),低 16 位「参与线程数 + 1」
维度JDK 7JDK 8
锁粒度Segment,默认 16 段桶头节点
结构Segment[] + HashEntry[]Node[] + 链表/红黑树
读无锁,volatile无锁,volatile
写锁整个 Segment空桶 CAS,非空桶 synchronized
并发度受段数限制接近桶数
扩容段内 rehash多线程协助 transfer
size两次统计,必要时锁全段baseCount + CounterCell
树化无有
方案锁范围读并发写并发备注
HashMap无不安全不安全单线程/只读
Collections.synchronizedMap整张表串行串行简单但并发度低
Hashtable整张表串行串行老类,不推荐
ConcurrentHashMap单个桶基本无锁桶级并行高并发首选
  • 追问链:

    1. CHM 的读为什么不用加锁? → tabAt 和节点的 val/next 是 volatile,读路径只做指针遍历;某个 key 已完成的 put 对后续 get 可见,但多 key 之间没有快照一致性。
    2. JDK 8 为什么放弃 Segment? → Segment 数量固定、锁粒度粗,热点段仍会串行;桶级锁 + 空桶 CAS 把并发度细化到桶,内存开销也更低。
    3. size() 为什么可能不准? → 计数分散在 baseCount 和多个 CounterCell 里,求和时其他线程还在更新;它是估计值,业务判断用 mappingCount() 或自己维护计数。
    4. 扩容时其他线程在做什么? → 通过 ForwardingNode 感知迁移,helpTransfer 加入搬运;transferIndex 把旧表分段认领,避免所有线程挤在同一段。
    5. sizeCtl 有哪些状态? → 0 未初始化;-1 正在初始化;其他负数表示扩容中(带 stamp 和参与线程数);正数是下一次扩容阈值。
    6. 为什么 CHM 不允许 null? → get 返回 null 时无法区分“key 不存在”和“value 就是 null”;HashMap 允许 null,所以没有这个歧义。
    7. get 后再 put 是原子的吗? → 不是;两个线程都可能先 get 到 null 再各自 put。用 putIfAbsent、computeIfAbsent、merge,它们对单个桶是原子的。
    8. computeIfAbsent 有什么坑? → mapping function 在桶锁内执行,长耗时或阻塞会卡住该桶;函数里递归修改同一个 map,JDK 9+ 会抛 IllegalStateException("Recursive update"),JDK 8 不要依赖该行为,应保持纯计算。
    9. CHM 的迭代器会抛 CME 吗? → 不会;它是弱一致迭代器,不保证看到全部更新,也不保证是某一时刻的快照。
    10. TreeBin 是什么? → 桶内红黑树的容器,用 lockState 维护 WRITER=1/WAITER=2/READER=4 和 waiter,读者 CAS 加计数;有写者或写者等待时 find 退化为链表遍历;节点数减少到阈值以下会 untreeify。
    11. CHM 和 Hashtable 怎么选? → 新代码用 CHM;Hashtable 和 synchronizedMap 都是整表锁,读也串行,只在维护老代码时见到。
    12. spread 为什么要 & HASH_BITS? → 清除符号位,保证普通节点 hash 非负;负数留给特殊节点(MOVED/TREEBIN/RESERVED),这样 fh >= 0 就能区分普通桶。
    13. treeifyBin 为什么先判断 64? → 小表碰撞多通常是容量不足,先 tryPresize(n << 1) 扩容比建树便宜,也避免频繁树化/退化;达到 64 才转 TreeBin。
    14. transfer 的 lastRun 是什么? → 链表迁移时找最后一段 hash & n 相同的连续后缀的起点,复用这段后缀,只克隆前面的节点,减少节点分配。
    15. TreeBin 的 lockState 怎么工作? → WRITER=1/WAITER=2/READER=4;写者独占,读者用 CAS 加读计数;有写者或写者等待时 find 退化为链表遍历,避免阻塞在树重平衡上。
    16. 为什么非空桶用 synchronized 而不是 CAS? → 非空桶要改 next/树结构和计数,单个 CAS 保护不了整个桶;synchronized 锁桶头简单、可重入,空桶 CAS 是快路径。
    17. addCount 什么时候触发扩容? → size >= sizeCtl 时;先 CAS sizeCtl 进入 transfer,其他线程通过 helpTransfer 协助。
    18. sizeCtl 的负数怎么读? → 高 16 位 resizeStamp(n),低 16 位参与线程数 + 1;-1 是初始化,其他负数才是扩容。
    19. ReservationNode 是干什么的? → computeIfAbsent/compute/merge 在空桶上先放占位节点,防止其他线程并发插入;find 返回 null。JDK 8 的 putVal 没有显式检查,JDK 9+ 遇到它才抛 IllegalStateException("Recursive update")。
    20. put 已存在的 key 会覆盖吗? → 会;putVal 遍历到相同 key 时按 onlyIfAbsent 更新/返回旧值,putIfAbsent 不覆盖。
  • 生产案例/取舍(示例,替换成你的项目):

    • 本地缓存用 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 可能自旋或行为不确定。
  • 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、弱一致、复合操作等边界 → 生产案例。