【多线程】-ConcurrentHashMap 源码解析

基于：OpenJDK JDK 8u 的 java.util.concurrent.ConcurrentHashMap（对照 JDK 7 分段锁实现与 JDK 9+ 演进）

本文以源码解析为主线，逐段拆解 JDK 8 版 ConcurrentHashMap 的核心实现：字段与 sizeCtl 语义、putVal 全链路、多线程协作扩容、无锁读、基于 CounterCell 的计数、红黑树化与 TreeBin，配合数据布局总图、类关系图、可运行示例与面试 FAQ。解决「源码读了记不住、面试讲不清 put 之后发生了什么」的问题。

1. 定位与历史演进

1.1 一句话定位

关键认知：ConcurrentHashMap 是 JUC 里「读多写少 + 高并发写」场景的线程安全 HashMap，JDK 8 版本以 CAS + 桶头 synchronized + 红黑树为核心：把锁粒度细化到每个哈希桶，无竞争写入只花一次 CAS，读操作完全无锁，扩容支持多线程协作——在保证线程安全的同时，把并发度从 JDK 7 的「16 个分段」提升到「桶个数」级别。

1.2 线程安全容器定位表

容器线程安全方式锁粒度读性能写性能（竞争）适用判断

Hashtable	全表一把锁（synchronized 方法）	整个表	锁内读	很差	历史遗留，勿用
Collections.synchronizedMap(map)	包装器锁（默认锁整个 map 对象）	整个表	锁内读	很差	仅小规模/兜底场景
ConcurrentHashMap（JDK 8+）	CAS + 桶头锁 + volatile	单个桶	无锁	好（分摊到桶）	默认并发首选
HashMap	无（依赖外部同步）	—	无锁最快	无锁最快	线程私有 / 外部已加锁
ConcurrentSkipListMap	CAS + 跳表	节点级	无锁	好	需要有序的并发 Map

一句话概括：凡是「一个 HashMap 被多个线程共享且需要增删」，默认答案就是 ConcurrentHashMap；Hashtable 与 synchronizedMap 的全局锁会让所有操作串行化，写入一多就退化。

1.3 从 JDK 7 到 JDK 8 的演进

维度JDK 7 ConcurrentHashMapJDK 8 ConcurrentHashMap

数据结构	Segment 数组（分段锁）+ 每个 Segment 内 HashEntry 链	直接是 Node 桶数组，桶内链表或红黑树
锁实现	继承 ReentrantLock 的 Segment，写某段锁某段	空桶 CAS 写入；非空桶 synchronized 锁桶头节点
锁粒度	16 个段（默认并发度 16，并发度上限 16）	桶数（可达 1<<30），并发度随扩容提升
读操作	需经过 volatile 读，不加锁	完全无锁（volatile + final + 不变性）
扩容	段内扩容，一次搬一段，段间互不影响	全表扩容，但多线程协同迁移（旧桶逐个搬）
计数	段内 count 相加	baseCount + CounterCell 分片（LongAdder 思想）
key/value	均不允许 null	均不允许 null
size()	依次加段 count，可能锁各段重算	遍历 CounterCell 求和，弱一致

为什么 JDK 8 敢放弃成熟的分段锁模型？核心原因：

锁粒度更细：分段锁粒度固定 16 段，热点段照样打架；桶锁粒度 = 桶数，且只在哈希冲突（桶非空）时才上锁，无冲突写入退化为一次 CAS；

读彻底无锁：JDK 7 读也要碰分段锁的 volatile 域；JDK 8 借助 volatile 桶引用 + Node 字段不可变/volatile 语义做到无锁读，读是并发场景最大头；

工程顺势而为：JDK 6 之后 synchronized 已被 JVM 全面优化（偏向锁/轻量级锁/锁消除），桶头加 synchronized 的成本低于 JDK 5 时代，代码还更简洁；官方解释也直言「synchronized 在 JDK 6 后性能已与 ReentrantLock 相当，而锁粒度细化后 synchronized 足以胜任」。

2. 整体设计总览

2.1 数据布局

JDK 8 的物理结构（桶数组里放四种节点之一，渲染版结构图）：在这里插入图片描述

桶内节点的 hash 字段被复用为类型标记（这是理解一切分派逻辑的钥匙）：

hash 值节点类型含义

≥ 0（真实哈希）	Node / TreeNode 链表	普通键值节点
-1（MOVED）	ForwardingNode	该桶已迁移完成，指向新表对应桶
-2（TREEBIN）	TreeBin	桶内是红黑树（TreeBin 是树根容器）
-3（RESERVED）	ReservationNode	computeIfAbsent 的占位节点

2.2 put 主流程总览

先建立全局视角，4~5 章再逐段对照源码：

put(key, value)
└─ putVal(key, value, onlyIfAbsent=false)
├─ ① key/value 判空（null 直接 NPE）
├─ ② table 为 null？──► initTable() 初始化（CAS 抢初始化权，见 3.2）
├─ ③ 定位桶：i = (table.length-1) & spread(hash)
├─ ④ 桶为 null？──► casTabAt 直接放新 Node（原子），成功即收工
├─ ⑤ 桶头 hash == MOVED？──► helpTransfer()：放下自己的写，先帮忙扩容
├─ ⑥ 否则 synchronized(桶头节点 f)：
│ ├─ 再次校验桶头没变（double-check）
│ ├─ f 是普通 Node：遍历链表
│ │ ├─ 找到同 key（equals）──► 覆盖 value（binCount 记录位置）
│ │ └─ 没找到 ──► 链表尾部插入新 Node
│ ├─ f 是 TreeBin：调用 putTreeVal 插入/覆盖红黑树
│ └─ 记录 binCount（链表长度，用于触发树化）
├─ ⑦ binCount ≥ 8（TREEIFY_THRESHOLD）──► treeifyBin() 尝试树化
│ （注意：桶数组 < 64 时先扩容而非树化）
└─ ⑧ addCount(1L, binCount) 计数，可能触发扩容（见第 5、6 章）

2.3 核心字段表

// JDK 8 实际字段（节选自 ConcurrentHashMap.java）
transient volatile Node<K,V>[] table; // 桶数组，懒初始化
private transient volatile Node<K,V>[] nextTable; // 扩容中的新表（只有扩容期非 null）

private transient volatile long baseCount; // 基础计数（无竞争时直接 CAS 更新）
private transient volatile int sizeCtl; // 并发控制总开关（见 2.4 表）
private transient volatile int transferIndex;// 扩容区间游标：下一个待迁移桶的起点
private transient volatile int cellsBusy; // CounterCell 数组扩容/初始化的锁（0/1）
private transient volatile CounterCell[] counterCells; // 计数分片（争用分散）

字段类型职责

table	Node[]	哈希桶数组，volatile 保证扩容后新表立即可见
nextTable	Node[]	扩容目标表（容量翻倍），仅扩容期间非 null
baseCount	long	无竞争时的计数累加基底
sizeCtl	int	状态机核心：初始容量/扩容阈值/初始化标记/扩容线程数，见下
transferIndex	int	扩容时从 table.length 递减，多线程从这里领取迁移区间
cellsBusy	int	CounterCell 表初始化的自旋锁（0=空闲，1=被占用）
counterCells	CounterCell[]	计数分片数组，降低热点竞争

2.4 sizeCtl 的语义

sizeCtl 是 CHM 的「大脑」，一个 int 在不同阶段表达四种含义——面试必考点：

sizeCtl 取值含义

0	表未初始化，且构造时未指定容量（用默认 16）
> 0	表未初始化 → 初始容量；表已初始化 → 扩容阈值（0.75 * 容量）
-1	有线程正在进行 initTable 初始化（只有一个线程能 CAS 成功）
< -1（如 -2）	正在扩容：-(1 + 参与扩容的线程数)，如 -2 表示已有 1 个线程在迁移

