books

《Java 并发编程·JUC 源码与容器》5.1 ConcurrentHashMap 的节点结构

从 JDK 25 的 javap 输出出发，逐个核对 ConcurrentHashMap 的 Node、TreeBin、ForwardingNode、ReservationNode 与 CounterCell 字段，解释 MOVED/TREEBIN/RESERVED 三种负 hash 与 sizeCtl 在初始化、阈值、扩容三种状态下的编码，并给出桶状态图和本机探针输出。

Leeting Yan 9 分钟阅读 4077 字

承接的问题

4.3 用 Exchanger 把两个线程的缓冲区对调，解决的是「两个参与者、一次交换」。真实的共享状态通常不是两个线程，而是几千个线程读写几十万个键。卷一的 SynchronizedLoanService 用一把监视器锁把库存表整个包住，正确但吞吐上不去；ReentrantReadWriteLock 把读放大，写仍然串行。

ConcurrentHashMap（下称 CHM）换了一个思路：锁不再保护整个表，而是保护「一个桶」。读操作完全不取锁，写操作只锁住目标桶的头节点，扩容时多个线程可以分片搬运。这个设计成立的前提，是桶里节点的字段布局和几个特殊节点类型配合得刚好。本节先把这些结构逐个核实清楚，5.2 再走 put/get 的路径，5.3 讲迭代与复合操作。

先给结论：JDK 25 的 CHM 没有 Segment 数组，字段是 table、nextTable、sizeCtl、transferIndex、baseCount、counterCells；普通节点 Node 的 hash/key 是 final，val/next 是 volatile；负 hash 不是普通键的哈希，而是三种特殊节点的类型标记。下面每一句都用本机 javap -p 核对过。

一个桶的四种形态

CHM 的表是一个 Node<K,V>[]，每个槽位称为一个桶。桶头可能是普通链表节点、红黑树容器、迁移转发节点，或 computeIfAbsent 临时占位节点。普通节点的定义很短，但每个修饰符都有用。

// JDK 25 源码摘录，已删减：ConcurrentHashMap.Node
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        volatile V val;
        volatile Node<K,V> next;

        Node(int hash, K key, V val, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.val = val;
            this.next = next;
        }

        Node<K,V> find(int h, Object k) {
            Node<K,V> e = this;
            if (k != null) {
                do {
                    K ek;
                    if (e.hash == h &&
                        ((ek = e.key) == k || (ek != null && k.equals(ek))))
                        return e;
                } while ((e = e.next) != null);
            }
            return null;
        }
    }

hash 和 key 是 final：节点一旦挂进桶里，位置和身份不再变。val 是 volatile：读者不取锁也能看到写者发布的新值。next 也是 volatile：链表尾部追加新节点时，读者要么看不到新节点，要么看到完整构造好的节点，不会看到「半截」引用。

普通节点的 hash 一定非负。spread 把高位异或到低位后与 HASH_BITS 相与，最高位被清掉。负数因此空出来做类型标记。

// JDK 25 源码摘录，已删减：ConcurrentHashMap 常量
    static final int MOVED     = -1; // hash for forwarding nodes
    static final int TREEBIN   = -2; // hash for roots of trees
    static final int RESERVED  = -3; // hash for transient reservations
    static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash

对应的桶状态可以画成这样。

table[i] == null                 空桶：put 用 CAS 直接挂新 Node，不取锁
table[i].hash >= 0               链表桶：synchronized(头节点)，尾插或改值
table[i].hash == TREEBIN (-2)    树桶：TreeBin 持有红黑树 root + 链表 first
table[i].hash == MOVED   (-1)    已迁移：ForwardingNode 指向 nextTable
table[i].hash == RESERVED(-3)    compute 占位：ReservationNode，其他写者重试

五个内部类的字段，用 javap -p 一次看全。

