Lesson 05 · 集合框架源码

ConcurrentHashMap 深度剖析：put 流程、size 统计与扩容

深度·🔥 极高·#集合·#并发·#源码

ConcurrentHashMap 分段锁到 CAS+synchronized 的演进

Day 2 / 66

💡 一、核心概念

ConcurrentHashMap（简称 CHM）是 Java 并发编程中最核心的线程安全集合类之一。它的演进贯穿了 Java 5 到 Java 8 的整个并发体系发展史，是面试官最爱的考点之一。

JDK 1.7 实现：基于 Segment（分段锁） + HashEntry 数组实现，每个 Segment 继承自 ReentrantLock，是一个可重入锁
JDK 1.8 实现：废弃 Segment，采用 Node 数组 + 链表 + 红黑树，锁粒度细化到每个桶（数组节点），使用 CAS + synchronized 实现
核心优势：比 Hashtable 和 Collections.synchronizedMap 性能高出一个数量级，比 CopyOnWriteArrayList 更适合读多写少的场景

🔑 核心要点：JDK 1.8 的 CHM 和 HashMap 的结构完全一致（数组+链表+红黑树），唯一的区别在于每个桶上的操作加上了 synchronized 锁。

🏗️ 二、底层数据结构演进

2.1 JDK 1.7：Segment + HashEntry 分段锁

Segment：继承自 ReentrantLock，每个 Segment 管理一个 HashEntry 数组（即一个桶段），大小固定为 2 的幂
HashEntry<K,V>：链表节点，key/volatile，value volatile，next 不变，不可变字段保证读无需加锁
ConcurrentHashMap：维护一个 Segment 数组，默认为 16 个 Segment，最大并发度 = Segment 数量

// JDK 1.7 核心结构示意
class ConcurrentHashMap<K,V> {
    final Segment<K,V>[] segments;  // 段数组
    // 每个 Segment 继承 ReentrantLock
    static class Segment<K,V> extends ReentrantLock {
        volatile HashEntry<K,V>[] table; // 桶数组
        int threshold; // 扩容阈值
    }
    static class HashEntry<K,V> {
        final K key;
        final int hash;
        volatile V value;
        final HashEntry<K,V> next;
    }
}
    

⚠️ 分段锁的局限性：虽然提高了并发度，但 Segment 数量固定导致并发度上限（默认 16）；size() 操作需要遍历所有 Segment 加锁求和，效率低且结果可能不准确。

2.2 JDK 1.8：Node 数组 + CAS + synchronized

Node<K,V>：与 HashMap.Node 类似，不可变的 key 和 hash，value 和 next 用 volatile 修饰
TreeBin：当链表长度 ≥ 8 时，封装红黑树根节点，提供读写锁来保护树操作
ForwardingNode：扩容时的过渡节点，指向下一个扩容任务的 Node 数组，帮助其他线程帮助扩容
Unsafe + CAS：用于 table 的初始化（initTable）、节点的 CAS 插入、扩容中标记位的设置等无锁操作

// JDK 1.8 核心结构示意
class ConcurrentHashMap<K,V> {
    transient volatile Node<K,V>[] table;  // 主数组，volatile
    private volatile LongAdder counterCell; // 精确计数
    
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        volatile V value;        // volatile 保证可见性
        volatile Node<K,V> next; // volatile 保证链表可见性
    }
    static final class TreeBin<K,V> extends Node<K,V> {
        final TreeNode<K,V> root;
        volatile TreeNode<K,V> first;
        volatile Thread waiter;
        volatile int lockState; // =1 写锁，=-1 读锁
    }
    static final class ForwardingNode<K,V> extends Node<K,V> {
        final Node<K,V>[] nextTable; // 扩容后的新数组
    }
}
    

🔐 三、CAS + synchronized 的并发控制机制

CAS（Compare-And-Swap）：用于无锁化的结构变更——table 初始化、新节点的插入、扩容时标记位的设置。通过 Unsafe.compareAndSwapObject() 实现原子操作
synchronized（锁桶）：只有当定位到的桶头节点不为 null 时才加锁，锁的粒度是单个桶（数组元素），而非整个 Segment

💡 为什么 JDK 1.8 改用 synchronized 而不是 ReentrantLock？
① synchronized 经过 JVM 持续优化（偏向锁→轻量级锁→重量级锁），在低竞争下性能优于 ReentrantLock；
② synchronized 支持锁粗化等优化，JVM 层面更加成熟；
③ 锁粒度已经细化到单个桶，竞争激烈程度远低于 Segment 级别，synchronized 完全够用。

