ConcurrentHashMap的十五年演进：从分段锁到CAS如何重塑Java并发基石

2003年，Doug Lea向JCP提交了JSR-166规范提案，试图为Java引入一套标准化的并发工具库。在此之前，Java开发者面对并发场景时只能在synchronized、Hashtable和Collections.synchronizedMap之间做出选择——它们要么过于粗粒度，要么性能堪忧。ConcurrentHashMap作为这套工具库的核心组件之一，其设计理念影响了此后二十年Java并发编程的范式。

2014年发布的JDK 8对ConcurrentHashMap进行了近乎重写级别的改造，将原本的分段锁（Segment-based locking）架构替换为CAS + synchronized的细粒度方案。这次改动的核心动机是什么？为什么Doug Lea放弃了看似优雅的分段锁设计？答案藏在对并发性能极限的追求中。

分段锁：JDK 7的妥协与智慧

JDK 7版本的ConcurrentHashMap采用了"分而治之"的策略。整个哈希表被划分为多个Segment，每个Segment本质上是一个独立的小型HashMap，拥有自己的ReentrantLock。

ConcurrentHashMap
├── Segment[0]  → HashMap + ReentrantLock
├── Segment[1]  → HashMap + ReentrantLock
├── Segment[2]  → HashMap + ReentrantLock
└── Segment[15] → HashMap + ReentrantLock (默认16个Segment)

这种设计的核心思想是：当多个线程访问不同Segment时，可以完全并行；只有访问同一Segment的线程才需要竞争锁。默认16个Segment意味着理论上最多支持16个线程并发写入，这在2003年的硬件环境下是一个合理的权衡。

但分段锁存在三个根本性问题：

并发度受限：最大并发数由Segment数量决定，无法随着CPU核心数动态扩展。当线程数超过Segment数量时，必然存在竞争。

内存开销：每个Segment都需要维护独立的HashEntry数组、负载因子阈值、modCount等元数据。对于小型Map而言，这种开销难以忽视。

伪共享风险：Segment继承自ReentrantLock，其内部包含state、exclusiveOwnerThread等字段。如果多个Segment恰好在同一缓存行中，高并发更新可能导致缓存行在CPU核心间反复失效。

更关键的是，Segment的设计本质上是"粗粒度锁的变体"。它只是在全局锁的基础上做了一次切割，并没有真正实现"每个桶一把锁"的细粒度控制。

JDK 8的范式转换：从分段到桶级

JDK 8彻底抛弃了Segment的概念，转而采用一种更激进的策略：直接在桶（bin）级别进行并发控制。

// JDK 8 ConcurrentHashMap核心数据结构
transient volatile Node<K,V>[] table;

一个volatile修饰的Node数组，这就是全部。不再有Segment，不再有预分配的锁对象。当需要同步时，直接对桶的头节点加synchronized锁。

这种设计带来了几个直接好处：

无限并发度：理论上，如果有N个桶，就可以支持N个线程并行写入。当然，实际中受限于哈希碰撞，但并发度的上限不再被硬编码。

内存效率：没有额外的锁对象开销，每个Node只有hash、key、val、next四个字段。

延迟初始化：JDK 7在构造时就会创建Segment数组，而JDK 8只有在第一次插入操作时才初始化table数组。

put操作的三层策略

JDK 8的putVal方法展示了这套新架构的精髓：

final V putVal(K key, V value, boolean onlyIfAbsent) {
    // 第一层：无锁CAS插入空桶
    if (tab[i] == null) {
        if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
            break;
    }
    // 第二层：发现ForwardingNode，协助扩容
    else if ((fh = f.hash) == MOVED)
        tab = helpTransfer(tab, f);
    // 第三层：synchronized锁住桶头节点
    else {
        synchronized (f) {
            // 遍历链表或红黑树进行插入或更新
        }
    }
}

第一层：CAS无锁插入