$ javap -p 'java.util.concurrent.ConcurrentHashMap$Node'
class java.util.concurrent.ConcurrentHashMap$Node<K, V> implements java.util.Map$Entry<K, V> {
  final int hash;
  final K key;
  volatile V val;
  volatile java.util.concurrent.ConcurrentHashMap$Node<K, V> next;
  java.util.concurrent.ConcurrentHashMap$Node(int, K, V);
  java.util.concurrent.ConcurrentHashMap$Node(int, K, V, java.util.concurrent.ConcurrentHashMap$Node<K, V>);
  public final K getKey();
  public final V getValue();
  public final int hashCode();
  public final java.lang.String toString();
  public final V setValue(V);
  public final boolean equals(java.lang.Object);
  java.util.concurrent.ConcurrentHashMap$Node<K, V> find(int, java.lang.Object);
}

$ javap -p 'java.util.concurrent.ConcurrentHashMap$TreeBin'
final class java.util.concurrent.ConcurrentHashMap$TreeBin<K, V> extends java.util.concurrent.ConcurrentHashMap$Node<K, V> {
  java.util.concurrent.ConcurrentHashMap$TreeNode<K, V> root;
  volatile java.util.concurrent.ConcurrentHashMap$TreeNode<K, V> first;
  volatile java.lang.Thread waiter;
  volatile int lockState;
  static final int WRITER;
  static final int WAITER;
  static final int READER;
  private static final long LOCKSTATE;
  private static final long WAITERTHREAD;
  static final boolean $assertionsDisabled;
  static int tieBreakOrder(java.lang.Object, java.lang.Object);
  java.util.concurrent.ConcurrentHashMap$TreeBin(java.util.concurrent.ConcurrentHashMap$TreeNode<K, V>);
  private final void lockRoot();
  private final void unlockRoot();
  private final void contendedLock();
  final java.util.concurrent.ConcurrentHashMap$Node<K, V> find(int, java.lang.Object);
  final java.util.concurrent.ConcurrentHashMap$TreeNode<K, V> putTreeVal(int, K, V);
  final boolean removeTreeNode(java.util.concurrent.ConcurrentHashMap$TreeNode<K, V>);
  static <K, V> java.util.concurrent.ConcurrentHashMap$TreeNode<K, V> rotateLeft(java.util.concurrent.ConcurrentHashMap$TreeNode<K, V>, java.util.concurrent.ConcurrentHashMap$TreeNode<K, V>);
  static <K, V> java.util.concurrent.ConcurrentHashMap$TreeNode<K, V> rotateRight(java.util.concurrent.ConcurrentHashMap$TreeNode<K, V>, java.util.concurrent.ConcurrentHashMap$TreeNode<K, V>);
  static <K, V> java.util.concurrent.ConcurrentHashMap$TreeNode<K, V> balanceInsertion(java.util.concurrent.ConcurrentHashMap$TreeNode<K, V>, java.util.concurrent.ConcurrentHashMap$TreeNode<K, V>);
  static <K, V> java.util.concurrent.ConcurrentHashMap$TreeNode<K, V> balanceDeletion(java.util.concurrent.ConcurrentHashMap$TreeNode<K, V>, java.util.concurrent.ConcurrentHashMap$TreeNode<K, V>);
  static <K, V> boolean checkInvariants(java.util.concurrent.ConcurrentHashMap$TreeNode<K, V>);
  static {};
}

$ javap -p 'java.util.concurrent.ConcurrentHashMap$ForwardingNode'
final class java.util.concurrent.ConcurrentHashMap$ForwardingNode<K, V> extends java.util.concurrent.ConcurrentHashMap$Node<K, V> {
  final java.util.concurrent.ConcurrentHashMap$Node<K, V>[] nextTable;
  java.util.concurrent.ConcurrentHashMap$ForwardingNode(java.util.concurrent.ConcurrentHashMap$Node<K, V>[]);
  java.util.concurrent.ConcurrentHashMap$Node<K, V> find(int, java.lang.Object);
}