// initTable 里抢初始化权的核心 CAS（节选）
if ((sc = sizeCtl) < 0) // sizeCtl 为负 = 别人在初始化/扩容
Thread.yield();
else if (U.compareAndSwapInt(this, SIZECTL, sc, –1)) { // 把 0/容量换成 -1，抢权成功
try {
if (tab == null || tab.length == 0) {
int n = (sc > 0) ? sc : DEFAULT_CAPACITY; // 容量取自构造参数
...
tab = new Node[n];
sizeCtl = n – (n >>> 2); // 写回扩容阈值 0.75n
}
} finally {
// 失败则恢复
}
}

关键认知：CHM 的所有并发协作（初始化、扩容认领、计数分片）都围绕「对一个共享 int 的 CAS」展开，没有一把全局锁——这就是它高并发的根源。凡是看到对 sizeCtl/cellsBusy/transferIndex 的 compareAndSwapInt，都是「分布式协作点」。

3. 入口与构造

3.1 类声明与重要常量

public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>
implements ConcurrentMap<K,V>, Serializable {

// ── 容量与阈值常量 ─────────────────────────────
private static final int DEFAULT_CAPACITY = 16;
private static final int MAXIMUM_CAPACITY = 1 << 30;
private static final float LOAD_FACTOR = 0.75f; // 仅构造参数兼容用（JDK8 内部不用它算阈值）
static final int TREEIFY_THRESHOLD = 8; // 桶内链表长度达到 8 → 尝试树化
static final int UNTREEIFY_THRESHOLD = 6; // 扩容拆桶后树节点 ≤ 6 → 退化为链表
static final int MIN_TREEIFY_CAPACITY = 64; // 桶数组 < 64 时先扩容，不树化

// ── 桶头节点 hash 字段的特殊标记 ────────────────
static final int MOVED = –1; // ForwardingNode：桶已迁移
static final int TREEBIN = –2; // TreeBin：桶内是红黑树
static final int RESERVED = –3; // ReservationNode：computeIfAbsent 占位
static final int HASH_BITS = 0x7fffffff; // 符号位清零，保证 hash 非负

static final int NCPU = Runtime.getRuntime().availableProcessors();
}

两个反直觉点先记住：

LOAD_FACTOR = 0.75f 在 JDK 8 里只是构造器参数兼容（把容量换算成立即初始化的 n），扩容阈值一律写成 sizeCtl = n – (n >>> 2)，即 0.75n 的位运算写法；

普通键值节点的 hash 字段存放 spread() 之后的值，必然 ≥ 0——所以判断桶头类型只需看符号位。

3.2 构造器与懒初始化

// 无参构造：什么都不做（关键！表是懒初始化的）
public ConcurrentHashMap() { }

// 指定容量：只把它换算成 2 的幂存进 sizeCtl，仍然不建表
public ConcurrentHashMap(int initialCapacity) {
if (initialCapacity < 0) throw new IllegalArgumentException();
int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
MAXIMUM_CAPACITY :
tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
this.sizeCtl = cap; // 此时 sizeCtl = 目标容量（正数），不是阈值
}

// 表真正建立发生在第一次 put 的 initTable()

initTable 的并发正确性（见 2.4 代码）：多个线程同时首次 put，都发现 table == null，但只有一个能把 sizeCtl 从 0 CAS 成 -1——抢到者建表，其余线程 Thread.yield() 自旋等待，等 sizeCtl 变成正的阈值后退出。

关键认知：CHM 没有「构造即分配」的传统，内存占用与启动成本都被推迟到第一次写入。构造传入的 initialCapacity 会被当作「预期含元素数」，内部先加 50% 再取 2 的幂，所以 new ConcurrentHashMap<>(100) 实际容量 256——避免中途扩容。

3.3 Node 内部类体系

五个内部类分工明确（类关系图见第 9 章）：

// 1. 普通节点：桶内链表元素，val/next 都是 volatile
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
volatile V val;
volatile Node<K,V> next;
...
}

// 2. 链表转树时的中间节点（先成双向链表，再搭红黑树）
static final class TreeNode<K,V> extends Node<K,V> {
TreeNode<K,V> parent;
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // 双向链表指针（树退化成链表要靠它）
boolean red;
}

// 3. 树的桶容器（hash 固定 -2），持有红黑树根 + 首节点链表 + 读写锁状态
static final class TreeBin<K,V> extends Node<K,V> {
TreeNode<K,V> root;
volatile TreeNode<K,V> first; // 链头：写锁竞争时读退化为线性扫描
volatile int lockState; // 简化读写锁，见 8.2
...
}

// 4. 扩容转发节点（hash 固定 -1）：旧桶迁移完成后占位，指向新表
static final class ForwardingNode<K,V> extends Node<K,V> {
final Node<K,V>[] nextTable;
ForwardingNode(Node<K,V>[] tab) { super(MOVED, null, null, null); this.nextTable = tab; }
}

// 5. computeIfAbsent 的占位节点（hash 固定 -3），防止递归计算同一 key
static final class ReservationNode<K,V> extends Node<K,V> {
ReservationNode() { super(RESERVED, null, null, null); }
}

4. putVal 分步详解

put 最终调用 putVal(key, value, onlyIfAbsent)，下面按源码顺序分步拆解。

4.1 定位与空桶 CAS

public V put(K key, V value) { return putVal(key, value, false); }

final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException(); // ① 双 null 拒绝
int hash = spread(key.hashCode()); // ② 扰动哈希

int binCount = 0;
for (Node<K,V>[] tab = table;;) { // ③ 自旋（CAS 失败会重来）
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
tab = initTable(); // ④ 懒建表（3.2）
else if ((f = tabAt(tab, i = (n – 1) & hash)) == null) { // ⑤ 定位桶且桶空
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null))) // ⑥ 空桶 CAS 直放
break; // ✅ 成功即完成（无锁！）
}
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f); // ⑦ 桶已迁移 → 帮忙扩容
else {
... // ⑧ 桶非空：桶头加锁（4.3）
}
}
addCount(1L, binCount); // ⑨ 计数
return null;
}

要点：

spread()：(h ^ (h >>> 16)) & HASH_BITS——高位参与低位计算（hashCode 低位相同的 key 不再扎堆），同时把符号位抹掉保证 hash ≥ 0（否则会与 MOVED 等负数标记冲突）；
tabAt / casTabAt：对桶数组元素的 volatile 读写与 CAS，通过 Unsafe.getObjectVolatile 实现（数组元素无法直接用 volatile 修饰）；
空桶写入全程无锁：多线程各写各的空桶，各自 CAS 成功，互不干扰——这是 JDK 8 并发度的天花板（= 桶数）。

4.2 MOVED 与协助扩容

f.hash == MOVED 说明这个桶已被迁移走，桶里放的是 ForwardingNode：

// ForwardingNode 的 find 会把查询转发到新表
static final class ForwardingNode<K,V> extends Node<K,V> {
final Node<K,V>[] nextTable;
Node<K,V> find(int h, Object k) {
outer: for (Node<K,V>[] tab = nextTable;;) { // 读操作跳到新表继续找
...
}
}
}

写入方看到 MOVED 不会傻等，而是加入迁移队伍（helpTransfer，5.2 详述）——写线程在旧表继续写可能丢失新插入的数据，所以必须先把旧桶搬完。这也是 CHM 的一个设计哲学：每个操作者都有义务推进全局状态，而不是旁观。

4.3 桶头加锁写入

桶非空且非 MOVED 时进入核心分支——锁桶头节点：