当目标桶为空时，使用compareAndSwapObject原子操作直接插入新节点。这是完全无锁的路径，性能接近普通HashMap。

static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
                                    Node<K,V> c, Node<K,V> v) {
    return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}

U是sun.misc.Unsafe实例，compareAndSwapObject最终会编译为CPU的cmpxchg指令。在现代x86处理器上，这条指令是Lock前缀的原子操作，保证在多核环境下的一致性。

第二层：协助扩容

如果发现桶的头节点hash值为MOVED（值为-1），说明这是一个ForwardingNode，表示当前桶已被迁移到新表。此时线程不会阻塞等待，而是主动加入扩容工作。

这是JDK 8设计中最精巧的部分：扩容不再是单线程的独占操作，而变成可并行协作的任务。

第三层：synchronized细粒度锁

只有当前两种情况都不满足时（桶非空且未在扩容），才使用synchronized锁住桶的头节点。这里有几个关键细节：

1. 锁的是头节点对象本身，而非某个全局或Segment级别的锁
2. synchronized在JDK 6之后经过了大量优化，无竞争时性能接近CAS
3. 锁的范围仅限于单个桶，不影响其他桶的操作

红黑树：对抗哈希碰撞的最后一道防线

JDK 8引入的另一个重大改进是桶的数据结构可变：当链表长度超过阈值时，自动转换为红黑树。

static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;

为什么是8？这不是拍脑袋决定的数字。在理想情况下，哈希冲突服从泊松分布。当负载因子为0.75时，单个桶中链表长度达到8的概率约为$0.00000006$——这是一个极小概率事件。

其中$\lambda = 0.5$（负载因子0.75 × 平均链表长度），计算得：

只有当哈希函数质量较差，或遭遇精心构造的碰撞攻击时，链表才会频繁达到8。此时红黑树将查找复杂度从$O(n)$降至$O(\log n)$，8个节点的情况下，最多需要$\lceil\log_2 8\rceil = 3$次比较。

TreeBin：红黑树的并发适配器

ConcurrentHashMap并没有直接在桶中存储红黑树，而是引入了TreeBin作为包装器：

static final class TreeBin<K,V> extends Node<K,V> {
    TreeNode<K,V> root;
    volatile TreeNode<K,V> first;
    volatile Thread waiter;
    volatile int lockState;
    // values for lockState
    static final int WRITER = 1; // 写锁
    static final int WAITER = 2; // 等待写锁
    static final int READER = 4; // 读锁计数
}

TreeBin的设计解决了红黑树在并发环境下的两个难题：

锁粒度问题：红黑树的插入、删除可能触发旋转，影响多个节点。如果每个节点单独加锁，复杂度不可接受。TreeBin采用单个读写锁保护整棵树。

根节点稳定性：红黑树的根节点可能因旋转而改变。直接对根节点加synchronized会导致锁对象变化。TreeBin作为不变的头节点，解决了这个问题。

多线程协作扩容：ForwardingNode的妙用

JDK 7的扩容是单线程独占式的：一个线程负责迁移所有数据，其他线程阻塞等待。这在大型Map（数百万entry）场景下会形成明显的停顿。

JDK 8采用了完全不同的策略：扩容可以由多个线程并行协作完成。

核心机制

扩容过程由三个关键变量协调：

private transient volatile int sizeCtl;        // 控制扩容状态
private transient volatile int transferIndex;  // 下一个待迁移的桶索引
private static final int MIN_TRANSFER_STRIDE = 16; // 单线程最少处理桶数

sizeCtl的值编码了丰富信息：

任务分片

扩容开始时，transferIndex被设为原数组长度。每个线程通过CAS操作"认领"一段桶区间：

// 计算本线程负责的桶区间
if ((nextIndex = transferIndex) <= 0) {
    // 所有桶已被认领完毕
}
stride = (n >>> 3) / NCPU;  // 根据CPU核心数动态计算步长
if (stride < MIN_TRANSFER_STRIDE)
    stride = MIN_TRANSFER_STRIDE;