$ javap -p 'java.util.concurrent.ConcurrentHashMap$ReservationNode'
final class java.util.concurrent.ConcurrentHashMap$ReservationNode<K, V> extends java.util.concurrent.ConcurrentHashMap$Node<K, V> {
  java.util.concurrent.ConcurrentHashMap$ReservationNode();
  java.util.concurrent.ConcurrentHashMap$Node<K, V> find(int, java.lang.Object);
}

$ javap -p 'java.util.concurrent.ConcurrentHashMap$CounterCell'
final class java.util.concurrent.ConcurrentHashMap$CounterCell {
  volatile long value;
  java.util.concurrent.ConcurrentHashMap$CounterCell(long);
}

TreeBin 本身也是一个 Node，但它的 key/val 是 null，hash 固定为 TREEBIN。真正的键值在 TreeNode 里，first 把所有树节点按链表串起来，迭代器因此不需要中序遍历红黑树。root 是红黑树根，lockState 是寄生在桶锁上的读写锁：写者已经持有桶监视器，但树旋转会让读者看到中间状态，所以写者还要等正在读树的读者退出。WRITER=1、WAITER=2、READER=4，读者每进来一个就加 4；写者先试 CAS(lockState, 0, WRITER)，失败就进入 contendedLock 等读者退出。

ForwardingNode 的构造器只做两件事：把 hash 设成 MOVED，保存 nextTable。它覆盖 find，让读到旧表的线程顺着 nextTable 去新表继续找，避免在扩容窗口里返回错误结果。ReservationNode 更简单，hash 是 RESERVED，find 永远返回 null；它只在 computeIfAbsent 往空桶插入时短暂占位。

树化不是到 8 就转

TREEIFY_THRESHOLD = 8、UNTREEIFY_THRESHOLD = 6、MIN_TREEIFY_CAPACITY = 64 三个常量要一起看。链表长度到 8 时，treeifyBin 先检查表长：小于 64 就调用 tryPresize 扩容，而不是建树。因为小表里长链往往只是表太短，扩容后自然散开；过早建树会让 TreeNode 的额外字段白占内存。

本机把 9 个 hash 全为 7 的键放进一个初始容量 64 的 map，桶头确实变成了 TreeBin：

after 9 colliding keys: table.length=128 sizeCtl=96 head.class=TreeBin head.hash=-2
tree root=K3 red=false first=K0
tree nodes reachable by next: 9

注意表长是 128 而不是 64。构造器参数 initialCapacity 表示「预计元素个数」，不是表长；内部按 1 + initialCapacity / 0.75 再取 2 的幂，64 个元素对应 128 个槽。sizeCtl 在首次 put 后从 128 变成 96，正好是 128 的 0.75 倍阈值。TreeBin 的 first 仍是 K0，说明链表顺序保留，树只是另建了一套 parent/left/right/red 索引。

sizeCtl 不是一个阈值

sizeCtl 是 CHM 里语义最多的字段。源码注释写得很清楚：

// JDK 25 源码摘录，已删减：ConcurrentHashMap.sizeCtl
    /**
     * Table initialization and resizing control.  When negative, the
     * table is being initialized or resized: -1 for initialization,
     * else -(1 + the number of active resizing threads).  Otherwise,
     * when table is null, holds the initial table size to use upon
     * creation, or 0 for default. After initialization, holds the
     * next element count value upon which to resize the table.
     */
    private transient volatile int sizeCtl;

把它拆成状态表：

sizeCtl 取值含义谁写入
0表未初始化，用默认容量 16构造器默认值
正数，表为 null首次初始化要用的容量构造器的 cap
正数，表非空下一次扩容的元素数阈值initTable、transfer 收尾
-1正在初始化，其他线程让出 CPUinitTable 的 CAS
< -1正在扩容，高 16 位是代数戳，低 16 位是参与线程数 + 1addCount、helpTransfer、transfer

负数的编码来自 resizeStamp：

// JDK 25 源码摘录，已删减：ConcurrentHashMap.resizeStamp
    static final int resizeStamp(int n) {
        return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
    }

