Lesson 04 · 集合框架源码

ConcurrentHashMap 演进：JDK7 分段锁 → JDK8 CAS+synchronized

高级·⭐ 必问·#集合·#并发·#核心

1.2 ConcurrentHashMap — 分段锁到 CAS + synchronized 的演进

📖核心概念

ConcurrentHashMap 是 Java 中最高性能的线程安全 Map 实现，在并发场景下远优于 Hashtable 和 Collections.synchronizedMap
Java 1.7 采用 分段锁（Segment） 机制：将数据分为多个 Segment，每个 Segment 继承自 ReentrantLock，锁粒度为 segment 级别
Java 1.8 采用 CAS + synchronized 机制：锁粒度缩小到 链表/红黑树的节点（bin）级别，并发度大幅提升
核心数据结构：数组 + 链表 + 红黑树（与 HashMap 1.8 结构一致），但增加了并发控制

🎯 为什么需要 ConcurrentHashMap？

HashMap 线程不安全（put 时可能死循环/数据覆盖），Hashtable 全表锁性能差，Collections.synchronizedMap 也是全表锁。ConcurrentHashMap 在保持线程安全的同时，将并发度提升到接近 HashMap 的性能水平。

🔒Java 1.7 分段锁机制

Segment：继承自 ReentrantLock，是锁的粒度单位。默认 16 个 Segment，通过 hash 值定位到具体 Segment 加锁
HashEntry：Segment 内部存储数据的链表节点，key/value/volatile next，其中 next 使用 volatile 保证可见性
put 流程：先通过 hash 定位到 Segment → 对 Segment 加锁（synchronized）→ 在 segment 内部的 table 数组中定位 bin → 链表插入
get 流程：无需加锁，直接通过 volatile 的 next 字段遍历链表（HashEntry.value 是 volatile 的）
扩容：每个 Segment 独立扩容，不会锁全表；扩容时不会迁移其他 Segment 的数据

// 1.7 内部结构示意
ConcurrentHashMap
├── Segment[16]  ← 默认16个段，每个段可独立加锁
│   ├── HashEntry[16]  ← 每个段内部的table数组
│   │   └── HashEntry(key, value, volatile next)  ← 链表节点
│   └── ...
│
Segment 继承 ReentrantLock，加锁粒度 = 1个 Segment ≈ 1/16 的数据

⚡Java 1.8 CAS + synchronized

锁粒度革命：从 Segment 级别缩小到 bin（链表头节点/红黑树根节点）级别，理论上可达 N 倍并发（N = 数组长度）
CAS 保证原子性：put 时先用 CAS 尝试插入表头节点（Unsafe.putOrderedObject），成功则直接返回，无需加锁
synchronized 保证安全：当 bin 非空时，用 synchronized 锁定 bin 的第一个节点（f），只锁这一个节点，其他线程可并行操作其他 bin
volatile 保证可见性：Node 的 val 和 next 都是 volatile，确保多线程下的可见性
treeifyBin：链表长度 ≥ 8 且数组长度 ≥ 64 时，将链表转为红黑树，查找从 O(n) 降为 O(log n)

// 1.8 put 核心流程
put(key, value):
  1. hash(key) 计算 hash 值
  2. 用 CAS 尝试初始化 table
  3. 定位 bin 位置: (n - 1) & hash
  4. 如果 bin 为空：CAS 插入新节点（无锁操作！）
  5. 如果 bin 不为空：
     a. 如果 f.hash == MOVED (-1) → 说明正在扩容，协助扩容
     b. synchronized(f) 锁定头节点
     c. 如果是链表：遍历插入/更新
     d. 如果是红黑树：treePut
  6. sizeAddCheck() 检查是否需要树化/扩容

// 扩容流程（支持并发扩容）
transfer():
  1. 创建 newTable (2倍大小)
  2. 用 ForwardingNode 占位 → 指示其他线程此位置正在扩容
  3. 多线程协作扩容：每个线程处理一部分 bin
  4. 完成后更新 table 引用

⚠️ 扩容时的并发处理

1.8 支持多线程并发扩容！当线程 A 正在扩容时，线程 B 来 put 数据，发现目标位置被 ForwardingNode 占位（hash == -1），会先帮忙扩容，扩容完再执行自己的 put。这种"协助扩容"机制大幅缩短了扩容时间窗口。

⚖️对比分析：1.7 vs 1.8 vs Hashtable vs synchronizedMap

特性	Hashtable	synchronizedMap	1.7 Segment	1.8 CAS+synchronized
锁粒度	全表锁	全表锁	Segment 级别（~1/16）	bin 级别（~1/N）
get 是否加锁	是	是	否（volatile）	否（volatile）
并发度	1	1	16	理论 N（数组长度）
扩容	全表重 hash	全表重 hash	Segment 独立扩容	多线程并发扩容
数据结构	数组+链表	数组+链表	数组+链表	数组+链表+红黑树
支持 null	不支持	不支持	不支持	不支持

🔬底层原理深度