3.1 put 操作流程（JDK 1.8）

① 检查 table 是否为空，若为空则通过 CAS 初始化（initTable）
② 计算 hash，定位桶索引 (n - 1) & hash
③ 无锁情况：若桶头节点 f = tabAt(tab, i) 为 null，则用 CAS 直接插入新节点（FIFO 插入，不加锁）
④ 冲突情况：若 f.hash == MOVED (-1)，说明正在扩容，当前线程帮助扩容（transfer）
⑤ 正常冲突：若 f 不为 null 且不是 FWD，则 synchronized (f) 加锁，按链表或树插入
⑥ 链表长度 ≥ 8 且数组长度 ≥ 64 时，转红黑树（treeifyBin）
⑦ 操作完成后调用 addCount() 检查是否需要扩容

// JDK 1.8 put() 核心流程伪代码
V put(K key, V value) {
    if (key == null) throw new NullPointerException();
    int hash = spread(key.hashCode());
    while (true) {
        Node<K,V> f; int n, i;
        // 步骤1: 初始化
        if ((n = table.length) == 0) initTable();
        // 步骤2: 定位桶
        else if ((f = tabAt(table, i = (n - 1) & hash)) == null) {
            // CAS 无锁插入
            if (casTabAt(table, i, null, new Node(hash, key, value))) break;
        }
        else if ((f.hash == MOVED)) {
            // 帮助扩容
            helpTransfer(table, f);
        }
        else {
            // synchronized 锁住桶头节点
            synchronized (f) {
                if (tabAt(table, i) == f) {
                    if (f.hash >= 0) {
                        // 链表插入
                        for (...) { ... }
                    } else if (f instanceof TreeBin) {
                        // 树插入
                        ((TreeBin<K,V>)f).putTreeVal(...);
                    }
                }
            }
        }
    }
    addCount(1L, binCount);
    return null;
}
    

3.2 get 操作流程（零锁读取）

① 计算 hash，定位桶 (n-1)&hash
② 读取桶头节点 f = volatile tabAt(table, i)
③ 比较 f.hash 与 hash，相等则直接返回 value（通过 volatile 读取，保证可见性）
④ 如果不等，按链表或树遍历查找（链表节点用 volatile 读 next，保证读到最新值）

✅ get() 完全无锁：因为 key/value/next 均为 volatile，且 key 不可变，所以读取时不需要任何同步，实现真正的"读无锁"。

⚖️ 四、对比分析

维度	JDK 1.7 Segment	JDK 1.8 CAS+synchronized
锁粒度	Segment 级别（默认 16 个桶段）	桶（数组节点）级别
最大并发度	固定为 Segment 数（默认 16）	理论上线性扩展（数组长度）
并发控制	ReentrantLock（继承）	CAS + synchronized
扩容机制	单个 Segment 独立扩容	多线程协作扩容（transfer 帮助扩容）
数据结构	Segment → HashEntry 链表	Node 链表 + TreeBin 红黑树
size() 操作	遍历所有 Segment 加锁求和	通过 LongAdder 精确计数
内存占用	更高（Segment 开销）	更低（直接数组）

🚀 五、实战场景

缓存本地化：使用 ConcurrentHashMap 作为本地缓存，替代 Collections.synchronizedMap，在高并发场景下显著提升吞吐量
计数器：利用 computeIfAbsent() + AtomicLong 实现分布式计数器，避免频繁加锁
线程安全缓存：结合 Caffeine / Guava Cache 的本地缓存层，CHM 作为二级缓存的线程安全容器
全局状态管理：Spring 应用中管理全局配置、在线用户数、连接池状态等

💼 最佳实践：CHM 的 computeIfAbsent(key, mappingFunction) 是线程安全的原子操作，避免 "get → put" 两步操作中的竞态条件。

⚠️ 六、踩坑经验

mappingFunction 不应有副作用：computeIfAbsent() 的映射函数如果内部操作耗时较长，会阻塞同桶的其他线程（因为持有 synchronized 锁）
迭代器是弱一致性的：CHM 的 Iterator 不会抛 ConcurrentModificationException，是 fail-safe 的，遍历时反映的是某个时刻的快照
hashCode 必须正确实现：如果 key 的 hashCode() 返回固定值，所有元素会集中在一个桶，退化为链表 O(n) 甚至树 O(log n)，性能骤降