else {
V oldVal = null;
synchronized (f) { // ① 锁粒度 = 单个桶的桶头节点
if (tabAt(tab, i) == f) { // ② double-check：等锁期间桶头可能已被搬走/替换
if (fh >= 0) { // ③ 普通链表桶
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
if (e.hash == hash && ((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val; // ④ 找到同 key → 覆盖
if (!onlyIfAbsent) e.val = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) { // ⑤ 尾插新节点
pred.next = new Node<K,V>(hash, key, value, null);
break;
}
}
}
else if (f instanceof TreeBin) { // ⑥ 红黑树桶：交给树去插（8.3）
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent) p.val = value;
}
}
}
}
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD) treeifyBin(tab, i); // ⑦ 树化判定
if (oldVal != null) return oldVal;
break;
}
}

设计要点逐条说清：

设计点说明

为什么锁桶头而不是锁数组	桶头是桶内链表的「入口」，锁住它 = 锁住整条链的写入口；不同桶的头节点不同 → 互不阻塞；锁对象无需自建，每个 Node 天然可当锁
double-check 的意义	等锁期间可能发生扩容（本桶被搬走并放上 ForwardingNode），醒来后必须确认桶头仍是 f，否则锁的是「旧世界的空头」
链表插入在锁内	链表尾插 + 计数都必须在锁内完成，保证同桶写入串行
覆盖与返回	put 返回旧值；putIfAbsent（onlyIfAbsent=true）则发现存在就跳过——注意它拿到的也是锁，所以是原子的「不存在才写」
TreeBin 分支	树化后桶头是 TreeBin，插入改走树算法，链表计数直接记 2（避免树内计数）

4.4 树化触发

binCount ≥ 8 时调用 treeifyBin，但并不一定真的树化：

private final void treeifyBin(Node<K,V>[] tab, int index) {
Node<K,V> b; int n, sc;
if (tab != null) {
if ((n = tab.length) < MIN_TREEIFY_CAPACITY) // ① 桶数组 < 64
tryPresize(n << 1); // → 先扩容到 2n（稀释冲突）
else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
synchronized (b) { // ② 锁桶头，把链表建成树
if (tabAt(tab, index) == b) {
TreeNode<K,V> hd = null, tl = null;
for (Node<K,V> e = b; e != null; e = e.next) {
TreeNode<K,V> p = new TreeNode<K,V>(e.hash, e.key, e.val, null, null);
if ((p.prev = tl) == null) hd = p; // 先串成双向链表
else tl.next = p;
tl = p;
}
setTabAt(tab, index, new TreeBin<K,V>(hd)); // 桶头换成 TreeBin(-2)
}
}
}
}
}

关键认知：桶数组不足 64 时，hash 冲突再严重也不树化，而是先扩容——因为此时树化的收益（log n 查找）敌不过「桶太少、容量马上要翻倍」的浪费；树化是「扩容也救不了的单桶冲突」的兜底。

4.5 计数与阈值检查

putVal 收尾调用 addCount(1L, binCount)，计数与扩容在此联动（第 5、6 章详述）：

private final void addCount(long x, int check) {
CounterCell[] as; long b, s;
if ((as = counterCells) != null ||
!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
// 竞争激烈 → 走 counterCells 分片计数（6.2）
CounterCell a; long v; int m;
boolean uncontended = true;
if (as == null || (m = as.length – 1) < 0 ||
(a = as[ThreadLocalRandom.getProbe() & m]) == null ||
!(uncontended = U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
fullAddCount(x, uncontended); // 初始化/扩容分片数组
return; // 计数路径在此结束
}
if (check <= 1) return; // 桶链很短，不用检查扩容
s = sumCount();
}
// check ≥ 0 且元素数超阈值 → 扩容（5.1）
if (check >= 0) {
Node<K,V>[] tab, nt; int n, sc;
while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
(n = tab.length) < MAXIMUM_CAPACITY) {
int rs = resizeStamp(n);
if (sc < 0) {
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
break; // 扩容已在进行/已结束，让位
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) // 登记「我来帮忙」
transfer(tab, nt);
}
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2)) // 成为第一个扩容者
transfer(tab, null);
s = sumCount();
}
}
}

4.6 put 全流程决策图

#mermaid-svg-IOXZnQiGl3ClkheL{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-IOXZnQiGl3ClkheL .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-IOXZnQiGl3ClkheL .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-IOXZnQiGl3ClkheL .error-icon{fill:#552222;}#mermaid-svg-IOXZnQiGl3ClkheL .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-IOXZnQiGl3ClkheL .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-IOXZnQiGl3ClkheL .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-IOXZnQiGl3ClkheL .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-IOXZnQiGl3ClkheL .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-IOXZnQiGl3ClkheL .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-IOXZnQiGl3ClkheL .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-IOXZnQiGl3ClkheL .marker{fill:#333333;stroke:#333333;}#mermaid-svg-IOXZnQiGl3ClkheL .marker.cross{stroke:#333333;}#mermaid-svg-IOXZnQiGl3ClkheL svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-IOXZnQiGl3ClkheL p{margin:0;}#mermaid-svg-IOXZnQiGl3ClkheL .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-IOXZnQiGl3ClkheL .cluster-label text{fill:#333;}#mermaid-svg-IOXZnQiGl3ClkheL .cluster-label span{color:#333;}#mermaid-svg-IOXZnQiGl3ClkheL .cluster-label span p{background-color:transparent;}#mermaid-svg-IOXZnQiGl3ClkheL .label text,#mermaid-svg-IOXZnQiGl3ClkheL span{fill:#333;color:#333;}#mermaid-svg-IOXZnQiGl3ClkheL .node rect,#mermaid-svg-IOXZnQiGl3ClkheL .node circle,#mermaid-svg-IOXZnQiGl3ClkheL .node ellipse,#mermaid-svg-IOXZnQiGl3ClkheL .node polygon,#mermaid-svg-IOXZnQiGl3ClkheL .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-IOXZnQiGl3ClkheL .rough-node .label text,#mermaid-svg-IOXZnQiGl3ClkheL .node .label text,#mermaid-svg-IOXZnQiGl3ClkheL .image-shape .label,#mermaid-svg-IOXZnQiGl3ClkheL .icon-shape .label{text-anchor:middle;}#mermaid-svg-IOXZnQiGl3ClkheL .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-IOXZnQiGl3ClkheL .rough-node .label,#mermaid-svg-IOXZnQiGl3ClkheL .node .label,#mermaid-svg-IOXZnQiGl3ClkheL .image-shape .label,#mermaid-svg-IOXZnQiGl3ClkheL .icon-shape .label{text-align:center;}#mermaid-svg-IOXZnQiGl3ClkheL .node.clickable{cursor:pointer;}#mermaid-svg-IOXZnQiGl3ClkheL .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-IOXZnQiGl3ClkheL .arrowheadPath{fill:#333333;}#mermaid-svg-IOXZnQiGl3ClkheL .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-IOXZnQiGl3ClkheL .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-IOXZnQiGl3ClkheL .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-IOXZnQiGl3ClkheL .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-IOXZnQiGl3ClkheL .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-IOXZnQiGl3ClkheL .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-IOXZnQiGl3ClkheL .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-IOXZnQiGl3ClkheL .cluster text{fill:#333;}#mermaid-svg-IOXZnQiGl3ClkheL .cluster span{color:#333;}#mermaid-svg-IOXZnQiGl3ClkheL div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-IOXZnQiGl3ClkheL .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-IOXZnQiGl3ClkheL rect.text{fill:none;stroke-width:0;}#mermaid-svg-IOXZnQiGl3ClkheL .icon-shape,#mermaid-svg-IOXZnQiGl3ClkheL .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-IOXZnQiGl3ClkheL .icon-shape p,#mermaid-svg-IOXZnQiGl3ClkheL .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-IOXZnQiGl3ClkheL .icon-shape .label rect,#mermaid-svg-IOXZnQiGl3ClkheL .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-IOXZnQiGl3ClkheL .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-IOXZnQiGl3ClkheL .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-IOXZnQiGl3ClkheL :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

