ConcurrentHashMap 实现原理

HashMap 在并发下会丢数据、破坏结构，Hashtable 则用一把 synchronized 锁住整个表，吞吐量低到几乎不可用。ConcurrentHashMap 是这两者之间的正确答案：它既要保证线程安全，又要让多线程尽量并行。本文对比 JDK 7 与 JDK 8 两代实现，重点讲清 JDK 8 的 CAS 加桶级锁、size 统计和扩容协助机制。

一、两代实现的根本差异

JDK 7 采用分段锁（Segment）：整个表被拆成 16 个 Segment，每个 Segment 继承 ReentrantLock，内部是一个 HashEntry 数组。不同 Segment 之间完全并行，锁粒度是"段"。

JDK 7
ConcurrentHashMap
 ├── Segment[0] (ReentrantLock) → HashEntry[] → 链表
 ├── Segment[1] (ReentrantLock) → HashEntry[] → 链表
 ├── ...
 └── Segment[15]

JDK 8 放弃了 Segment，直接沿用 HashMap 的"数组 + 链表 + 红黑树"，锁粒度降到单个桶的头节点。并发度不再受段数限制，等于数组长度。

JDK 8
Node[] table
[0]  → null
[1]  → Node → Node → null        （synchronized 锁住头节点）
[2]  → null
[3]  → TreeBin（红黑树）
...

核心字段：

transient volatile Node<K,V>[] table;      // 主表，volatile 保证可见性
private transient volatile Node<K,V>[] nextTable;  // 扩容期间的临时表
private transient volatile long baseCount; // size 基础值
private transient volatile int sizeCtl;    // 控制标识：初始化/扩容/阈值
private transient volatile int transferIndex;

sizeCtl 是理解 ConcurrentHashMap 的钥匙，一个变量承担多种语义：

二、put：CAS 占位 + synchronized 锁桶

putVal 的主干逻辑如下，注释标出了每一步的并发策略：

final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());
    int binCount = 0;
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh; K fk; V fv;
        // 1. 表未初始化，先初始化
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        // 2. 桶为空，CAS 写入，无锁
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
                break;
        }
        // 3. 桶头是 MOVED，说明正在扩容，当前线程去帮忙
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        // 4. 桶非空，synchronized 锁住头节点
        else {
            V oldVal = null;
            synchronized (f) {
                if (tabAt(tab, i) == f) {          // 双重检查，防止锁前被换掉
                    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;
                                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);
                                break;
                            }
                        }
                    }
                    else if (f instanceof TreeBin) { // 红黑树
                        // putTreeVal ...
                    }
                }
            }
            if (binCount != 0) {
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    addCount(1L, binCount);
    return null;
}

几个关键设计：

• 桶为空时用 CAS，不进入同步块。绝大多数写入在无竞争时完全不阻塞。
• 桶非空时只锁头节点，不同桶可以并行写入。锁对象是 f，也就是链表第一个节点或 TreeBin。
• synchronized 而非 ReentrantLock。JDK 8 中偏向锁、轻量级锁让未竞争时的 synchronized 开销很低，而且省去了每个节点维护锁对象的内存。
• MOVED 标记。扩容时旧桶头节点会被替换成 ForwardingNode，其 hash 为 MOVED（-1）。其他线程看到后调用 helpTransfer 一起迁移，而不是干等。
• 不允许 null key/value。并发下 get 返回 null 无法区分"不存在"和"值为 null"，因此直接禁止。

spread 方法把高位异或到低位，并强制最高位为 0，避免与负数 hash 标记冲突：

static final int spread(int h) {
    return (h ^ (h >>> 16)) & HASH_BITS;  // HASH_BITS = 0x7fffffff
}

initTable 用 CAS 抢初始化权，失败的一方让出 CPU 而不是自旋空转：

private final Node<K,V>[] initTable() {
    Node<K,V>[] tab; int sc;
    while ((tab = table) == null || tab.length == 0) {
        if ((sc = sizeCtl) < 0)
            Thread.yield();                    // 其他线程正在初始化，让出 CPU
        else if (U.compareAndSetInt(this, SIZECTL, sc, -1)) {
            try {
                if ((tab = table) == null || tab.length == 0) {
                    int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                    Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                    table = tab = nt;
                    sc = n - (n >>> 2);        // 0.75 * n
                }
            } finally {
                sizeCtl = sc;
            }
            break;
        }
    }
    return tab;
}