🚨 经典 Bug：自定义对象作为 key 未重写 hashCode/equals
某业务系统中使用自定义对象作为 CHM 的 key，忘记重写 hashCode()。导致所有 key 的 hash 相同，全部集中在同一个桶，当数据量达到百万级时，get 操作从 O(1) 退化为 O(n)，直接导致 CPU 飙升至 100%。排查方向：检查 CHM 的 size() 远大于桶数量，使用 jmap 查看桶分布。

⚠️ computeIfAbsent 陷阱
map.computeIfAbsent(key, k -> expensiveOperation())
如果 expensiveOperation() 耗时 100ms，那么持有该桶锁的所有线程都会被阻塞。解决方案：将映射函数改为无锁的轻量操作，或使用 ConcurrentHashMap.compute() 替代方案。

🎯 七、模拟面试题

🔥 高频面试题

Q1：请对比 JDK 1.7 和 JDK 1.8 中 ConcurrentHashMap 的实现差异

答：1.7 使用 Segment 分段锁（继承 ReentrantLock），1.8 使用 Node 数组+CAS+synchronized。1.8 锁粒度更细（桶级别）、并发度更高、扩容支持多线程协助、size() 精确计数。数据结构方面，1.8 增加了红黑树结构（链表转树阈值 8）

Q2：JDK 1.8 为什么用 synchronized 而不用 ReentrantLock？

答：① JVM 对 synchronized 有持续优化（偏向锁、轻量级锁、锁消除、锁粗化），低竞争下性能优于 ReentrantLock；② 锁粒度已经到桶级别，竞争激烈程度很低；③ synchronized 是 JVM 内置语法，性能开销更小；④ CAS + synchronized 的组合在 JDK 1.8 的 LockSupport 和 Unsafe 支持下非常高效

Q3：put 操作的具体流程？哪些步骤加了锁？哪些没有？

答：① CAS 初始化 table — 无锁；② CAS 直接插入空桶 — 无锁；③ 帮助扩容 — 无锁；④ synchronized 锁桶头后插入/更新 — 有锁；⑤ addCount 检查扩容 — 无锁（CAS 原子操作）。只有步骤④加了锁，其余均为无锁操作

Q4：ConcurrentHashMap 如何保证线程安全？读操作为什么不需要加锁？

答：写操作通过 CAS（结构变更）+ synchronized（桶级别写锁）保证线程安全。读操作不需要加锁，因为 key/value/next 都用 volatile 修饰，保证了可见性和有序性。key 是不可变的（final），value 的 volatile 保证了读取到最新写入值

Q5：扩容时如何保证线程安全？什么是帮助扩容？

答：JDK 1.8 使用 ForwardingNode 标记扩容中的桶。当线程发现桶中是 FWD 节点时，会参与 transfer() 帮助扩容。扩容过程将原数组分片（stride 默认 16 个桶），每个线程负责一段范围的迁移。迁移时将原桶替换为 FWD 节点，防止其他线程继续写入旧数据

Q6：CHM 在什么情况下链表会转红黑树？树在什么情况下退化为链表？

答：链表长度 ≥ 8 且数组长度 ≥ 64 时，调用 treeifyBin() 转红黑树。如果数组长度 < 64，优先选择 expandTable() 扩容而非转树（因为扩容后节点分散可能就不冲突了）。当树中节点数量 ≤ 6 时（树删除操作中），退化为链表

Q7：CHM 和 Hashtable、Collections.synchronizedMap 有什么区别？

答：① Hashtable：整个 Map 加一把大锁，并发性能极差；② Collections.synchronizedMap：整个 Map 加一把大锁，读也需加锁；③ ConcurrentHashMap：1.7 分段锁（16 把锁），1.8 桶级锁（N 把锁）+ CAS，读完全无锁，并发性能高出 1 个数量级

📊 今日总结

ConcurrentHashMap 是 Java 并发集合的标杆实现。理解从 Segment 到 CAS+synchronized 的演进，本质上是在理解 Java 并发体系从"粗粒度锁"到"细粒度无锁化"的进化方向。重点掌握 put/get 流程中哪些步骤有锁、哪些无锁。

锁机制
CAS + synchronized 桶级锁

读操作
完全无锁（volatile）

锁升级
链表 ≥ 8 转红黑树

📚 学习进度

2 / 66 知识点

👉

明日预告 · Day 3

ArrayList vs LinkedList 使用场景

Java 中高级面试复习 · java-interview-outline · Day 2/66

📋 Java 中高级面试复习卡片