是

否

是

否

是

成功

失败有人抢先

否

是

否

是

否

否是 TreeBin

是

否

是

否

是

否

put key value

key 或 value 为 null

抛 NullPointerException

spread 扰动哈希定位桶 i

table 未初始化

initTable 抢初始化权

桶 i 为空

CAS 放入新 Node

完成

桶头 hash == MOVED

helpTransfer 协助扩容

synchronized 桶头节点

桶头是普通 Node

遍历链表

找到同 key

覆盖 value

尾部插入

putTreeVal 树内插入或覆盖

记录 binCount

binCount ≥ 8

treeifyBin

桶数组 ≥ 64

先扩容 2n

链表转红黑树

addCount 计数

元素数超阈值

触发或加入扩容

5. 扩容机制 transfer

扩容是 CHM 源码里最复杂的部分，也是面试的深水区。JDK 8 的扩容与 JDK 7 最大的不同：全表扩容 + 多线程认领迁移。

5.1 扩容触发点

触发入口场景

addCount（4.5）	每次 put 后检查元素数 ≥ sizeCtl 阈值
tryPresize	putAll、treeifyBin 遇桶数组 < 64 时主动扩
helpTransfer	写入时遇到 MOVED 桶头，加入正在进行的扩容

扩容目标 nextTable = new Node[n << 1]（容量翻倍，仍是 2 的幂）。

5.2 多线程分工与区间领取

private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
int n = tab.length, stride;
// ① 每个线程最少搬 stride 个桶：容量 / 8 / CPU 核数，下限 16
if ((stride = (n >>> 3) / NCPU) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE;

if (nextTab == null) { // ② 第一个扩容者负责建新表
try {
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
nextTab = nt;
} catch (Throwable ex) { ... }
nextTable = nextTab;
transferIndex = n; // ③ 认领游标从最后一个桶开始
}
int nextn = nextTab.length;

// ④ 主循环：CAS 领取一段区间 [bound, i]，从高到低迁移
while (advance < 0) { ... } // 简化示意
for (int i = 0, bound = 0;;) {
// 领取区间：transferIndex 是全局唯一游标，
// 线程通过 CAS transferIndex -= stride 拿走「从 transferIndex 往前的一段」
...
if (i < 0 || i >= n || i + n >= nextn) { finish = true; break; }
else if ((f = tabAt(tab, i)) == null) {
advance = casTabAt(tab, i, null, fwd); // 空桶直接放 ForwardingNode
}
else if ((fh = f.hash) == MOVED) advance = true; // 别人搬完了
else {
synchronized (f) { ... 迁移单个桶（见 5.3）... }
}
}
}

分工模型（务必理解「游标领取」而不是「均分」）：

transferIndex 初始 = n（旧表桶数）
┌─ 线程 A 认领 [n-16, n) 这批桶 ─┐
transferIndex ──CAS──▶ │
n ──────────────────────────┤ 线程 B 接着认领 [n-32, n-16)
│ 线程 C 认领 [n-48, n-32)
▼
高索引桶 ←───────── 迁移方向 ←───────── 低索引桶

桶数大于 stride × 线程数时每个线程搬一块；桶少时一个线程也能搬完；
速度快/后来的线程发现 transferIndex ≤ 0（没有剩余桶）就退出，再帮 finish；
空桶迁移零成本：直接 CAS 放一个 ForwardingNode 占位，不用加锁。

5.3 桶迁移与高低位拆分

单个桶的迁移是 putVal 的镜像操作：先 synchronized(f) 锁桶头，再决定桶内元素去新表的哪个位置：

synchronized (f) {
if (tabAt(tab, i) == f) {
Node<K,V> ln, hn; // 低位链 / 高位链
if (fh >= 0) { // 普通链表
int runBit = fh & n;
// ① 先找到「最后一段 runBit 相同的子链」，直接整段复用
Node<K,V> lastRun = f;
for (Node<K,V> p = f.next; p != null; p = p.next) {
int b = p.hash & n;
if (b != runBit) { runBit = b; lastRun = p; }
}
if (runBit == 0) { ln = lastRun; hn = null; }
else { hn = lastRun; ln = null; }

// ② 其余节点按 (hash & n) 拆成高低两条链
for (Node<K,V> p = f; p != lastRun; p = p.next) {
int ph = p.hash; K pk = p.key; V pv = p.val;
if ((ph & n) == 0) ln = new Node<K,V>(ph, pk, pv, ln);
else hn = new Node<K,V>(ph, pk, pv, hn);
}
setTabAt(nextTab, i, ln); // ③ 低位链 → 新表原下标 i
setTabAt(nextTab, i + n, hn); // ④ 高位链 → 新表下标 i+n
setTabAt(tab, i, fwd); // ⑤ 旧桶放 ForwardingNode 收工
advance = true;
}
else if (f instanceof TreeBin) {
// 树桶：遍历双向链表同样拆成 lo/hi 两条链，
// 若任一条 ≤ UNTREEIFY_THRESHOLD(6) 则退化成普通 Node 链，
// 否则各自 new TreeBin 保持树结构
...
}
}
}

为什么只看 hash & n 一位就能拆分？因为旧表长度 n 是 2 的幂：

关键认知（扩容数学）：桶下标 = (n-1) & hash。扩容到 2n 后，新下标 = (2n-1) & hash = 原下标或原下标 + n——多出来的是 hash 二进制里的第 log2(n) 位。所以迁移只需按这一位把一条链拆成「低位链 ln」和「高位链 hn」，分别放到新表的 i 与 i+n 两个桶，节点在新表内不再需要重新哈希（这也是 HashMap 同款优化）。

5.4 ForwardingNode 与无锁读

扩容期间旧表的每个已迁移桶里都放一个 ForwardingNode(-1)，它同时承担三个职责：

职责机制

写保护	写线程定位到该桶 → 知道桶已搬走 → helpTransfer 加入迁移，避免数据写进旧桶丢失
读转发	读线程 get 到 MOVED 桶 → 顺着 ForwardingNode 里保存的 nextTable 引用去新表找（见 7.1）
迁移进度	桶逐个被替换为 ForwardingNode，等于可并行的迁移进度条

所有桶搬完后的收尾（最后一个完成的线程）：

if (finish) {
nextTable = null; // 新表转正
table = nextTab;
sizeCtl = (n << 1) – (n >>> 1); // sizeCtl = 新容量 2n 的 0.75 = 1.5n
return;
}

关键认知：扩容期间读线程永不阻塞——要么读旧桶（没搬走），要么经 ForwardingNode 转发到新表（搬走了），新表内部元素的 next 引用链也是完整的；最多看到「新旧交替瞬间的中间状态」，这就是弱一致性。代价是：扩容期间 size() 等统计是近似值。

6. 计数机制

6.1 CounterCell 与伪共享

JDK 7 的 size() 要把各段 count 加起来，竞争激烈时还不准；JDK 8 借鉴 LongAdder 思路：一个全局 baseCount + 一组分片 CounterCell[]，写多线程时各自 CAS 自己的分片，把计数器热点打散。

// 每个分片一个 long，@sun.misc.Contended 注解让每个 Cell 独占一个缓存行（128 字节填充）
@sun.misc.Contended
static final class CounterCell {
volatile long value;
CounterCell(long x) { value = x; }
}

关键认知：多个线程频繁写不同 Cell 时，若它们落在同一 CPU 缓存行（64 字节），会互相使对方缓存失效（伪共享 False Sharing），性能断崖。@Contended 注解强制 Cell 之间间隔一个缓存行大小，从物理上隔离热点。

6.2 addCount 与 fullAddCount