初始化只做一次，sizeCtl 从 -1 恢复为 0.75n，此后它就承担扩容阈值的角色。这个"一个字段多语义"的设计减少了 CAS 目标数量，但读代码时必须结合上下文判断当前含义。

三、扩容：多线程协同迁移

transfer 把旧表每个桶迁移到新表，核心是把迁移任务按桶区间切分，由 transferIndex 协调。每个线程领取一段区间，从后往前处理。

private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
    int n = tab.length, stride;
    // 每个线程至少处理 16 个桶，避免任务切得太碎
    if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
        stride = MIN_TRANSFER_STRIDE;

    if (nextTab == null) {
        nextTab = new Node[n << 1];
        nextTable = nextTab;
        transferIndex = n;
    }
    int nextn = nextTab.length;
    ForwardingNode<K,V> fwd = new ForwardingNode<>(nextTab);
    boolean advance = true;
    boolean finishing = false;

    for (int i = 0, bound = 0;;) {
        Node<K,V> f; int fh;
        while (advance) {
            int nextIndex, nextBound;
            if (--i >= bound || finishing)
                advance = false;
            else if ((nextIndex = transferIndex) <= 0) {
                i = -1;
                advance = false;
            }
            else if (U.compareAndSetInt(this, TRANSFERINDEX, nextIndex,
                     nextBound = (nextIndex > stride ? nextIndex - stride : 0))) {
                bound = nextBound;
                i = nextIndex - 1;
                advance = false;
            }
        }
        // ... 迁移 tab[i] 的链表或树
        // 迁移完成后把旧桶设为 fwd
        setTabAt(tab, i, fwd);
    }
}

迁移单个桶时，链表同样按 (e.hash & n) == 0 拆成低位链和高位链，与 HashMap 的 resize 思路一致。红黑树则用 TreeBin 的 split，节点数不足时退化为链表。

扩容期间的读操作不会阻塞：get 遇到 ForwardingNode 会转向 nextTable 继续查找。

final 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) {
        if ((eh = e.hash) == h) {
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        }
        else if (eh < 0)   // TreeBin 或 ForwardingNode
            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;
}

get 全程无锁，依赖 tabAt 的 volatile 语义保证节点可见性。

tabAt 与 setTabAt 的实现揭示了另一个细节：

static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
    return (Node<K,V>)U.getReferenceAcquire(tab, ((long)i << ASHIFT) + ABASE);
}

static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
    U.putReferenceRelease(tab, ((long)i << ASHIFT) + ABASE, v);
}

数组元素本身无法声明为 volatile，ConcurrentHashMap 通过 Unsafe 的 acquire/release 语义对单个槽位做 volatile 读写。ASHIFT 是对象引用大小的位移量（压缩指针下为 2，即 4 字节），ABASE 是数组首元素偏移。这样既保证了可见性，又不必把整个数组声明为 volatile（Java 也不允许）。

四、size 统计：LongAdder 式分片计数

ConcurrentHashMap.size() 不是简单维护一个 AtomicLong，否则每次写入都要竞争同一个变量。它采用类似 LongAdder 的思路：基础值 baseCount 加一个 CounterCell 数组，写入时分散到不同槽位。

private final void addCount(long x, int check) {
    CounterCell[] cs; long b, s;
    if ((cs = counterCells) != null ||
        !U.compareAndSetLong(this, BASECOUNT, b = baseCount, s = b + x)) {
        // CAS 失败说明有竞争，走分片计数
        CounterCell c; long v; int m;
        boolean uncontended = true;
        if (cs == null || (m = cs.length - 1) < 0 ||
            (c = cs[ThreadLocalRandom.getProbe() & m]) == null ||
            !(uncontended = U.compareAndSetLong(c, CELLVALUE, v = c.value, v + x))) {
            fullAddCount(x, uncontended);   // 初始化或扩容计数槽
            return;
        }
        if (check <= 1) return;
        s = sumCount();
    }
    // 检查是否需要扩容 ...
}

