books

《Java 并发编程·JUC 源码与容器》5.3 弱一致迭代与复合操作

用本机实验说明 ConcurrentHashMap 迭代器的弱一致性：Traverser 如何跨新旧表、为什么不抛 ConcurrentModificationException，以及 compute/computeIfAbsent/merge 只锁单桶的原子性边界和递归更新导致的异常与跨 map 死锁。

Leeting Yan 2026-10-28 10 分钟阅读 4818 字

承接的问题

5.2 走完了 get 和 putVal：读不取锁，写只锁桶头，扩容时 helpTransfer 把等待变成搬运。还剩两个容易被误用的地方：

迭代器到底看到的是创建那一刻的快照，还是遍历过程中的实时状态？遍历时另一个线程扩容、删除、插入，会不会抛 ConcurrentModificationException？
compute、computeIfAbsent、merge 号称「整个调用原子」，这个「原子」覆盖多大范围？在映射函数里再改同一个 map 会怎样？

这两个问题的答案都不是「是/否」，而是「在哪个范围内成立」。本节用源码和本机实验把边界画出来。

迭代器是实时视图，不是快照

CHM 的迭代器没有 modCount，也不复制一份表。它继承 Traverser，按数组下标从 baseIndex 往 baseLimit 走，每个桶当场读取。

// JDK 25 源码摘录，已删减：ConcurrentHashMap.Traverser.advance
        final Node<K,V> advance() {
            Node<K,V> e;
            if ((e = next) != null)
                e = e.next;
            for (;;) {
                Node<K,V>[] t; int i, n;  // must use locals in checks
                if (e != null)
                    return next = e;
                if (baseIndex >= baseLimit || (t = tab) == null ||
                    (n = t.length) <= (i = index) || i < 0)
                    return next = null;
                if ((e = tabAt(t, i)) != null && e.hash < 0) {
                    if (e instanceof ForwardingNode) {
                        tab = ((ForwardingNode<K,V>)e).nextTable;
                        e = null;
                        pushState(t, i, n);
                        continue;
                    }
                    else if (e instanceof TreeBin)
                        e = ((TreeBin<K,V>)e).first;
                    else
                        e = null;
                }
                if (stack != null)
                    recoverState(n);
                else if ((index = i + baseSize) >= n)
                    index = ++baseIndex; // visit upper slots if present
            }
        }

几个要点：

tab 是当前表，遇到 ForwardingNode 时会临时切到 nextTable；pushState 把旧表和当前下标压栈，recoverState 在新表这一段走完后恢复旧表的位置。这样迁移中的桶只走一次，未迁移的桶也不会漏。
TreeBin 不按红黑树中序输出，而是取 first 走链表；所以树化前后迭代顺序一致。
每个桶在访问时才读，已经走过的桶不会再回看。创建迭代器之后新增到后面桶的条目可能被看到，新增到前面桶的看不到；删除同理。

Iterator.remove 也不是维护迭代器内部状态，而是转成一次 map 删除：

// JDK 25 源码摘录，已删减：ConcurrentHashMap.BaseIterator.remove
        public final void remove() {
            Node<K,V> p;
            if ((p = lastReturned) == null)
                throw new IllegalStateException();
            lastReturned = null;
            map.replaceNode(p.key, null, null);
        }

实验让迭代器先消费两个条目，再删除一个尚未访问的键、插入一个落在同一桶的新键，然后继续遍历。a 到 h 恰好落在 1 到 8 号桶，最小复现如下：

package juc.ch05;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;

public final class WeakIterationDemo {
    public static void main(String[] args) {
        ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();
        for (String k : List.of("a", "b", "c", "d", "e", "f", "g", "h")) {
            map.put(k, 1);
        }
        Iterator<Map.Entry<String, Integer>> it = map.entrySet().iterator();
        List<String> seen = new ArrayList<>();
        seen.add(it.next().getKey());
        seen.add(it.next().getKey());
        map.remove("g");
        map.put("z1", 100);
        while (it.hasNext()) {
            seen.add(it.next().getKey());
        }
        System.out.println("seen=" + seen);
    }
}