RESIZE_STAMP_BITS = 16，n 是 2 的幂，numberOfLeadingZeros(n) 唯一标识这一代容量。把结果左移 16 位，低 16 位留给参与者计数。addCount 发起扩容时写入 rs + 2，每多一个帮助线程 CAS 成 sc + 1，每退出一个线程 CAS 成 sc - 1；当值退到 rs + 1，说明最后一个线程正在收尾。

本机用反射读到的生命周期如下：

== sizeCtl lifecycle (new ConcurrentHashMap<>(64)) ==
after new: sizeCtl=128 table=null
after 1 put: sizeCtl=96 table.length=128
after 48 puts: size=48 sizeCtl=96 table.length=128
after 49 puts: size=49 sizeCtl=96 table.length=128

这段输出来自下面这个只读探针。它通过反射读 table 和 sizeCtl，不修改 map：

package juc.ch05;

import java.lang.reflect.Field;
import java.util.concurrent.ConcurrentHashMap;

public final class SizeCtlProbe {
    public static void main(String[] args) throws Exception {
        ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>(64);
        System.out.printf("after new: sizeCtl=%d table=%s%n",
                sizeCtl(map), table(map) == null ? "null" : table(map).length);
        map.put("a", 1);
        System.out.printf("after 1 put: sizeCtl=%d table.length=%d%n",
                sizeCtl(map), table(map).length);
        for (int i = 1; i < 48; i++) {
            map.put("k" + i, i);
        }
        System.out.printf("after 48 puts: size=%d sizeCtl=%d table.length=%d%n",
                map.size(), sizeCtl(map), table(map).length);
        map.put("k48", 48);
        System.out.printf("after 49 puts: size=%d sizeCtl=%d table.length=%d%n",
                map.size(), sizeCtl(map), table(map).length);
    }

    static Object[] table(ConcurrentHashMap<?, ?> map) throws Exception {
        return (Object[]) field(map, "table");
    }

    static int sizeCtl(ConcurrentHashMap<?, ?> map) throws Exception {
        return (int) field(map, "sizeCtl");
    }

    static Object field(Object target, String name) throws Exception {
        Field f = ConcurrentHashMap.class.getDeclaredField(name);
        f.setAccessible(true);
        return f.get(target);
    }
}

$ javac --release 25 -d out src/juc/ch05/SizeCtlProbe.java
$ java --add-opens java.base/java.util.concurrent=ALL-UNNAMED -cp out juc.ch05.SizeCtlProbe
after new: sizeCtl=128 table=null
after 1 put: sizeCtl=96 table.length=128
after 48 puts: size=48 sizeCtl=96 table.length=128
after 49 puts: size=49 sizeCtl=96 table.length=128

用反射调用私有 tryPresize，让真实的 transfer 跑起来，再用采样线程抓负值（不是自然 put 竞争触发的扩容）：

== sizeCtl while resizing ==
sampled negative sizeCtl min=-2146959359 (0x80080001)
decode: stamp=32776 resizers=1 expected stamp=32776
after transfer: table.length=16777216 sizeCtl=12582912

0x80080001 的高 16 位是 0x8008，即 32776，对应表长 1 << 23 的 resizeStamp；低 16 位是 1，按「参与者数 + 1」的编码，此刻活跃参与者是 0，最后一个线程正在把 sizeCtl 从 rs + 2 减到 rs + 1，下一步才提交新表。最终 table.length 是 16777216，sizeCtl 是 12582912，正好是它的 0.75 倍。

这也是为什么不能用 sizeCtl > 0 判断「表已初始化」：初始化前它也可能是正数，表示待建容量；初始化后它又是阈值。判断表是否存在只看 table。

在 libraryd-conc 里落地

库存缓存 MapBackedStockCache 用 CHM 存 ISBN 到剩余库存的映射。构造时把预计 ISBN 数传给 CHM，让它一次性建好合适的表，避免上线后连续扩容；stockOf 先无锁读，未命中再用 putIfAbsent 从仓储物化。