计数主路径（源码逻辑见 4.5 节代码）：

// addCount(x, check) 的逻辑：
// ① counterCells 未初始化且 baseCount CAS 成功 → 完事（无竞争快路径）
// ② 否则按线程探针（ThreadLocalRandom.getProbe）哈希到某个 Cell，CAS 该 Cell
// ③ 该 Cell 也 CAS 失败 → fullAddCount：扩容 Cell 数组（翻倍）或换个 Cell 重试

// fullAddCount 核心（节选语义）：初始化 counterCells 用 cellsBusy 自旋锁保护
private final void fullAddCount(long x, boolean wasUncontended) {
int h;
if ((h = ThreadLocalRandom.getProbe()) == 0) { // 线程探针 = 随机数种子
ThreadLocalRandom.localInit();
h = ThreadLocalRandom.getProbe();
wasUncontended = true;
}
boolean collide = false;
for (;;) {
CounterCell[] as; CounterCell a; int n; long v;
if ((as = counterCells) != null && (n = as.length) > 0) {
// 随机选中一个 Cell，CAS 累加；失败则考虑扩容数组或重哈希
...
else if (cellsBusy == 0 && U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
// 拿到 cellsBusy 锁 → counterCells 翻倍扩容
...
}
}
else if (cellsBusy == 0 && U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
// counterCells 为 null：初始化 2 个 Cell
}
...
}
}

6.3 size 与 mappingCount

public int size() { long n = sumCount(); return (n < 0L) ? 0 : (n > Integer.MAX_VALUE) ? Integer.MAX_VALUE : (int)n; }

public long mappingCount() { // JDK8 新增：size 溢出风险的正确打开方式
long n = sumCount();
return (n < 0L) ? 0L : n; // 需要精确值请配 sizeCtl/锁场景自行取舍
}

final long sumCount() {
CounterCell[] as = counterCells; CounterCell a;
long sum = baseCount; // 基数 + 所有分片
if (as != null) {
for (int i = 0; i < as.length; ++i) {
if ((a = as[i]) != null) sum += a.value;
}
}
return sum; // ⚠️ 遍历期间并发写仍在发生 → 弱一致近似值
}

一句话概括：size() 不做任何加锁与快照，只是「baseCount + 各分片」快速求和，返回的是某一瞬间的近似值；元素数可能超 int 范围时请用 mappingCount()（返回 long）。JDK 文档明确说了「用于监控与统计，不用于精确决策」。

7. 读操作与遍历

7.1 get 为什么可以无锁

