承接的问题
ConcurrentHashMap 解决了并发读写，但它的键是无序的：没有 firstKey、没有 subMap、没有 ceilingKey。需要“按 ISBN 区间出一份在架清单”或“找到下一个不小于给定 ISBN 的书目”时，CHM 只能把所有键捞出来排序，一次查询就是 O(n log n)。
能保持有序的经典结构是红黑树，但 TreeMap 完全不是线程安全的，Collections.synchronizedSortedMap 又把整棵树压在一把锁下。要在有序结构上做细粒度并发，JDK 的选择是跳表（skip list）：ConcurrentSkipListMap 与 ConcurrentSkipListSet。
本节回答三个问题：跳表的索引在 JDK 25 里长什么样；插入为什么能只靠 CAS；“有序 + 并发”为什么落到跳表而不是平衡树。
先说我踩过的坑。绝大多数中文资料（包括不少面试笔记）描述的是 JDK 8 的实现，那里有 HeadIndex 和 level 字段。本机用 Zulu 8u482 核对：
Compiled from "ConcurrentSkipListMap.java" // Zulu 8u482，javap -p
private static final java.lang.Object BASE_HEADER;
private volatile transient java.util.concurrent.ConcurrentSkipListMap$HeadIndex<K, V> head;
private static final sun.misc.Unsafe UNSAFE;
final class java.util.concurrent.ConcurrentSkipListMap$HeadIndex<K, V> extends java.util.concurrent.ConcurrentSkipListMap$Index<K, V> {
final int level;
}
JDK 25 里 HeadIndex 与 level 都不存在了。本机 javap -p 的真实输出：
Compiled from "ConcurrentSkipListMap.java" // Temurin 25.0.5+8，javap -p
public class java.util.concurrent.ConcurrentSkipListMap<K, V> extends java.util.AbstractMap<K, V> implements java.util.concurrent.ConcurrentNavigableMap<K, V>, java.lang.Cloneable, java.io.Serializable {
private static final long serialVersionUID;
final java.util.Comparator<? super K> comparator;
private transient java.util.concurrent.ConcurrentSkipListMap$Index<K, V> head;
private transient java.util.concurrent.atomic.LongAdder adder;
private transient java.util.concurrent.ConcurrentSkipListMap$KeySet<K, V> keySet;
private transient java.util.concurrent.ConcurrentSkipListMap$Values<K, V> values;
private transient java.util.concurrent.ConcurrentSkipListMap$EntrySet<K, V> entrySet;
private transient java.util.concurrent.ConcurrentSkipListMap$SubMap<K, V> descendingMap;
private static final int EQ;
private static final int LT;
private static final int GT;
private static final java.lang.invoke.VarHandle HEAD;
private static final java.lang.invoke.VarHandle ADDER;
private static final java.lang.invoke.VarHandle NEXT;
private static final java.lang.invoke.VarHandle VAL;
private static final java.lang.invoke.VarHandle RIGHT;
两处变化值得记一笔。head 从 HeadIndex 降级成普通 Index，并且不再是 volatile：可见性由方法入口的 VarHandle.acquireFence() 加 HEAD 句柄的 CAS 提供，这是把屏障“上提到循环入口”的做法，源码注释称之为 fence-hoisting，思路接近 RCU。计数则是从无到有：JDK 8 的 size() 是沿底层链表逐个数，复杂度 O(n)，本机 javap -c 能看到它 findFirst 之后一个 goto 循环累加；JDK 25 改用 LongAdder（第 8 章讲它为什么分片）。sun.misc.Unsafe 也全部换成了 VarHandle。
结构：三层指针，层数不在字段里
跳表只有两种节点。先看源码（两段合在一起，各自完整）：
// JDK 25 源码摘录，已删减
static final class Node<K,V> {
final K key; // currently, never detached
V val;
Node<K,V> next;
Node(K key, V value, Node<K,V> next) {
this.key = key;
this.val = value;
this.next = next;
}
}
static final class Index<K,V> {
final Node<K,V> node; // currently, never detached
final Index<K,V> down;
Index<K,V> right;
Index(Node<K,V> node, Index<K,V> down, Index<K,V> right) {
this.node = node;
this.down = down;
this.right = right;
}
}
Node 是底层有序单链表，key 是 final（删除时不摘键，只把 val 置空），next 可变。Index 是索引节点：node 指向它代言的数据节点，down 指向下一层的同名索引，right 指向本层右侧的下一个索引。down 与 node 都是 final，只有 right 会被 CAS 修改——这是整个设计的关键约束：索引的增删永远只改一个 right 指针。
那么“层数”存在哪？答案是：不存在。head 是最顶层的那个 Index，从它沿着 down 一路走下去的步数就是总层数。JDK 8 用一个 HeadIndex.level 字段显式记录，JDK 25 把这个信息编码进了链的形状里。加一层不再需要“修改 head 的 level”，而是用一个新的 head 把旧 head 包起来。写法在 doPut 的尾部（本节后面会引用）：new Index<>(h.node, h, hx) 造一个新 head，它的 node 还是那个哑头节点，down 指向旧 head，right 指向新层的第一个索引，最后一次 CAS 把 head 从 h 换成 nh。一次 CAS 就完成“长高一层”，旧 head 完好无损，正在读它的线程不受影响。
降层由 tryReduceLevel() 反向操作：最上面三层都空才 CAS 把 head 下移一格，下移后立刻再检查旧 head 是否被别人挂了新索引，是就马上 CAS 回去。源码注释承认这个回滚“in practice appears to be a better option than allowing unrestrained growth of levels”——它不是一个严格正确的算法，而是概率上极难出错的启发式；代价是可能短暂“丢掉”一层，影响性能不影响正确性。
本机用反射读 head，沿 down 数层数、沿每层 right 数索引节点、沿底层 next 数数据节点（完整程序在本书配套的 skip-shape 实验里，运行时必须加 --add-opens java.base/java.util.concurrent=ALL-UNNAMED）。本机输出：
== 结构（n=100000，JDK 25.0.5+8-LTS）
层数 14，索引节点 50733，基链节点 100000（含哑头 true）
索引节点/总节点 = 0.337
100000 个键对应 14 层，索引节点占 33.7%。这两个数都能从源码里的参数推出来：(lr & 0x3) == 0 意味着 1/4 的节点会建索引；每一层是否继续向上由随机数的下一位决定（约 1/2），所以一个被索引的节点平均有 2 层索引。于是一个节点有索引的概率是 1/4，期望索引层数是 2，索引节点数 ≈ n × 1/2，占比 ≈ 0.5 / 1.5 = 1/3。实测 0.337，对得上。层数 14 也与 log₂(100000) ≈ 16.6 的量级一致。
插入：先挂底层，再补索引
doPut 是全书最长的方法之一，但骨架只有一段：先爬到目标层，再在底层插入，最后回头补索引。
// JDK 25 源码摘录，已删减
private V doPut(K key, V value, boolean onlyIfAbsent) {
if (key == null)
throw new NullPointerException();
Comparator<? super K> cmp = comparator;
for (;;) {
Index<K,V> h; Node<K,V> b;
VarHandle.acquireFence();
int levels = 0; // number of levels descended
if ((h = head) == null) { // try to initialize
Node<K,V> base = new Node<K,V>(null, null, null);
h = new Index<K,V>(base, null, null);
b = (HEAD.compareAndSet(this, null, h)) ? base : null;
}
else {
for (Index<K,V> q = h, r, d;;) { // count while descending
while ((r = q.right) != null) {
Node<K,V> p; K k;
if ((p = r.node) == null || (k = p.key) == null ||
p.val == null)
RIGHT.compareAndSet(q, r, r.right);
else if (cpr(cmp, key, k) > 0)
q = r;
else
break;
}
if ((d = q.down) != null) {
++levels;
q = d;
}
else {
b = q.node;
break;
}
}
}
if (b != null) {
到这里为止是“定位”阶段：b 是底层的前驱节点，levels 是爬下来的层数。接下来是底层插入：
// JDK 25 源码摘录，已删减
Node<K,V> z = null; // new node, if inserted
for (;;) { // find insertion point
Node<K,V> n, p; K k; V v; int c;
if ((n = b.next) == null) {
if (b.key == null) // if empty, type check key now
cpr(cmp, key, key);
c = -1;
}
else if ((k = n.key) == null)
break; // can't append; restart
else if ((v = n.val) == null) {
unlinkNode(b, n);
c = 1;
}
else if ((c = cpr(cmp, key, k)) > 0)
b = n;
else if (c == 0 &&
(onlyIfAbsent || VAL.compareAndSet(n, v, value)))
return v;
if (c < 0 &&
NEXT.compareAndSet(b, n,
p = new Node<K,V>(key, value, n))) {
z = p;
break;
}
}
① 外层 for (;;) 是唯一的重试机制。整段没有 synchronized、没有 tryLock、没有超时；失败（CAS 输给别人、遇到 marker、头节点被别人抢先建好）就回起点重来，这是无锁算法的标准形态：重试代替阻塞。注意内层那个 for (;;) 是“沿底层向右走”，不是重试——break 才代表放弃并回到外层。② levels 记录从顶层爬到底层经过了几层，后面要用它决定新索引从哪一层开始补，是“索引高度与数据插入位置对齐”的依据。
③ 头节点是懒初始化的，用 HEAD 句柄 CAS 一个“哑头节点 + 顶层 Index”，竞争失败的一方拿到 b = null，跳过后面的 if (b != null) 回到 ① 重来。④ 查找阶段只走索引层：while (r = q.right) 向右走到不能再走，down 下一层继续。这里有一个顺手做的清理：如果右邻居的 node/key/val 有任何一个是 null（已被删除或只是索引残骸），就用 CAS 把 q.right 直接跨过它。遍历路径顺便帮别人收尸，这是无锁结构里 helping 的典型手法，避免删除者挂掉后整个结构卡住。
⑤ 底层插入是纯 CAS：NEXT.compareAndSet(b, n, new Node<>(key, value, n))。三个分支各有含义：n == null 表示 b 已是链尾，c = -1 触发追加；k == null 表示撞上了删除 marker，break 回外层重来；v == null 表示 n 已被别人删除，先帮忙 unlinkNode 再继续。键相等时走 onlyIfAbsent || VAL.compareAndSet(n, v, value)，putIfAbsent 与 put 的差别就落在这一行。成功后才会进入索引阶段：
// JDK 25 源码摘录，已删减
if (z != null) {
int lr = ThreadLocalRandom.nextSecondarySeed();
if ((lr & 0x3) == 0) { // add indices with 1/4 prob
int hr = ThreadLocalRandom.nextSecondarySeed();
long rnd = ((long)hr << 32) | ((long)lr & 0xffffffffL);
int skips = levels; // levels to descend before add
Index<K,V> x = null;
for (;;) { // create at most 62 indices
x = new Index<K,V>(z, x, null);
if (rnd >= 0L || --skips < 0)
break;
else
rnd <<= 1;
}
if (addIndices(h, skips, x, cmp) && skips < 0 &&
head == h) { // try to add new level
Index<K,V> hx = new Index<K,V>(z, x, null);
Index<K,V> nh = new Index<K,V>(h.node, h, hx);
HEAD.compareAndSet(this, h, nh);
}
if (z.val == null) // deleted while adding indices
findPredecessor(key, cmp); // clean
}
addCount(1L);
return null;
}
这段代码里有四个精确的数字：
(lr & 0x3) == 0：只有 1/4 的插入会建索引。源码注释称之为k=1, p=0.5的稀疏索引，意思是每 1 个节点里平均只有 1/4 上索引，比教科书跳表的 p=0.5 更稀，为的是省内存。rnd >= 0L：用 64 位随机数判断最高位。每判断一次失败就rnd <<= 1，等价于“再抛一次硬币”，所以层高服从几何分布，期望 2 层。--skips < 0与 62 层上限：skips初值是levels，表示前levels层不建索引（因为那些层的索引已经在查找路径上被“跳过”了），超过后才逐层向上补。上限 62 对应 2⁶² 个元素，实际上永远碰不到。if (z.val == null)：索引建好之后发现数据节点已经被别人删了，立刻调findPredecessor清理残留索引。索引是“尽力而为”的缓存，数据才是真相。
补索引的 addIndices 是递归的：先在本层找到拼接点，x.right = r 后 CAS RIGHT，成功则返回 true 让调用方向上层递归；失败则把 retrying 置位、重新找拼接点。索引补失败不是错误——源码注释的原话是“even when this happens, the index lists correctly guide search. This can impact performance, but since skip lists are probabilistic anyway…”。少一层索引只是搜索路径变长，键值绝不会丢。
删除走的是另一套三步协议：先 VAL.compareAndSet(n, v, null) 把值置空宣告死亡，再在 n 后面插入一个 key == null 的 marker，最后 NEXT.compareAndSet(b, n, p) 把前驱直接连到 marker 之后。任何线程在遍历时看到 val == null 都会帮忙调 unlinkNode，看到 key == null 就知道遇上了 marker、必须重来。这是 Harris/Michael 的无锁链表删除法，跳表只是给它加了一层索引。
为什么有序容器是跳表，不是红黑树
这是本节最值得记的一问：红黑树在单线程下更快、更省内存，为什么并发版本没人用？答案在“一次原子写能改多少东西”。并发正确性要求每个结构变化都能用一次 CAS 完成，或者至少能被别的线程安全地观察到中间态。红黑树的插入要旋转：一次旋转会同时改父子三个节点的 left/right/parent，再加颜色位。这些指针必须在同一个原子步里一起生效，而 CAS 一次只能比较并交换一个机器字。你没法用一次 CAS 完成旋转，于是只剩两条路：要么给整棵树加锁（退化成 synchronizedSortedMap），要么引入复杂得多的事务性内存或锁耦合（lock coupling，读的时候一路加锁一路放锁，写的时候持有父节点锁）。后者的实现复杂度和常数开销都远超跳表。
跳表把这个问题消掉了：结构变化永远只改一个 right 指针或一个 next 指针。插入数据节点是一次 CAS；补一个索引是一次 CAS；长高一层是一次 CAS。索引允许暂时缺失、允许重复遍历同一个节点、允许指向已删除节点的残骸——所有这些“不一致”都只影响性能，不影响正确性。这种“允许局部退化”的宽容度，正是无锁算法最稀缺的性质。
代价也很清楚。用同一批 10 万个键，本机统计三种结构的节点数与结构内存：
TreeMap 节点数 = 100000
粗估结构内存：skip 4710 KB，TreeMap 3906 KB
CHM 节点 100000，表长 262144，粗估 4149 KB（表数组按 4B/槽）
粗估口径：Node/Index 各按 32 字节（16 字节对象头 + 3 个 4 字节引用，对齐到 32），TreeMap.Entry 按 40 字节（多一个 parent 引用和一个 boolean），CHM 另加表数组 4 字节/槽。结论是跳表比 TreeMap 多约 20% 的结构开销（那 5 万个索引节点），与 CHM 大致同级。类注释里写的是“slightly less than for the current implementation of java.util.TreeMap”，本机实测是略多——统计口径（是否计入哑头与数组）和 Entry 布局都会影响这个比较，量级上三者可以认为同档。
读写性能的差距更悬殊。本机同一进程内对比（每次运行前重建 10 万键，三轮取稳定值）：
== 单点查找 ns/次
skip 596.8 ns/次 chm 80.1 ns/次
skip 384.5 ns/次 chm 21.9 ns/次
skip 357.1 ns/次 chm 20.5 ns/次
== 1000 次区间求和（宽度 300），us/次
skip 6.2 us/次 chm 771.4 us/次
skip 2.4 us/次 chm 607.3 us/次
单点查找跳表比 CHM 慢 10–20 倍：跳表要走 14 层、每层比较一次，是十几次跨对象的指针追逐，几乎每次都是缓存缺失；CHM 一次哈希、一次数组下标。这是结构决定的，不是实现粗糙。但区间查询反过来差两个数量级：跳表用 subMap 定位到起点后顺着底层链表走，代价是 O(log n + k)；CHM 没有顺序，只能全量遍历、过滤、排序，代价是 O(n log n)。1000 次宽 300 的区间求和，跳表 2–6 微秒，CHM 600–840 微秒，约 200 倍。这两个数字加起来就是选型结论：只要查询里出现“范围”“前驱后继”“有序遍历”，就用跳表，即使单点会慢一个量级；如果只有单点查，CHM 完胜。
什么时候不要用 ConcurrentSkipListMap？一，只做点查、从不需要顺序——用 CHM，能省一个数量级的延迟。二，键不可比较或比较很贵（compareTo 里有字符串解析、正则、远程调用）——每次查找要做十几次比较，成本被放大。三，不能接受 null 键：doPut/doGet 第一行就是 if (key == null) throw new NullPointerException()。四，内存极度敏感且元素上千万——索引节点多出 33%。五，只需要“最小/最大”而不需要任意区间——用一个 AtomicReference 加 CAS 维护极值更便宜。
在 libraryd-conc 里落地
conc-core 的书目目录需要三个能力：按 ISBN 精确找书、按 ISBN 区间出一份清单、找“下一个不小于给定 ISBN 的书”。后两个能力直接排除 CHM，所以用 ConcurrentSkipListMap，并且只用它一个——点查也走它，虽然慢一点，但避免了双写（6.3 会算这笔账）。
package com.plume.conc.core;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.concurrent.ConcurrentSkipListMap;
/** 按 ISBN 有序的书目目录。键是 ISBN 字符串，排序即字典序。 */
public final class ShelfCatalog {
private final ConcurrentSkipListMap<String, Book> byIsbn =
new ConcurrentSkipListMap<>();
public void put(Book book) { byIsbn.put(book.isbn(), book); }
public boolean remove(String isbn) { return byIsbn.remove(isbn) != null; }
public Book findByIsbn(String isbn) { return byIsbn.get(isbn); }
/** 区间清单：左闭右开，结果按 ISBN 升序。 */
public List<Book> range(String fromIsbn, String toIsbn) {
return new ArrayList<>(byIsbn.subMap(fromIsbn, true, toIsbn, false).values());
}
/** 下一本“不小于”给定 ISBN 的书；没有就返回 null。 */
public Book nextAtOrAfter(String isbn) {
Map.Entry<String, Book> e = byIsbn.ceilingEntry(isbn);
return e == null ? null : e.getValue();
}
public Book first() { return byIsbn.isEmpty() ? null : byIsbn.firstEntry().getValue(); }
public int size() { return byIsbn.size(); }
}
四个 API 的语义要点。subMap(from, true, to, false) 的区间是左闭右开，写调用点时最好把 true/false 显式写出来，别用 subMap(from, to) 那个默认左闭右开的简写——读者一眼看不出边界。ceilingEntry 返回“大于等于”的第一个条目，floorEntry 是“小于等于”，higher/lower 是严格不等，这四个方法在库存补货、书架定位这类场景里非常好用。size() 现在是 LongAdder.sum()，源码里有 if ((c = a.sum()) <= 0L) return 0L 的兜底，因为并发删除时可能短暂出现负数。
下面这段验证并发写入不丢数据，可以独立运行：
import java.util.concurrent.ConcurrentSkipListMap;
import java.util.concurrent.CountDownLatch;
public final class ConcSkipProbe {
public static void main(String[] args) throws Exception {
final int threads = 8, perThread = 25_000;
long expected = (long) threads * perThread;
ConcurrentSkipListMap<Integer, Integer> map = new ConcurrentSkipListMap<>();
CountDownLatch start = new CountDownLatch(1), done = new CountDownLatch(threads);
for (int t = 0; t < threads; t++) {
final int base = t * perThread;
Thread.ofPlatform().start(() -> {
try {
start.await();
for (int i = 0; i < perThread; i++) map.put(base + i, base + i);
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
} finally { done.countDown(); }
});
}
start.countDown();
done.await();
int prev = -1; boolean ordered = true; long sum = 0;
for (int k : map.keySet()) {
if (k <= prev) { ordered = false; break; }
prev = k; sum += map.get(k);
}
System.out.println("size=" + map.size() + " 期望=" + expected);
System.out.println("firstKey=" + map.firstKey() + " lastKey=" + map.lastKey());
System.out.println("严格升序=" + ordered);
System.out.println("值求和=" + sum + " 期望=" + (expected * (expected - 1) / 2));
}
}
本机输出：
size=200000 期望=200000
firstKey=0 lastKey=199999
严格升序=true
值求和=19999900000 期望=19999900000
20 万次并发 put 既不丢也不重，遍历顺序严格递增。
常见错误与边界
第一，把 size() 当精确值做业务判断。它底层是 LongAdder，并发下是估算；isEmpty() 有专门的快速路径，判断“有没有”用它而不是 size() == 0。
第二，以为索引是权威数据。索引可能缺失、可能指向已删除节点、可能暂时指错；所有判断都必须落到数据节点上。这也是为什么 doGet 命中索引后还要再读 p.val。
第三，用可变对象做键，或者键的 compareTo 与 equals 不一致。跳表靠 compareTo 定位，equals 完全不参与；两者不一致会出现“get 找不到但遍历能看到”的怪事。CHM 没这个问题，它只看 hashCode/equals。
第四，以为遍历是强一致的。keySet()、entrySet() 的迭代器是弱一致的：不抛 CME，能看到遍历开始后的部分修改，也可能看不到。要一份稳定视图就 new ArrayList<>(map.values()) 拷出来。
第五，忽略 comparator 字段的可见性。它声明为包级 final Comparator<? super K> comparator（不是 private），因为嵌套类要直接读；这不是给你用的 API，别想着通过反射去换比较器。
第六，拿 JDK 8 的 HeadIndex/level 去读 JDK 25 的调试器视图。层数现在只能靠 down 链长度数出来，level 字段已经不存在了。
小结
ConcurrentSkipListMap 用一层稀疏索引（1/4 的节点、平均 2 层、上限 62 层）把底层有序链表加速到期望 O(log n)，用 Node.next、Index.right、HEAD 三个 CAS 点覆盖了插入、删除、长高的全部结构变化，并且刻意容忍索引缺失与残骸——因为容忍换来了无锁。JDK 25 去掉了 HeadIndex 与 level，把层数编码进 head 的 down 链，加层就是“用新 head 包住旧 head”。它比 TreeMap 多约 20% 内存，点查比 CHM 慢一个数量级，但区间查询快两个数量级。
有序，就是这个容器存在的唯一理由。下一节把 CHM、跳表、COW 放进同一张矩阵，回答“到底该选哪个”。
阅读导航：上一节 6.1 CopyOnWriteArrayList/Set ｜ 下一节 6.3 并发集合选型矩阵
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。