线程从数组末尾向前"切割"任务，每个线程负责至少16个桶。这种动态分片机制确保：

1. CPU核心多的机器，单个线程任务量少，并行度高
2. 即使某个线程处理较慢，其他线程也可以继续工作

ForwardingNode：迁移中的路标

当一个桶完成迁移后，原位置会被放置一个ForwardingNode：

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;
    }
    
    Node<K,V> find(int h, Object k) {
        // 在新表中查找
    }
}

ForwardingNode的hash值固定为MOVED（-1），它持有新表的引用。当读操作遇到ForwardingNode时：

1. 不会阻塞，而是直接转向新表查找
2. 写操作会调用helpTransfer加入扩容队伍

sequenceDiagram
    participant T1 as 线程1
    participant T2 as 线程2
    participant Old as 旧表
    participant New as 新表
    
    T1->>Old: 检测到需要扩容
    T1->>New: 创建新表
    T1->>Old: 开始迁移桶[0-15]
    
    T2->>Old: put操作
    T2->>Old: 发现ForwardingNode
    T2->>New: 协助迁移桶[16-31]
    
    T1->>Old: 完成桶[0-15]
    T2->>Old: 完成桶[16-31]
    
    Note over Old,New: 多线程协作完成扩容

写时复制的哈希分布优化

迁移过程中有一个精妙的优化：由于新表容量是旧表的2倍，元素在新表中的位置只有两种可能——原位置i或i + n（n为旧表长度）。判断依据是hash值新增的最高位：

if ((e.hash & n) == 0) {
    // 位置不变，留在低位链表
    if (loTail == null)
        loHead = e;
    else
        loTail.next = e;
    loTail = e;
} else {
    // 移到新位置，加入高位链表
    if (hiTail == null)
        hiHead = e;
    else
        hiTail.next = e;
    hiTail = e;
}

这种拆分避免了重新计算hash，将原链表一分为二，分别放入新表的两个位置。

LongAdder式计数：分布式累加器

ConcurrentHashMap.size()的实现也是一个精巧的并发设计。直接对计数器加锁会显著影响性能，而简单的原子变量在高并发场景下会产生严重的CAS竞争。

JDK 8借鉴了LongAdder的设计思想：分散热点，分片计数。

private transient volatile long baseCount;
private transient volatile CounterCell[] counterCells;

@sun.misc.Contended
static final class CounterCell {
    volatile long value;
    CounterCell(long x) { value = x; }
}

计数流程：

private final void addCount(long x, int check) {
    CounterCell[] as; long b, s;
    // 尝试直接更新baseCount
    if ((as = counterCells) != null ||
        !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
        // CAS失败，使用CounterCell
        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;
        }
    }
}

当多个线程同时更新baseCount失败时，它们会被引导到不同的CounterCell槽位。每个线程根据自己的ThreadLocalRandom.getProbe()值选择槽位，大大减少了竞争。

计算size时，需要累加baseCount和所有CounterCell的值：

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;
}

值得注意的是，这个值不是精确的——在遍历counterCells的过程中，其他线程可能正在更新某些槽位。但对于size()这类操作，弱一致性是可接受的权衡。

性能对比：数字说话

Doug Lea在JDK 8的设计文档中提供了一组基准测试数据，展示了不同并发策略的性能差异：

单线程场景（无竞争开销，纳秒）：

高并发场景（64线程，纳秒）：

JDK 8在并发读取场景下性能提升近4倍，这得益于完全无锁的get操作。对于put操作，CAS优先策略配合细粒度锁，吞吐量提升了约5倍。

更关键的是延迟分布的变化。JDK 7的Segment锁在高并发下容易出现"热点Segment"，导致部分请求延迟飙升。JDK 8的细粒度设计将延迟方差大幅降低，P99延迟更加可预测。

synchronized的重生：从性能洼地到优化标杆