size() 的精确性：1.7 中 size 累加每个 Segment 的 count；1.8 中 size 通过 CAS 累加。Java 8u40 引入 sumCount() 通过 LongAdder 风格的累加器实现精确 size
size() 的语义：返回的是"近似"大小。在并发环境下，精确计数代价极高。size() 返回的是最近一次成功更新操作后的值，如果有其他并发修改，可能略小于实际值
forwardingNode：扩容时的占位节点，hash == -1，用于通知其他线程"这个位置正在扩容，请协助"。它的 nextTable 指向新数组
treeifyBin 阈值：链表长度 ≥ 8 且数组长度 ≥ 64 才转红黑树。如果数组长度 < 64，优先扩容而非树化，因为扩容能更有效地降低碰撞率
spread(hash) 函数：对 key 的 hashCode 进行扰动，高 16 位和低 16 位异或，减少高位差异不参与计算导致的碰撞

🎤面试要点

核心考点：1.8 为什么放弃 Segment 改用水桶结构 + CAS + synchronized？答：Segment 的锁粒度还是太大（1/16），synchronized 在 1.6+ 优化后性能大幅提升，CAS + synchronized 可以锁定更小的粒度，并发度更高
put 操作全程是否需要加锁？答：不一定。如果 bin 为空，CAS 成功即可，无需加锁。只有在 bin 非空需要遍历链表时，才需要 synchronized 锁定头节点
get 操作为什么不需要加锁？答：因为 Node.value 和 Node.next 都是 volatile 的，volatile 的 happens-before 关系保证了可见性。但注意：get 返回的是"近似"值，可能读到旧数据（因为 put 的操作分两步：先改 val，再 unlink 旧节点）
为什么 ConcurrentHashMap 不支持 null 键和 null 值？答：因为 get(key) 返回 null 无法区分是"key 不存在"还是"key 对应的值为 null"。这在 ConcurrentHashMap 中会产生歧义
ConcurrentHashMap 的迭代器是强一致性还是弱一致性？答：弱一致性（weakly consistent）。迭代器不会抛 ConcurrentModificationException，能反映创建迭代器之后的修改，但不保证反映所有修改

🛠️实战场景

缓存计数：用 ConcurrentHashMap 的 compute() 或 merge() 方法做分布式环境下的本地计数，替代 AtomicInteger 做细粒度计数
用户会话存储：Spring Session 等框架中，用 ConcurrentHashMap 做内存级 Session 缓存（配合过期清理策略）
本地缓存：小型本地缓存场景，不需要引入 Guava Cache / Caffeine 时，CHM 是简单有效的选择
统计汇总：在并发场景下统计各类指标（UV/PV/接口耗时分布等），用 CHM 做聚合比加锁 HashMap 简单高效

// 实用：merge 做计数
ConcurrentHashMap<String, Integer> stats = new ConcurrentHashMap<>();
stats.merge("error", 1, Integer::sum);    // 不存在则创建，存在则+1
stats.merge("success", 1, Integer::sum);

// 实用：compute 做条件更新
stats.compute("total", (k, v) -> {
    if (v == null) return 1;
    return v + 1;
});

💥踩坑经验

put 值覆盖问题：putIfAbsent() 虽然原子性地"不存在则插入"，但 put() 不保证原子性。如果需要"不存在则创建+初始化"的复合操作，用 computeIfAbsent()，它内部保证了原子性
compute/merge 的陷阱：compute 的 mappingFunction 执行期间持有 bin 锁，如果 mappingFunction 内部调用外部服务或做耗时操作，会阻塞其他线程对该 bin 的访问，严重影响性能
迭代时不要修改：虽然迭代器不会抛异常，但并发修改会影响迭代结果的正确性
containsValue/containsKey 不是原子操作：这两个方法是逐元素遍历检查，并发环境下结果不准确。如果需要原子性检查+操作，用 computeIfAbsent/merge

🚫 computeIfAbsent 经典坑

在 Java 8 中，computeIfAbsent 如果 mappingFunction 返回 null，会认为操作失败而不插入，这是符合预期的。但如果 mappingFunction 内部执行耗时 IO 操作（如查数据库），会长时间持有 bin 锁，造成其他线程阻塞。解决方案：提前在外部准备好值，或使用异步方式。

❓模拟面试题

Q1: 请详细描述 ConcurrentHashMap 在 1.7 和 1.8 中的实现差异

参考回答要点：①数据结构：1.7 是 Segment 数组 + HashEntry 数组 + 链表，1.8 是 Node 数组 + 链表/红黑树；②锁机制：1.7 是 Segment 继承 ReentrantLock 做分段锁，1.8 是 CAS + synchronized 锁 bin 头节点；③锁粒度：1.7 是 1/16 数据，1.8 是 1/N 数据；④并发扩容：1.7 各 Segment 独立扩容，1.8 支持多线程协助扩容；⑤扩容方式：1.7 是头插法，1.8 也是头插法但通过 ForwardingNode 支持并发扩容。

Q2: ConcurrentHashMap 的 get 操作为什么不需要加锁？

参考回答要点：①Node 的 value 和 next 字段都是 volatile 修饰的，volatile 的写操作 happens-before 于后续读操作，保证了可见性；②put 操作分两步：先修改 value（volatile 写），再 unlink 旧节点（volatile 写），读操作总能读到最新的 value 或旧 value，不会读到脏数据；③但 get 返回的是近似值，不能保证读到所有并发修改。

Q3: ConcurrentHashMap 支持 null 键和 null 值吗？为什么？

参考回答要点：不支持。因为 get(key) 返回 null 无法区分是 key 不存在还是 value 为 null。这与 HashMap 不同——HashMap 允许 null 键因为它的 put 是原子性的（单线程下不存在歧义），但 ConcurrentHashMap 在并发场景下，null 值会导致语义歧义。