sumCount 把 baseCount 和所有 CounterCell 加起来，因此 size() 返回的是近似值，扩容或并发写入过程中可能不准。JDK 8 的 size() 直接调用 sumCount()，不再像 JDK 7 那样尝试加锁重算两次。

final long sumCount() {
    CounterCell[] cs = counterCells;
    long sum = baseCount;
    if (cs != null) {
        for (CounterCell c : cs)
            if (c != null)
                sum += c.value;
    }
    return sum;
}

这种设计借鉴自 LongAdder：写多读少时，把竞争分散到多个缓存行，代价是读需要遍历汇总。如果业务确实需要精确计数（比如限流阈值），不要依赖 size()，应在业务层维护独立的原子计数，或者用信号量控制并发度。

CounterCell 上有一个 @Contended 注解，用于填充缓存行，避免相邻 Cell 出现伪共享（false sharing）。这是高并发计数器能线性扩展的关键细节：两个线程改的虽然是不相关的字段，但如果落在同一条 64 字节缓存行，硬件层面仍会互相失效，性能退化到接近单变量 CAS。

五、并发场景分析

computeIfAbsent 是缓存场景的常用方法，但要警惕：映射函数在持有桶锁时执行，如果函数内部又去操作同一个 map 的其他 key，可能死锁或抛异常。

JDK 8 的 computeIfAbsent 对空桶还有一条"先占位"的快路径，用占位节点避免同一个 key 被并发计算两次：

// 简化示意
if (f == null) {
    ReservationNode r = new ReservationNode();
    synchronized (r) {
        if (casTabAt(tab, i, null, r)) {
            binCount = 1;
            Node<K,V> node = null;
            try {
                if ((val = mappingFunction.apply(key)) != null)
                    node = new Node<K,V>(h, key, val);
            } finally {
                setTabAt(tab, i, node);   // 用真实节点替换占位
            }
        }
    }
}

占位节点的 hash 为 RESERVED（-3），其他线程看到后会在外层循环重试，而不是重复执行映射函数。这也解释了为什么映射函数必须很快：它阻塞的不只是一个 key，而是整个桶位。

// 错误：映射函数里递归操作同一个 map
map.computeIfAbsent("a", k -> {
    map.put("b", 1);   // 可能死锁或抛 IllegalStateException
    return 1;
});

// 正确：先在锁外算好
Integer v = computeExpensiveValue();
map.putIfAbsent("a", v);

六、常见坑 / 最佳实践

1. 不要用 size() 做精确判断。它是近似值，需要精确计数时用 mappingCount()（返回 long，语义相同但避免 int 溢出）配合业务侧独立计数。
2. get 返回 null 不代表 key 不存在。ConcurrentHashMap 禁止 null value，所以返回 null 就是不存在，这一点比 HashMap 更明确；但 containsKey 仍可用于区分场景。
3. 复合操作必须用原子方法。if (!map.containsKey(k)) map.put(k, v) 是典型的 check-then-act 竞态，应改为 putIfAbsent 或 computeIfAbsent。
4. computeIfAbsent 的映射函数要短。它在桶锁内执行，长耗时计算会阻塞同桶的其他写入。
5. 迭代器是弱一致的。ConcurrentHashMap 的迭代器不抛 ConcurrentModificationException，但也不保证看到某一时刻的完整快照。
6. 不要用 Collections.synchronizedMap 替代。前者是单锁，并发度远低于 ConcurrentHashMap。

七、小结

• JDK 7 用 Segment 分段锁，JDK 8 改为数组 + 链表/红黑树，锁粒度降到桶头节点。
• put 分三种路径：空桶 CAS、非空桶 synchronized 锁头节点、遇到 MOVED 协助扩容。
• sizeCtl 一个字段承担初始化、扩容标记和阈值三种语义。
• 扩容支持多线程协同迁移，transferIndex 分配任务，读操作经 ForwardingNode 无锁转发。
• size 采用 baseCount 加分片 CounterCell，返回近似值。
• 并发复合操作用 compute、merge、putIfAbsent，不要自己写 check-then-act。