为什么JDK 8敢于在热路径中使用synchronized？这与JVM层面的锁优化密不可分。

在早期的JDK中，synchronized确实性能较差。每次加锁都需要向操作系统申请互斥量，涉及用户态/内核态切换。但从JDK 6开始，HotSpot引入了一系列优化：

偏向锁（Biased Locking）：当锁只有一个线程访问时，对象头的Mark Word会记录线程ID，后续加锁无需任何同步操作。这在单线程或线程交替执行的场景下几乎零开销。

轻量级锁：当存在轻度竞争时，使用CAS在栈帧中创建锁记录，避免重量级锁的开销。

自适应自旋：线程在获取锁失败后会短暂自旋等待，而非立即阻塞。自旋次数根据历史成功率动态调整。

锁粗化：JIT检测到连续的加锁/解锁操作时，会自动合并为单个锁区间。

锁消除：逃逸分析证明对象不会逃逸出方法时，直接消除锁操作。

// 锁消除示例
public String concat(String s1, String s2) {
    StringBuffer sb = new StringBuffer();
    sb.append(s1);  // StringBuffer的append是synchronized方法
    sb.append(s2);
    return sb.toString();
    // 由于sb不会逃逸，JIT会消除这两个锁
}

到了JDK 8时代，synchronized在无竞争或低竞争场景下性能已经与CAS相差无几。只有在真正的高竞争场景下，才会膨胀为重量级锁（使用操作系统互斥量）。

这也是为什么ConcurrentHashMap选择synchronized而非显式ReentrantLock的原因之一：

1. synchronized由JVM深度优化，未来升级无需修改代码
2. 内存占用更小，不需要额外的锁对象
3. 在锁对象本身（桶头节点）上同步，语义更清晰

当然，ReentrantLock在需要公平锁、可中断锁、尝试获取锁等高级特性时仍有其价值。

设计哲学：权衡的艺术

ConcurrentHashMap从JDK 7到JDK 8的演进，本质上是一场关于如何在高并发环境下最小化同步开销的工程探索。

JDK 7的设计是在2003年的硬件约束下做出的合理选择。当时的CPU核心数普遍较少，16个Segment足以覆盖大部分场景。锁的粒度虽然比全局锁细，但实现相对简单，代码可维护性好。

JDK 8的设计面向的是多核时代。CPU核心数持续增长，SSD普及导致I/O瓶颈前移，应用层对并发数据结构的性能要求不断提高。CAS + synchronized + 红黑树 + 协作扩容的组合，是对这些新需求的回应。

这种演进也反映了并发编程的一般原则：能用无锁算法解决的，尽量不用锁；能锁更小粒度的，尽量不锁更大范围；能协作完成的，尽量不串行等待。

参考资料：

1. Lea, D. (2003). JSR-166: Concurrency Utilities. Java Community Process.
2. OpenJDK. (2014). JDK 8 ConcurrentHashMap Source Code. https://github.com/openjdk/jdk/blob/jdk8/jdk/src/share/classes/java/util/concurrent/ConcurrentHashMap.java
3. JDK-8023463. Improvements to HashMap/LinkedHashMap use of bins/buckets and trees. https://bugs.openjdk.org/browse/JDK-8023463
4. Goetz, B. (2006). Java Concurrency in Practice. Addison-Wesley.
5. Baeldung. (2024). A Guide to ConcurrentMap. https://www.baeldung.com/java-concurrent-map
6. 美团技术团队. (2019). ConcurrentHashMap源码分析. https://tech.meituan.com/2019/12/05/aqs-theory-and-apply.html
7. Shipilev, A. (2019). JVM Anatomy Quark: Lock Coarsening and Loops. https://shipilev.net/jvm/anatomy-quarks/1-lock-coarsening-for-loops/
8. OpenJDK. JEP 374: Deprecate and Disable Biased Locking. https://openjdk.org/jeps/374