public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
int h = spread(key.hashCode());
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n – 1) & h)) != null) { // ① volatile 读桶头
if ((eh = e.hash) == h) { // ② 桶头就命中
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
else if (eh < 0) // ③ hash<0：特殊节点
return (p = e.find(h, key)) != null ? p.val : null;
while ((e = e.next) != null) { // ④ 链表顺序找
if (e.hash == h && ((ek = e.key) == key ||
(ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}

无锁读的安全性来自三个层次：

层次保证

tabAt volatile 读	桶数组元素读取一定看到「最近的可见状态」，扩容换表后读到的是新表引用
链表节点的 next 是 volatile	迁移中的链表在锁内被「复制」到新表而非原地改动（5.3 用 new Node 重建），旧链一旦被读线程引用就不会被改写——不变性：已发布的链表只读不写
特殊节点的 find 多态	ForwardingNode → 转发新表；TreeBin → 树查找或退化为链表扫描（8.2）

关键认知：扩容迁移是「复制式」而非「移动式」——旧桶的节点链在迁移时被新建成两条链放进新表，旧链表结构从不被原地修改（除了桶头换成 ForwardingNode 这一步 CAS）。所以读线程无论拿到旧还是新结构都安全，这就是无锁读的根基。

7.2 remove 与 replace

public V remove(Object key) { return replaceNode(key, null, null); }

final V replaceNode(Object key, V value, Object cv) {
int hash = spread(key.hashCode());
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || ... || (f = tabAt(tab, i = (n–1)&hash)) == null)
break; // 桶不存在 → 无需删
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f); // 扩容中先帮忙
else {
boolean validated = false; boolean deleted = false;
synchronized (f) { // 同样锁桶头
if (tabAt(tab, i) == f) {
validated = true;
if (fh >= 0) { // 链表删除：prev.next = e.next
...
}
else if (f instanceof TreeBin) {
// 树删除：removeTreeNode（会维护双向链表 + 红黑树平衡），
// 桶内若只剩少量节点不主动转链表（等扩容时再退化）
}
}
}
}
}
// 删除成功 → addCount(-1L, -1) 回退计数
}

replace(key, oldValue, newValue) 走同一个 replaceNode(key, newValue, cv=oldValue) 重载：在锁内校验旧值，实现原子的条件替换。remove/replace 与 put 共用同一套桶锁，所以「读-改-写」组合（如 containsKey 后 put）之间没有原子性——需要原子复合请用 7.4 的 compute 系或 putIfAbsent。

7.3 弱一致性迭代器

JDK 8 的迭代器（KeyIterator/ValueIterator/EntryIterator）基于 Traverser 设计，遍历规则：

// 语义：逐桶前进；遇到 ForwardingNode 则顺着 nextTable 继续找该桶在新表的位置
// 特点：全程无锁、不抛 ConcurrentModificationException、遍历期间的新增/删除"部分可见"
static final class Traverser<K,V> {
Node<K,V>[] tab; // 当前正在读的表
...
Node<K,V> advance() {
// 桶内走完 → 下一个桶；桶头是 ForwardingNode → 进入 nextTable 对应桶继续
}
}

弱一致性的具体表现：

场景遍历结果

遍历开始后其他线程 put 新 key	新元素可能出现在「还没遍历到的桶」，会被看到；已遍历过的桶则看不到
遍历期间删除元素	已被迭代器持引用的旧节点仍能读到（不抛异常）
遍历期间扩容	迭代器自动追到新表继续；可能读到同一 key 的新旧两个值（旧桶节点被持有引用时）

一句话概括：CHM 迭代器是「无锁 + 尽力而为」的快照，迭代期间容器可写、不抛 CME，但不保证看到迭代开始后的全部变化——这正是为了性能付出的语义代价（适合统计/拷贝/转移等批量操作）。

7.4 复合操作 compute 系列

computeIfAbsent / compute / merge 都拿到桶锁后执行，保证原子性；其中 computeIfAbsent 需要占位节点防止递归计算：

public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
...
for (Node<K,V>[] tab = table;;) {
...
else if (fh == RESERVED) // 槽位被本线程自己占着？
throw new IllegalStateException("Recursive update"); // JDK9+：递归检测
...
// 没找到 → synchronized(f) 内在桶尾插入一个 ReservationNode(RESERVED) 占位
// 释放锁后调用 mappingFunction.apply(key) 计算（慢操作不在锁内做！）
// 算完带着结果再回来把占位节点替换成真实节点；算出来 null 则删除占位
}
}

两个设计细节很值钱：

计算函数在锁外执行：占位后先释放锁再调 mappingFunction，避免把用户代码锁在桶上（若在锁内计算，用户函数里再碰这个 CHM 就直接死锁）；

递归检测：若用户函数内部又对同一个 key 调 computeIfAbsent，会发现占位节点并抛 IllegalStateException("Recursive update")——⚠️ 这个保护是 JDK 9+ 才补全的（JDK-8160404/8180352）：JDK 8 的 computeIfAbsent 遇到递归更新会死循环或内存溢出，经典线上事故（如 Spring 早期某些嵌套缓存加载）。线上跑 JDK 8 的同学留意：computeIfAbsent 的回调里不要再查同一个 key。

8. 树化与 TreeBin

8.1 8 与 6 两个阈值

阈值值触发方向

TREEIFY_THRESHOLD	8	桶内链表 ≥ 8 且桶数组 ≥ 64 → 链表转红黑树
UNTREEIFY_THRESHOLD	6	扩容拆桶后，树桶内节点 ≤ 6 → 红黑树退化链表
MIN_TREEIFY_CAPACITY	64	桶数组长度不足时先扩容不树化

为什么是 8？官方注释给了依据——泊松分布：在理想随机哈希下，单个桶内节点数 k 的概率约为 (0.5)^k / k!（负载因子 0.75 时到达次数 λ≈0.5）：

桶内节点数 k概率

8	约 0.00000006（千万分之六）
10	约 1.8e-13

链表到树要到 8 才触发，说明这是「哈希已经严重失守（或有人恶意构造冲突）」的异常信号；反过来退化阈值取 6 而非 8，是为了避免元素数在 7 附近震荡时链表/树反复横跳（8 与 6 之间留了 1 的滞回带）。这两个数字同时暗示了：正常数据下红黑树几乎不会出现，树化主要是「反哈希碰撞攻击」的防御（如让 HashMap 退化成链表做 DoS）。

8.2 TreeBin 的读写锁思路

TreeBin 本身是个 Node（hash=-2），它作为桶头被 put/remove 的 synchronized 锁住（写互斥已由桶锁保证）。但 get 是无锁的，它怎么安全地并发读树？答案是 TreeBin 内部的 lockState 简化读写锁：

static final int WRITER = 1; // bit0：写者锁（持有者 = 树结构调整方）
static final int WAITER = 2; // bit1：有写者在等锁
static final int READER = 4; // bit2+：读者计数（每次 +4）

// 树查找（get 路径）——对读者友好
final Node<K,V> find(int h, Object k) {
...
for (Node<K,V> e = first; e != null; ) {
int s; K ek;
if (((s = lockState) & (WAITER | WRITER)) != 0) {
// ① 有写者在场 → 直接沿 first 双向链表线性扫描（绝不阻塞读）
}
else if (U.compareAndSwapInt(this, LOCKSTATE, s, s + READER)) {
// ② 无写者 → CAS 把 reader 计数 +1，然后放心走红黑树查找
TreeNode<K,V> r, p; ... return p; // finally 中 CAS 回退 reader 计数
}
// CAS 失败（与写者竞争瞬间）→ 退化为链表扫描
}
}

操作锁读是否阻塞

桶头 put/remove（先于树操作）	synchronized(TreeBin)	写写互斥
树查找 get	lockState 读者计数（CAS）	不阻塞，最坏线性扫描
树结构调整（删除节点后的平衡）	lockRoot()：CAS lockState → WRITER	读线程不退让就置 WAITER 标记自旋/park 等

树维护两个结构：红黑树（查） + first 串起的双向链表（写者在场时的兜底查 + 扩容拆桶的遍历依据）——双结构是 TreeBin 优雅并发读的基础。

关键认知：JDK 8 的 CHM 树化后读写并发策略是「读者绝不等待写者，写者尽量不打扰读者」：树内查找走 CAS 读者计数；一有写者（删除后平衡树）在读，新读者直接降级走链表。这也是 get 在树桶上依旧无锁的原因。

8.3 树与链表的双向转换

链表 ──(桶内节点≥8 且 table≥64, 锁桶头)──▶ TreeBin(双向链表 → 平衡成红黑树)
TreeBin ──(扩容拆桶后 lo/hi 任一条 ≤6)──▶ 普通 Node 链表
TreeBin ──(桶内节点仍多)─────────────────▶ 两个新 TreeBin 各走一边

链表→树：4.4 的 treeifyBin：先在锁内把 Node 链改建成 TreeNode 双向链表，再交给 TreeBin 构造时做红黑树平衡（balanceInsertion）；
树→链表：只发生在扩容拆桶（5.3）时——拆出的高低两条链若 ≤6 节点，直接退化；桶内删除（removeTreeNode）不主动退化，避免「删一个就重构」；
TreeNode 继承 Node 且持 prev 指针，拆桶时可以像链表一样遍历拆分，无需在树上做 split 算法。

9. 关键类关系图

#mermaid-svg-s4IneM1vkb6mLYx8{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-s4IneM1vkb6mLYx8 .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-s4IneM1vkb6mLYx8 .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-s4IneM1vkb6mLYx8 .error-icon{fill:#552222;}#mermaid-svg-s4IneM1vkb6mLYx8 .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-s4IneM1vkb6mLYx8 .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-s4IneM1vkb6mLYx8 .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-s4IneM1vkb6mLYx8 .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-s4IneM1vkb6mLYx8 .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-s4IneM1vkb6mLYx8 .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-s4IneM1vkb6mLYx8 .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-s4IneM1vkb6mLYx8 .marker{fill:#333333;stroke:#333333;}#mermaid-svg-s4IneM1vkb6mLYx8 .marker.cross{stroke:#333333;}#mermaid-svg-s4IneM1vkb6mLYx8 svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-s4IneM1vkb6mLYx8 p{margin:0;}#mermaid-svg-s4IneM1vkb6mLYx8 g.classGroup text{fill:#9370DB;stroke:none;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:10px;}#mermaid-svg-s4IneM1vkb6mLYx8 g.classGroup text .title{font-weight:bolder;}#mermaid-svg-s4IneM1vkb6mLYx8 .cluster-label text{fill:#333;}#mermaid-svg-s4IneM1vkb6mLYx8 .cluster-label span{color:#333;}#mermaid-svg-s4IneM1vkb6mLYx8 .cluster-label span p{background-color:transparent;}#mermaid-svg-s4IneM1vkb6mLYx8 .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-s4IneM1vkb6mLYx8 .cluster text{fill:#333;}#mermaid-svg-s4IneM1vkb6mLYx8 .cluster span{color:#333;}#mermaid-svg-s4IneM1vkb6mLYx8 .nodeLabel,#mermaid-svg-s4IneM1vkb6mLYx8 .edgeLabel{color:#131300;}#mermaid-svg-s4IneM1vkb6mLYx8 .edgeLabel .label rect{fill:#ECECFF;}#mermaid-svg-s4IneM1vkb6mLYx8 .label text{fill:#131300;}#mermaid-svg-s4IneM1vkb6mLYx8 .labelBkg{background:#ECECFF;}#mermaid-svg-s4IneM1vkb6mLYx8 .edgeLabel .label span{background:#ECECFF;}#mermaid-svg-s4IneM1vkb6mLYx8 .classTitle{font-weight:bolder;}#mermaid-svg-s4IneM1vkb6mLYx8 .node rect,#mermaid-svg-s4IneM1vkb6mLYx8 .node circle,#mermaid-svg-s4IneM1vkb6mLYx8 .node ellipse,#mermaid-svg-s4IneM1vkb6mLYx8 .node polygon,#mermaid-svg-s4IneM1vkb6mLYx8 .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-s4IneM1vkb6mLYx8 .divider{stroke:#9370DB;stroke-width:1;}#mermaid-svg-s4IneM1vkb6mLYx8 g.clickable{cursor:pointer;}#mermaid-svg-s4IneM1vkb6mLYx8 g.classGroup rect{fill:#ECECFF;stroke:#9370DB;}#mermaid-svg-s4IneM1vkb6mLYx8 g.classGroup line{stroke:#9370DB;stroke-width:1;}#mermaid-svg-s4IneM1vkb6mLYx8 .classLabel .box{stroke:none;stroke-width:0;fill:#ECECFF;opacity:0.5;}#mermaid-svg-s4IneM1vkb6mLYx8 .classLabel .label{fill:#9370DB;font-size:10px;}#mermaid-svg-s4IneM1vkb6mLYx8 .relation{stroke:#333333;stroke-width:1;fill:none;}#mermaid-svg-s4IneM1vkb6mLYx8 .dashed-line{stroke-dasharray:3;}#mermaid-svg-s4IneM1vkb6mLYx8 .dotted-line{stroke-dasharray:1 2;}#mermaid-svg-s4IneM1vkb6mLYx8 #compositionStart,#mermaid-svg-s4IneM1vkb6mLYx8 .composition{fill:#333333!important;stroke:#333333!important;stroke-width:1;}#mermaid-svg-s4IneM1vkb6mLYx8 #compositionEnd,#mermaid-svg-s4IneM1vkb6mLYx8 .composition{fill:#333333!important;stroke:#333333!important;stroke-width:1;}#mermaid-svg-s4IneM1vkb6mLYx8 #dependencyStart,#mermaid-svg-s4IneM1vkb6mLYx8 .dependency{fill:#333333!important;stroke:#333333!important;stroke-width:1;}#mermaid-svg-s4IneM1vkb6mLYx8 #dependencyStart,#mermaid-svg-s4IneM1vkb6mLYx8 .dependency{fill:#333333!important;stroke:#333333!important;stroke-width:1;}#mermaid-svg-s4IneM1vkb6mLYx8 #extensionStart,#mermaid-svg-s4IneM1vkb6mLYx8 .extension{fill:transparent!important;stroke:#333333!important;stroke-width:1;}#mermaid-svg-s4IneM1vkb6mLYx8 #extensionEnd,#mermaid-svg-s4IneM1vkb6mLYx8 .extension{fill:transparent!important;stroke:#333333!important;stroke-width:1;}#mermaid-svg-s4IneM1vkb6mLYx8 #aggregationStart,#mermaid-svg-s4IneM1vkb6mLYx8 .aggregation{fill:transparent!important;stroke:#333333!important;stroke-width:1;}#mermaid-svg-s4IneM1vkb6mLYx8 #aggregationEnd,#mermaid-svg-s4IneM1vkb6mLYx8 .aggregation{fill:transparent!important;stroke:#333333!important;stroke-width:1;}#mermaid-svg-s4IneM1vkb6mLYx8 #lollipopStart,#mermaid-svg-s4IneM1vkb6mLYx8 .lollipop{fill:#ECECFF!important;stroke:#333333!important;stroke-width:1;}#mermaid-svg-s4IneM1vkb6mLYx8 #lollipopEnd,#mermaid-svg-s4IneM1vkb6mLYx8 .lollipop{fill:#ECECFF!important;stroke:#333333!important;stroke-width:1;}#mermaid-svg-s4IneM1vkb6mLYx8 .edgeTerminals{font-size:11px;line-height:initial;}#mermaid-svg-s4IneM1vkb6mLYx8 .classTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-s4IneM1vkb6mLYx8 .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-s4IneM1vkb6mLYx8 .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-s4IneM1vkb6mLYx8 :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

继承

table 桶数组元素

桶内树容器 hash=-2

分片计数

红黑树根与链表

ConcurrentHashMap

-table Node[]

-nextTable Node[]

-baseCount long

-sizeCtl int

-transferIndex int

-counterCells CounterCell[]

+put(key, value)

+get(key)

+remove(key)

+size()

+putIfAbsent(…)

Node

#hash int

#key K

#val V volatile

#next Node volatile

TreeNode

-parent TreeNode

-left TreeNode

-right TreeNode

-prev TreeNode 双向链表

-red boolean

TreeBin

-root TreeNode

-first TreeNode 链头

-lockState int 读写锁

+putTreeVal(…)

+find(h, k)

ForwardingNode

-nextTable Node[]

+find(h, k) : 转发到新表

ReservationNode

占位 computeIfAbsent

CounterCell

-value long Contended

Map

读图要点：所有「特殊桶头」都是 Node 的子类，table[i] 这一格子里永远放 Node——put/get/remove 拿到桶头后先看 hash 符号与类型再分派，这是理解整份源码的「总开关」；CounterCell 与主表无继承关系，只服务于计数。

10. 可运行示例

10.1 并发读写与遍历 demo

演示多线程写入、复合操作与弱一致遍历（JDK 8+，直接 javac/java 可运行）：

// ChmConcurrentDemo.java
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.atomic.AtomicLong;

public class ChmConcurrentDemo {
public static void main(String[] args) throws Exception {
final ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();
final int threads = 8, each = 10_000;
CountDownLatch latch = new CountDownLatch(threads);

// 8 个线程各写各的 key 区间：几乎无桶冲突 → 大部分写入是空桶 CAS，零加锁
for (int t = 0; t < threads; t++) {
final int id = t;
new Thread(() -> {
for (int i = 0; i < each; i++) map.put("k-" + id + "-" + i, i);
latch.countDown();
}, "writer-" + t).start();
}
latch.await();
System.out.println("写入完成后 size = " + map.size()); // 80000
System.out.println("mappingCount = " + map.mappingCount());

// 读：无锁；key 不存在返回 null（CHM 本身不允许存 null，无二义性）
System.out.println("get 不存在的 key = " + map.get("nope"));

// putIfAbsent：已存在则返回旧值不覆盖（原子的「不存在才写」）
Integer old = map.putIfAbsent("k-0-1", –1);
System.out.println("putIfAbsent 返回旧值 = " + old); // 1

// computeIfAbsent：mappingFunction 只对缺席的 key 执行一次
map.computeIfAbsent("hot-key", k -> k.length() * 100);
map.computeIfAbsent("hot-key", k -> k.length() * 100);
System.out.println("computeIfAbsent 结果 = " + map.get("hot-key")); // 700

// 弱一致性迭代：遍历期间另一个线程持续写入 → 不抛 CME
final AtomicLong seen = new AtomicLong();
Thread mutator = new Thread(() -> {
for (int i = 0; i < 100_000; i++) map.put("mut-" + i, i);
});
mutator.start();
for (Map.Entry<String, Integer> e : map.entrySet()) seen.incrementAndGet();
mutator.join();
System.out.println("迭代期间看到的条目 >= " + seen.get()); // 不一定 80000+，不抛异常即可
System.out.println("迭代结束后 size = " + map.size());
}
}

$ javac ChmConcurrentDemo.java && java ChmConcurrentDemo
写入完成后 size = 80000
mappingCount = 80000
get 不存在的 key = null
putIfAbsent 返回旧值 = 1
computeIfAbsent 结果 = 700
迭代期间看到的条目 >= 80000 # 数值不确定（弱一致），但不抛 ConcurrentModificationException
迭代结束后 size = 180000

10.2 简易缓存 demo

用 CHM 实现线程安全、惰性过期、并发加载只执行一次的本地缓存（模拟常见中间件缓存层写法）：

// SimpleCache.java
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
import java.util.function.Function;

public class SimpleCache {
private static class Entry {
final Object value;
final long expireAt;
Entry(Object value, long ttlMillis) {
this.value = value;
this.expireAt = System.currentTimeMillis() + ttlMillis;
}
boolean expired() { return System.currentTimeMillis() > expireAt; }
}

private final Map<String, Entry> store = new ConcurrentHashMap<>();

/** 读取：无锁 get + 惰性过期（过期不主动清理，读到才丢弃） */
public Object get(String key) {
Entry e = store.get(key);
return (e == null || e.expired()) ? null : e.value;
}

/** 写入：带 TTL 的 put */
public void put(String key, Object value, long ttlMillis) {
store.put(key, new Entry(value, ttlMillis));
}

/** 缓存加载器：多线程同时 miss 同一 key 时，loader 只执行一次（computeIfAbsent 语义） */
public Object getOrLoad(String key, long ttlMillis, Function<String, Object> loader) {
Object hit = get(key);
if (hit != null) return hit;
// 返回 null 表示不缓存该 key；mappingFunction 在桶锁保护下只执行一次
Entry loaded = store.computeIfAbsent(key,
k -> { Object v = loader.apply(k);
return v == null ? null : new Entry(v, ttlMillis); });
return loaded == null ? null : loaded.value;
}

public static void main(String[] args) throws Exception {
SimpleCache cache = new SimpleCache();
Thread[] ts = new Thread[10];
for (int t = 0; t < ts.length; t++) {
final int id = t;
ts[t] = new Thread(() -> {
// 10 个线程同时打同一个 key：期望 [loader] 只打印一次
Object v = cache.getOrLoad("user:10086", 5_000,
k -> { System.out.println(" [loader] 加载 " + k);
return "value-of-" + k; });
System.out.println("线程 " + id + " 拿到 " + v);
});
ts[t].start();
}
for (Thread t : ts) t.join();

System.out.println("TTL 内直接命中: " + cache.get("user:10086"));
Thread.sleep(5_200); // 等 TTL(5s) 过期
System.out.println("TTL 过期后再读: " + cache.get("user:10086")); // null
}
}

$ javac SimpleCache.java && java SimpleCache
[loader] 加载 user:10086 # 只出现一次 → 加载逻辑只执行了一次
线程 0 拿到 value-of-user:10086
线程 1 拿到 value-of-user:10086
...（10 行，值相同）
TTL 内直接命中: value-of-user:10086
TTL 过期后再读: null

⚠️ 扩展思考：上述 getOrLoad 存在「读到了刚过期但尚未被替换的 Entry」的极小窗口（先 get 后 computeIfAbsent 不是原子操作）——生产级缓存请用 compute 系列在锁内完成过期判断，或用 Caffeine/Guava Cache 这种成熟实现。

11. 横向对比总表

维度HashtableCollections.synchronizedMapCHM JDK 7CHM JDK 8+HashMap（线程私有）

锁粒度	整表	整表	16 分段	单桶（冲突时）	无
无冲突写入	全程锁	全程锁	锁分段	一次 CAS	CAS 都不用（单线程）
读	锁	锁	无锁（volatile）	无锁	无锁
扩容	全表锁后搬	全表锁后搬	段内搬	多线程协作搬	单线程搬
计数	size 变量	—	段 count 和	CounterCell 分片	modCount+size
null	不允许	取决于包装的 Map	不允许	不允许	key/value 均可
迭代	fail-fast	fail-fast	弱一致	弱一致	fail-fast
适用	遗留代码	快速小规模包装	已被 8 取代	默认选择	无线程共享

决策建议：

无并发共享 → HashMap；

多线程共享、需要并发读写 → ConcurrentHashMap（JDK 8+）；

需要有序/范围查询 → ConcurrentSkipListMap；

Hashtable / synchronizedMap 只出现在「无法改代码」的遗留场景。

12. FAQ 与扩展点

Q1：为什么 JDK 8 放弃分段锁，改用 CAS + synchronized 锁桶头？

见 1.3 的三条原因，浓缩为一句：分段锁把并发度锁死在 16，且无论冲突与否写入都要碰锁；桶锁粒度细到「桶数」、无冲突写入退化为 CAS、读完全无锁，加上 JDK 6 后 synchronized 已被 JVM 深度优化，官方注释直言新方案的吞吐与内存占用都优于分段锁。

Q2：CHM 为什么不允许 null key / null value？HashMap 却允许？

get 返回 null 有两种可能：key 不存在、或映射到 null。单线程 HashMap 可以再调一次 containsKey 消除歧义；而 CHM 要在并发下维持这个歧义判断，会让无锁读的语义变得复杂且易误导调用方（也影响 get/putIfAbsent/compute 等复合操作的原子语义），因此设计上直接拒绝 null（put 即抛 NPE）。这是 Doug Lea 在源码注释里点明的刻意取舍。

Q3：桶数组长度为什么必须保持 2 的幂？

两处依赖：① 下标计算用位运算 (n-1) & hash 替代取模；② 扩容时 hash & n 一位即可判定节点去新表的 i 还是 i+n（5.3），整条链高低拆分、无需重哈希。

Q4：sizeCtl 负数两种含义如何区分？

-1 专指「初始化中」（initTable 的 CAS 目标）；小于 -1 表示「扩容中」，且 -(1 + 线程数) 编码了参与者数量——首个扩容线程把 sizeCtl CAS 成 (resizeStamp << 16) + 2（即 -(1+1)），后续每加入一个线程 +1。观察 jstack 或调 sizeCtl（反射）可确认是否在扩容。

Q5：扩容期间正在读的线程安全吗？会不会读到丢失或半截数据？

安全。迁移是「复制式」的：桶内链表在桶锁保护下被复制重建进新表，旧链表除桶头被 CAS 换成 ForwardingNode 外不再被修改；读线程要么读旧桶残留链（完整），要么经 ForwardingNode 转发到新表（完整）。两个结构各自一致，读线程只是可能看到「搬走前/后」的其中一个，绝不会看到撕裂的数据——代价是弱一致性。

Q6：树化阈值为什么是 8？退化为什么是 6？

泊松分布下理想哈希的桶内节点数 ≥8 的概率约千万分之六，达到 8 说明哈希已严重退化（或遭恶意冲突攻击），此时树化作为兜底；退化取 6 是为了在 7 附近留滞回带，避免频繁「树化↔退化」抖动。MIN_TREEIFY_CAPACITY=64 保证桶足够多时树化才有意义。

Q7：size() 返回的值精确吗？

不保证。sumCount() 不加锁地累加 baseCount + 各 CounterCell，统计瞬间并发写仍在进行，返回值是近似值；文档定位为监控统计用途。需要精确容量（如做淘汰、配额判断）应在业务层自行同步或接受近似。

Q8：JDK 8 的 computeIfAbsent 有什么著名大坑？

回调内递归更新同一个 key 会死循环（链表越插越长 / 或行为异常），该问题在 JDK 9+ 通过 ReservationNode 占位检测修复——递归更新会抛 IllegalStateException("Recursive update")。JDK 8 上线的系统要警惕：mappingFunction 里若触发了对同一 CHM 同 key 的读写（如回调里查缓存、Spring 早期嵌套 bean 加载），可能直接打满 CPU。规避：回调内绝不访问同一个 key。

Q9：CHM 的迭代器与 HashMap 的有什么本质区别？

HashMap 迭代器是 fail-fast：遍历期间结构性修改立刻抛 ConcurrentModificationException（靠 modCount 检测）；CHM 迭代器是弱一致：无锁、不抛异常、尽力看到遍历开始时的快照并容忍并发修改（7.3）。批量拷贝/转移/聚合请用 CHM 迭代器或 forEach，别担心遍历中被改。

Q10：JDK 9~17 里 CHM 结构有变化吗？

核心结构（桶数组 + Node + TreeBin + 扩容协作 + CounterCell）自 JDK 8 定型后保持稳定；后续主要是行为修复与增强：computeIfAbsent 递归检测（JDK 9）、remove 相关边缘并发修复、文档与 Javadoc 完善等。分析 JDK 8 源码的结论在当代版本依然成立——这也是它值得精读的原因。

13. 参考资料与延伸

OpenJDK JDK 8 ConcurrentHashMap.java（本文源码依据，源码里 Doug Lea 的长注释值得逐行读）
OpenJDK JDK 8 LongAdder.java（CounterCell 计数的思想源头）
OpenJDK JDK 7 ConcurrentHashMap.java（分段锁实现对照）
ConcurrentHashMap (Java SE 8 官方文档)
《Java 并发编程的艺术》方腾飞等：第 6 章 ConcurrentHashMap 详解
《深入理解 Java 虚拟机》周志明：锁优化与并发电面背景知识

目录