package com.plume.conc.core;

import java.util.Optional;
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) {
        Integer cached = stock.get(isbn);
        if (cached != null) {
            return cached;
        }
        Book book = books.findByIsbn(isbn)
                .orElseThrow(() -> new LoanException(ErrorCode.BOOK_NOT_FOUND, isbn));
        Integer prior = stock.putIfAbsent(isbn, book.stock());
        return prior != null ? prior : book.stock();
    }

    public Optional<Book> find(String isbn) {
        Integer left = stock.get(isbn);
        return books.findByIsbn(isbn)
                .map(book -> new Book(book.isbn(), book.title(),
                        left == null ? book.stock() : left));
    }
}

new ConcurrentHashMap<>(expectedIsbns) 的语义是「预计放这么多元素」，内部会按 0.75 的装载密度放大再取 2 的幂。传 10 000 会得到 16 384 个槽，而不是 10 000。表是懒初始化的，构造完 table 仍是 null，第一次 putIfAbsent 才分配数组；如果服务启动后立刻有流量，这一点延迟可以忽略，但不要在请求线程里反复创建这种大表。

find 读 stock.get(isbn) 和 books.findByIsbn 两次，结果可能不是同一时刻的快照：库存刚被别的线程扣掉，返回的仍是旧值。展示型查询可以接受；下单校验必须走 5.2 的原子扣减。

这个设计的代价

  • 每个条目至少一个 Node 对象：普通 HashMap.Node 也要对象头加 hash/key/value/next 四个字段，CHM 的 Node 还带 volatile 语义；表数组本身按 2 的幂预分配。树化后每个节点再变成 TreeNode，多出 parent/left/right/prev/red 五个字段。键值对很多时，内存比 HashMap 高不少。
  • 桶锁只保护桶：hash 分布差时，所有写者挤在同一个头节点上，CHM 退化成一把锁。攻击者可以构造碰撞键做 DoS；对外接口不要直接拿用户输入当键，至少加一层前缀或改用不可预测的 ID。
  • 读无锁但不免费：get 要做 volatile 读、指针追逐，树桶还要走 TreeBin.find 的读写锁状态检查。它适合读多写少，不适合把 CHM 当本地缓存频繁扫全表。
  • 不支持 null 键和值：put(null, ...) 直接 NPE。需要表达「不存在」时用哨兵值或 Optional，不要试图存 null。
  • 什么时候不要用：需要按范围查询、需要稳定迭代顺序、需要多键事务性更新，都不该选 CHM。前两者看 6.2 的 ConcurrentSkipListMap，后者需要外部锁或换数据结构。

小结

  • CHM 的桶有四种形态：普通链表 Node、TreeBin（hash -2）、ForwardingNode（hash -1）、ReservationNode（hash -3）。
  • Node 的 hash/key 是 final，val/next 是 volatile；普通节点 hash 非负，负数留给特殊节点。
  • TreeBin 不存业务键值，只持有红黑树 root、链表 first 和寄生读写锁 lockState；树节点仍保留 next，迭代器按链表走。
  • sizeCtl 同时表示未初始化容量、扩容阈值、初始化中（-1）和扩容中（负数，高 16 位代数戳 + 低 16 位参与者数 + 1）。
  • 构造器参数是预计元素数，不是表长；new ConcurrentHashMap<>(64) 实际建 128 个槽，阈值 96。

阅读导航：上一节 4.3 Exchanger 与同步器组合 ｜ 下一节 5.2 put/get 的并发路径与 size 统计

继续阅读

探索更多技术文章

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

全部文章 返回首页

「books」更多文章

  1. 《Java 消息中间件·事件驱动架构》附录 B 架构决策记录模板
  2. 《Java 消息中间件·事件驱动架构》附录 A 术语表
  3. 《Java 消息中间件·事件驱动架构》15.3 全书验收