$ javac --release 25 -d out src/juc/ch05/WeakIterationDemo.java
$ java -cp out juc.ch05.WeakIterationDemo
seen=[a, b, c, d, e, f, z1, h]

g 不在结果里，z1 在；如果迭代器是快照，结果会反过来。

g 在 7 号桶，迭代器还没走到；删除后换成同桶的 z1，继续遍历时看到的是 z1，不是 g。如果迭代器是快照，g 仍会出现、z1 不会出现。事实相反：它读的是遍历那一刻的桶。

再看并发结构修改。一个写线程不断插入新键、删除旧键，主线程同时遍历 20 万条的 map：

== iterator under concurrent structural change ==
iterated=214872 writesDuringIteration=48836 sum=26073620342 (no ConcurrentModificationException)

遍历条数大于初始的 200 000，说明它看到了写线程后来插入的键；整个过程中没有 ConcurrentModificationException，因为 CHM 根本没有 modCount 检查。writesDuringIteration 和 sum 每次运行都不同，这两个数只证明过程完成，不作为吞吐结论。

弱一致的准确含义是：

不会抛 ConcurrentModificationException；
反映迭代器创建之后、遍历到该桶之前发生的部分修改；
不保证看到某个时刻的完整快照，也不保证同一个键的值前后一致；
EntryIterator 返回的 MapEntry 在 next() 时复制 key 和 value，之后 map 再改不影响这个 entry 的 getValue()，但 setValue 会写回 map。

迁移中的迭代：为什么要一个栈

只靠 tab = nextTable 还不够。假设旧表 16 个桶，迭代到 3 号桶时发现它已迁移，跳到新表 32 个桶。新表的 3 号和 19 号对应旧表 3 号的后继，但新表下标 3 之后还有 4、5……这些新桶可能对应旧表 2 号桶（已访问）或旧表 4 号桶（未访问）。如果没有栈记录「我从旧表几号来、旧表多长」，跳过去再回来就会重复或漏掉。

pushState 在遇到 ForwardingNode 时保存 tab、length、index；recoverState 在新表这一段结束后弹出，恢复旧表的 index，再按 baseIndex 前进。源码注释说得很直接：需要这套保存/恢复机制的情况很少，但一旦遇到一个转发节点，通常会遇到很多个，所以 Traverser 用 spare 复用 TableStack 节点，避免大量分配。

这也是「弱一致」不是「随便一致」的原因：它保证一次遍历不会把同一个桶走两遍，也不会跳过尚未访问的旧桶；但桶在遍历过程中被搬走、被删、被加，看到什么取决于时序。

compute 家族：只锁一个桶的原子性

computeIfAbsent 在空桶上先放一个 ReservationNode 占位，再在它的监视器里执行映射函数：

// JDK 25 源码摘录，已删减：ConcurrentHashMap.computeIfAbsent 空桶分支
            else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
                Node<K,V> r = new ReservationNode<K,V>();
                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);
                        }
                    }
                }
                if (binCount != 0)
                    break;
            }

桶非空时锁的是桶头，映射函数同样在锁内执行。如果函数返回非 null，新节点追加到链表尾部；追加前会检查 pred.next 是否被递归修改过：

// JDK 25 源码摘录，已删减：ConcurrentHashMap.computeIfAbsent 链表尾部
                                if ((e = e.next) == null) {
                                    if ((val = mappingFunction.apply(key)) != null) {
                                        if (pred.next != null)
                                            throw new IllegalStateException("Recursive update");
                                        added = true;
                                        pred.next = new Node<K,V>(h, key, val);
                                    }
                                    break;
                                }

compute 的结构相同，区别是它允许返回 null 表示删除，并且用 delta 记录计数变化：

// JDK 25 源码摘录，已删减：ConcurrentHashMap.compute 链表分支
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);
            else {
                synchronized (f) {
                    if (tabAt(tab, i) == f) {
                        if (fh >= 0) {
                            binCount = 1;
                            for (Node<K,V> e = f, pred = null;; ++binCount) {
                                K ek;
                                if (e.hash == h &&
                                    ((ek = e.key) == key ||
                                     (ek != null && key.equals(ek)))) {
                                    val = remappingFunction.apply(key, e.val);
                                    if (val != null)
                                        e.val = val;
                                    else {
                                        delta = -1;
                                        Node<K,V> en = e.next;
                                        if (pred != null)
                                            pred.next = en;
                                        else
                                            setTabAt(tab, i, en);
                                    }
                                    break;
                                }
                                pred = e;
                                if ((e = e.next) == null) {
                                    val = remappingFunction.apply(key, null);
                                    if (val != null) {
                                        if (pred.next != null)
                                            throw new IllegalStateException("Recursive update");
                                        delta = 1;
                                        pred.next = new Node<K,V>(h, key, val);
                                    }
                                    break;
                                }
                            }
                        }

merge 只在键存在时调用重映射函数，参数顺序是 (oldValue, givenValue)；返回 null 删除，键不存在时直接放入 givenValue。它和 compute 共用同一套桶锁和 delta 计数。

原子性边界可以列成表：

操作	原子范围	不保证
`computeIfAbsent(k, f)`	同一个桶内、键 `k` 的「查—算—插」	映射函数对其他键、其他桶的操作
`compute(k, f)`	同一个桶内、键 `k` 的「查—算—改/删」	跨桶的复合不变量
`merge(k, v, f)`	同一个桶内、键 `k` 的「查—合并—改/删」	其他键的并发修改
`replace(k, old, new)`	同一个桶内、单键比较替换	先 `get` 再判断的复合逻辑
两次不同键的 `compute`	各自桶内原子	两个键之间的整体原子性

同一个桶里的不同键会互相等待，因为锁是桶头；不同桶可以并行。映射函数执行时间直接等于桶锁持有时间，所以只能做纯内存计算，不能做 I/O，也不能修改同一个 map。

在映射函数里改同一个 map

本机三种写法，结果完全不同：

== computeIfAbsent on empty bin, recursive put same key ==
threw IllegalStateException: Recursive update; map={}
== computeIfAbsent on occupied bin, recursive put another key ==
threw IllegalStateException: Recursive update; map={alpha=1, c14=5}
== computeIfAbsent, recursive put to a different bin ==
result=2 map={x=2, d0=1} size=2

逐个解释：

空桶里递归 put 同一个键：外层已经把 ReservationNode 放进桶，内层 putVal 看到 ReservationNode 直接抛 IllegalStateException("Recursive update")。外层的 finally 把桶设回 null，所以 map 还是空的。
已有链表桶里递归 put 同桶另一个键：synchronized 可重入，内层 put 成功把 c14=5 追加进链表；外层映射函数返回 6 后检查 pred.next != null，发现链表被改过，抛异常。异常发生时内层的写入已经生效，map 留下 {alpha=1, c14=5}——这正是「不要在映射函数里改 map」的代价：失败不是回滚。
递归 put 到不同桶：没有触发同一个桶的检查，看起来成功，{x=2, d0=1}、size=2。但这是未定义行为，JDK 文档明确要求映射函数不得修改本 map；换一个版本、换一种桶形态（树桶、扩容中）就可能变成异常或计数错误。

compute 的映射函数返回 null 会删除键，computeIfAbsent 返回 null 则不插入；两者都不会因为返回 null 抛异常。真正危险的是副作用，不是返回值。

死锁：同桶可重入，不同桶照样反转

第一种，同一个线程、同一个 map、同一个桶：synchronized 可重入，不会自己等自己。它要么像上面那样抛 Recursive update，要么无限递归到 StackOverflowError。

第二种，同一个 map、两个不同的桶，嵌套 compute。线程 A 先锁 1 号桶，再锁 2 号桶；线程 B 先锁 2 号桶，再锁 1 号桶。虽然是同一个 map，锁顺序仍然反转。本机用 "a"（1 号桶）和 "b"（2 号桶）构造：

== deadlock: one map, two different bins, opposite lock order ==
same-map findDeadlockedThreads: 2 threads
same-map-A-then-B state=BLOCKED lock=java.util.concurrent.ConcurrentHashMap$ReservationNode@8efb846
  at java.util.concurrent.ConcurrentHashMap.compute(...)
  at juc.ch05.ComputeRecursionProbe.lambda$sameMapDeadlock$1(...)
  at juc.ch05.ComputeRecursionProbe$$Lambda/0x0000780001040c00.apply(...)
  at java.util.concurrent.ConcurrentHashMap.compute(...)
same-map-B-then-A state=BLOCKED lock=java.util.concurrent.ConcurrentHashMap$ReservationNode@54bedef2
  at juc.ch05.ComputeRecursionProbe.lambda$sameMapDeadlock$4(...)
  at juc.ch05.ComputeRecursionProbe$$Lambda/0x0000780001041000.apply(...)
  at java.util.concurrent.ConcurrentHashMap.compute(...)

两个线程都停在 compute 的 synchronized (f) 上，状态 BLOCKED，各自等待对方持有的 ReservationNode 监视器。注意这不是「两个 map」的特例，而是「持有一把桶锁时再去拿另一把桶锁」的通病。

第三种，两个 map 各有一个热点桶，嵌套顺序相反。CHM 在持有桶锁时调用用户函数，用户函数再去拿另一个 map 的桶锁，就是同一类锁顺序反转。本机用两个所有键都落在同一个桶的 Key（hashCode() 恒为 7）构造：

== deadlock: two maps, two bins, opposite lock order ==
findDeadlockedThreads: 2 threads
thread-A-then-B state=BLOCKED lock=java.util.concurrent.ConcurrentHashMap$ReservationNode@23fc625e
  at java.util.concurrent.ConcurrentHashMap.compute(...)
  at juc.ch05.ComputeRecursionProbe.lambda$crossMapDeadlock$1(...)
  at juc.ch05.ComputeRecursionProbe$$Lambda/0x00001fc001042690.apply(...)
  at java.util.concurrent.ConcurrentHashMap.compute(...)
thread-B-then-A state=BLOCKED lock=java.util.concurrent.ConcurrentHashMap$ReservationNode@452b3a41
  at java.util.concurrent.ConcurrentHashMap.compute(...)
  at juc.ch05.ComputeRecursionProbe.lambda$crossMapDeadlock$4(...)
  at juc.ch05.ComputeRecursionProbe$$Lambda/0x00001fc0010428d0.apply(...)
  at java.util.concurrent.ConcurrentHashMap.compute(...)

两个线程都停在 compute 的 synchronized (f) 上，状态 BLOCKED，等待对方持有的 ReservationNode 监视器。ThreadMXBean.findDeadlockedThreads() 能直接识别这种监视器死锁；对象地址每次运行不同，线程名和栈帧是稳定的。

避免方式只有一条：映射函数保持纯函数。需要跨 map 或跨键的原子更新时，在 compute 外面用一把固定的外部锁，并且约定所有调用方都按同一顺序拿锁；或者把两个键合并成一个复合键，让它们落在同一个桶、由同一次 compute 处理。线上遇到这类死锁，用线程转储定位持锁链，卷三第 4 章展开。

在 libraryd-conc 里落地

05.2 的 tryReserve 用 get 加 replace 自旋。改成 compute 后，重试循环消失，扣减和判断在同一个桶锁内完成；物化库存用 computeIfAbsent，归还用 merge。

package com.plume.conc.core;

import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;

public final class MapBackedStockCache {
    private final BookRepository books;
    private final ConcurrentHashMap<String, Integer> stock;
    public MapBackedStockCache(BookRepository books, int expectedIsbns) {
        this.books = books;
        this.stock = new ConcurrentHashMap<>(expectedIsbns);
    }
    public int stockOf(String isbn) {
        return stock.computeIfAbsent(isbn, this::loadStock);
    }
    private int loadStock(String isbn) {
        return books.findByIsbn(isbn)
                .map(Book::stock)
                .orElseThrow(() -> new LoanException(ErrorCode.BOOK_NOT_FOUND, isbn));
    }

    public int tryReserve(String isbn, int copies) {
        return stock.compute(isbn, (key, current) -> {
            int left = current == null ? loadStock(key) : current;
            if (left < copies) {
                throw new LoanException(ErrorCode.OUT_OF_STOCK, key);
            }
            return left - copies;
        });
    }

    public void returnCopies(String isbn, int copies) {
        stock.merge(isbn, copies, Integer::sum);
    }

    public Map<String, Integer> snapshot() {
        return Map.copyOf(stock);
    }
}

loadStock 只访问仓储，不碰 stock，满足「映射函数不修改本 map」。tryReserve 库存不足时抛异常，compute 不会写入新值，映射保持不变；returnCopies 的 merge 在键不存在时插入 copies，存在时相加，不会出现「先查再写」的窗口。

snapshot() 用 Map.copyOf 复制一份不可变 map，适合做报表或对账的起点。它不是原子快照：复制过程中其他线程仍在改，副本可能混合不同时刻的值；要严格一致，只能在业务低峰暂停写入，或者用外部锁包住整段复制。

什么时候不要用

用迭代器做对账：弱一致遍历可能漏掉遍历期间新增到已访问桶的条目，也可能看到已被删除的条目。对账要 Map.copyOf 后在稳定副本上做，或者暂停写入。
在 compute 里做 I/O 或远程调用：桶锁会被持有整个调用期间，同桶其他键全部阻塞；一个慢查询就能把热点桶拖垮。先把数据取出来，再进 compute 做纯计算。
在 compute 里改同一个 map：轻则 Recursive update，重则留下部分写入；跨 map 嵌套还会死锁。需要递归结构时用 ConcurrentHashMap<String, FutureTask<V>>，先 putIfAbsent 占位，再在 FutureTask 里计算。
把 computeIfAbsent 当缓存加载器：同一个键并发请求时只有一个线程执行映射函数，其他线程阻塞在桶锁上；映射函数抛异常时没有缓存，下一次请求会重试。缓存加载应该有超时、降级和击穿保护。
需要跨键原子性：库存扣减和会员配额更新是两个键，compute 只能保证其中一个。要么合并成一个聚合对象放在同一个键下，要么用外部锁/数据库事务。

小结

CHM 迭代器是弱一致的实时视图：没有 modCount，不抛 ConcurrentModificationException，遍历到桶时才读取，能看到创建后、访问前的部分修改。
Traverser 用 TableStack 保存旧表位置，遇到 ForwardingNode 切到新表，走完再恢复，保证不重复、不跳过已访问的桶。
computeIfAbsent/compute/merge 的原子范围是「一个桶内的一个键」；映射函数在桶锁内执行，同桶其他键会等待。
在映射函数里改同一个 map：空桶递归触发 ReservationNode 的 Recursive update，链表桶递归靠 pred.next 检查抛异常，且可能留下部分写入；不同桶可能侥幸成功，但属于未定义行为。
同一 map 同一桶对同一线程可重入，不会自锁；同一 map 的不同桶、或两个 map 之间，以相反顺序嵌套 compute 会因桶锁顺序反转而死锁，映射函数必须保持纯函数。

阅读导航：上一节 5.2 put/get 的并发路径与 size 统计｜下一节 6.1 CopyOnWriteArrayList/Set

继续阅读

探索更多技术文章

浏览归档，发现更多关于系统设计、工具链和工程实践的内容。

全部文章返回首页