对企业网站的印象类似直播平台网站的建设费用
ConcurrentSkipListMap的源码很复杂,但它的核心思想和实现方式非常值得深入学习。下面会提炼出它的关键结构,并重点解释最复杂、最值得学习的方法,以及它在并发和跳表结合上的独特用法。
1. 关键结构
跳表(Skip List)基本结构
- Node<K,V>:跳表的基础节点,存储key、value和指向下一个节点的指针(next)。
 - Index<K,V>:跳表多级索引节点,存储指向下方索引(down)和右侧索引(right)的指针,每个Index节点关联一个Node节点。
 - head:顶层索引节点(Index类型),通过down可以访问到底层。
 
static final class Node<K,V> {final K key;V val;Node<K,V> next;...
}
static final class Index<K,V> {final Node<K,V> node;final Index<K,V> down;Index<K,V> right;...
}
 
其他核心成员
- comparator:可选的比较器,决定排序规则。
 - LongAdder adder:高效计数器,记录元素数量。
 - VarHandle机制:用来做原子操作,支持无锁CAS(Compare and Swap)修改指针和数据。
 
2. 并发跳表的独特实现
跳表的多层索引
-  
跳表结构使得查找、插入、删除的平均复杂度为O(log n),而且天然适合并发遍历。
 -  
索引节点(Index)和底层节点(Node)分离,每次变更都只需CAS原子操作,避免全局锁。
 
无锁设计(Lock-Free)
- 主要依赖CAS原子操作(比如 NEXT.compareAndSet、VAL.compareAndSet),避免传统锁带来的性能瓶颈。
 - 节点删除采用“懒惰删除”+“帮助删除”,即遇到被标记为删除的节点时,顺便帮忙物理移除,所有线程协作完成清理。
 
doPut(插入/更新元素)
这是插入和更新的核心方法,难点在于:
- 多线程场景下,如何安全地插入节点和建立索引;
 - 如何在概率意义下决定新节点的高度(索引层数);
 - 如何处理并发插入冲突和失败的重试。
 
简化流程:
- 找到插入位置的前驱节点(findPredecessor)。
 - 通过CAS原子操作插入新节点;
 - 按概率(1/4)决定是否生成索引节点,并逐层向上插入索引(addIndices);
 - 若有必要,增加跳表高度。
 
doPut 方法是 ConcurrentSkipListMap 的核心插入方法,实现了线程安全的键值对插入操作。以下是该方法的详细分析:
1. 方法签名与参数说明
private V doPut(K key, V value, boolean onlyIfAbsent)
 
- key: 要插入的键
 - value: 要插入的值
 - onlyIfAbsent: 如果为 
true,仅在键不存在时插入;如果为false,则替换已存在的值 - 返回值: 如果是新插入返回 
null,如果是替换则返回旧值 
整体执行流程
第一阶段:初始化检查与跳表遍历
if (key == null)throw new NullPointerException();
Comparator<? super K> cmp = comparator;
for (;;) {  // 无限循环,直到操作成功Index<K,V> h; Node<K,V> b;VarHandle.acquireFence(); // 内存屏障,确保可见性
 
关键知识点:
- 使用 无限循环 实现 乐观锁 机制
 VarHandle.acquireFence()提供 内存可见性保证,类似于 volatile 读操作
第二阶段:跳表初始化
if ((h = head) == null) {          // 跳表未初始化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; // CAS 操作
}
 
设计要点:
- 使用 哨兵节点 简化边界处理
 - 通过 CAS 操作 保证线程安全的初始化
 - 如果 CAS 失败,说明其他线程已完成初始化,重新开始循环
 
第三阶段:跳表索引层遍历
for (Index<K,V> q = h, r, d;;) { // 从顶层开始遍历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; // 继续向右elsebreak; // 找到插入位置}if ((d = q.down) != null) {++levels; // 记录下降层数q = d;    // 向下一层}else {b = q.node; // 找到基础层的前驱节点break;}
}
 
跳表遍历原理:
- 水平遍历:在当前层级向右查找,直到找到大于等于目标键的位置
 - 垂直下降:当无法继续右移时,下降到下一层级
 - 清理机制:遍历过程中清理已标记删除的节点,维护数据结构完整性
 
基础层节点插入
寻找精确插入位置
for (;;) {  // 在基础层寻找插入点Node<K,V> n, p; K k; V v; int c;if ((n = b.next) == null) {if (b.key == null)  // 空跳表,进行类型检查cpr(cmp, key, key);c = -1;}else if ((k = n.key) == null)break;  // 遇到标记节点,重新开始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;  // 找到相同键,根据 onlyIfAbsent 决定是否更新
 
执行 CAS 插入
if (c < 0 && NEXT.compareAndSet(b, n, p = new Node<K,V>(key, value, n))) {z = p;  // 记录新插入的节点break;
}
 
CAS 插入机制:
- 原子性地将新节点插入到 
b和n之间 - 如果 CAS 失败,说明其他线程修改了链表结构,需要重新查找
 
来详细解释这段看似复杂的 null 处理逻辑。这些设计都与 ConcurrentSkipListMap 的并发删除机制 密切相关。
1. 类型检查逻辑分析
if (b.key == null)       // if empty, type check key nowcpr(cmp, key, key);
 
为什么需要这个检查?
这个看似奇怪的 cpr(cmp, key, key) 调用实际上是一个 提前类型检查:
- 触发时机:当跳表为空时(
b.key == null表示b是哨兵节点) - 目的:提前验证 
key的类型是否与比较器兼容 - 机制:通过自比较触发潜在的 
ClassCastException 
// cpr 方法的实现逻辑
static int cpr(Comparator c, Object x, Object y) {return (c != null) ? c.compare(x, y) : ((Comparable)x).compareTo(y);
}
 
如果 key 类型不兼容,这里会立即抛出异常,避免在后续操作中出现问题。
2. 并发删除机制的核心区别
key == null vs val == null 的本质区别
在 ConcurrentSkipListMap 中,这两种 null 状态代表 删除过程的不同阶段:
| 状态 | 含义 | 处理方式 | 原因 | 
|---|---|---|---|
key == null | 标记节点,表示前一个节点正在被删除 | break 重新开始 | 结构不稳定,无法安全插入 | 
val == null | 逻辑删除,节点已被标记删除但仍在链表中 | unlinkNode() 物理删除 | 可以安全地完成物理删除 | 
3. 并发删除的三阶段过程
根据代码注释,ConcurrentSkipListMap 采用三阶段删除:
阶段 1:逻辑删除
// 将节点值设为 null,标记为已删除
VAL.compareAndSet(n, v, null)
 
阶段 2:插入标记节点
// 插入一个 key=null 的标记节点
NEXT.compareAndSet(n, f, new Node<K,V>(null, null, f))
 
阶段 3:物理删除
// 将前驱节点直接指向后继节点
NEXT.compareAndSet(b, n, p)
 
代码逻辑的并发安全考虑
else if ((k = n.key) == null)break;                   // can't append; restart
else if ((v = n.val) == null) {unlinkNode(b, n);c = 1;
}
 
为什么 key == null 需要重启?
- 结构不稳定:遇到标记节点说明正在进行删除操作
 - 无法预测:不知道删除何时完成,链表结构可能随时改变
 - 安全策略:重新开始遍历,等待删除操作完成
 
为什么 val == null 可以继续?
- 状态确定:节点已被逻辑删除,不会再被修改
 - 助人为乐:当前线程可以帮助完成物理删除
 - 性能优化:避免其他线程重复遇到已删除节点
 
实际执行流程示例
假设有链表:A -> B -> C,要删除节点 B:
// 初始状态
A.next -> B(key=b, val=v) -> C// 步骤1:逻辑删除 B
A.next -> B(key=b, val=null) -> C
// 此时遇到 val==null,执行 unlinkNode// 步骤2:插入标记节点
A.next -> B(key=b, val=null) -> marker(key=null, val=null) -> C
// 此时遇到 key==null,执行 break 重启// 步骤3:物理删除完成
A.next -> C
 
 
这种设计的巧妙在于:
- 渐进式删除:避免一次性操作导致的竞争
 - 协作式清理:多个线程共同维护数据结构完整性
 - 无锁设计:通过 CAS 操作保证原子性
 - 异常安全:提前进行类型检查,避免后续错误
 
这就是为什么同样是 null,但处理方式完全不同的根本原因——它们代表了并发删除过程中的不同状态,需要采用不同的应对策略来保证线程安全。
索引层构建(概率性)
随机决定是否添加索引
int lr = ThreadLocalRandom.nextSecondarySeed();
if ((lr & 0x3) == 0) {  // 1/4 概率添加索引int hr = ThreadLocalRandom.nextSecondarySeed();long rnd = ((long)hr << 32) | ((long)lr & 0xffffffffL);int skips = levels;  // 从当前层级开始构建索引
 
构建索引链
Index<K,V> x = null;
for (;;) {  // 构建垂直索引链x = new Index<K,V>(z, x, null);  // 创建新索引节点if (rnd >= 0L || --skips < 0)break;elsernd <<= 1;  // 左移判断下一层
}
 
跳表索引构建原理:
- 概率性构建:每层索引节点数量约为下层的 1/2
 - 几何分布:通过位运算实现高效的概率计算
 - 最大层数限制:最多构建 62 层索引
 
添加索引到跳表
if (addIndices(h, skips, x, cmp) && skips < 0 && head == h) {// 需要增加新的顶层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);
}
 
关键技术特性
并发安全机制
-  
Lock-Free 设计:全程无锁,使用 CAS 操作保证原子性
 -  
内存屏障:使用
VarHandle.acquireFence()确保内存可见性 -  
重试机制:失败时重新开始,保证最终一致性
 
性能优化策略
-  
惰性删除:标记删除而非立即物理删除
 -  
清理机制:遍历过程中顺便清理已删除节点
 -  
概率性索引:平衡查找效率和空间开销
 
数据结构维护
- 动态层级调整:根据需要增加新的索引层
 - 索引一致性:确保索引层与基础层数据一致
 - 并发清理:在操作过程中维护结构完整性
 
为什么需要标记节点?并发链表删除的根本问题
详细解释为什么ConcurrentSkipListMap不能"直接CAS删除",而必须使用标记节点的分步删除策略。
如果我们尝试"直接删除":
// 危险的直接删除方式
NEXT.compareAndSet(A, B, C);  // 直接让A指向C
 
这会导致严重的并发竞态条件:
// 初始状态
A -> B -> C -> D// 线程T1想删除B,读取了B.next = C
// 线程T2在B和C之间插入了新节点X
A -> B -> X -> C -> D// T1执行CAS:A.next从B改为C
A -> C -> D  // X节点永远丢失!
 
unlinkNode的三步删除策略
查看unlinkNode的实现:
static <K,V> void unlinkNode(Node<K,V> b, Node<K,V> n) {if (b != null && n != null) {Node<K,V> f, p;for (;;) {if ((f = n.next) != null && f.key == null) {p = f.next;               // 步骤1:发现已有标记节点break;}else if (NEXT.compareAndSet(n, f,new Node<K,V>(null, null, f))) {p = f;                    // 步骤2:插入标记节点break;}}NEXT.compareAndSet(b, n, p);      // 步骤3:绕过被删节点}
}
 
 
为什么分步删除是必需的?
无锁并发的本质需求
- 原子性保证:每个CAS操作都是原子的,但组合操作不是
 - 顺序依赖:必须先"锁定"被删节点的next指针,再修改前驱节点
 - 状态可见性:中间状态必须对所有线程可见和可处理
 
对比有锁方案
// 如果用锁(但ConcurrentSkipListMap是无锁的)
synchronized(lock) {A.next = B.next;  // 可以原子完成
}
 
但无锁环境下,我们只能依赖CAS的原子性,因此必须分解为原子步骤。
实际运行示例
// 时刻T1:初始状态
A.next -> B(key=5, val="hello") -> C(key=10)// 时刻T2:线程1开始删除B,执行逻辑删除
A.next -> B(key=5, val=null) -> C(key=10)// 时刻T3:线程2试图在B后插入节点失败
// 因为发现B.val==null,执行unlinkNode帮助删除// 时刻T4:插入标记节点
A.next -> B(key=5, val=null) -> marker(key=null, val=null) -> C(key=10)// 时刻T5:物理删除完成
A.next -> C(key=10)
 
findPredecessor(查找前驱节点)
- 负责自顶向下查找,过程中顺便帮忙清理已删除节点的索引,保证跳表结构整洁。
 - 支持并发删除时的“协作清理”。
 
核心逻辑:
    private Node<K,V> findPredecessor(Object key, Comparator<? super K> cmp) {Index<K,V> q;VarHandle.acquireFence();if ((q = head) == null || key == null)return null;else {for (Index<K,V> r, d;;) {while ((r = q.right) != null) {Node<K,V> p; K k;if ((p = r.node) == null || (k = p.key) == null ||p.val == null)  // unlink index to deleted nodeRIGHT.compareAndSet(q, r, r.right);else if (cpr(cmp, key, k) > 0)q = r;elsebreak;}if ((d = q.down) != null)q = d;elsereturn q.node;}}} 
 
VarHandle.acquireFence() 的作用
VarHandle.acquireFence() 在此处的作用是:
- 保证可见性:确保读取到其他线程对 
head字段的最新修改 - 防止重排序:确保后续的读操作基于一致的内存状态
 - 性能优化:避免使用过多 volatile 字段的开销
 - 维护弱一致性:为无锁数据结构提供必要的内存语义保证
 
这是 ConcurrentSkipListMap 实现高性能并发访问的关键技术之一。
acquireFence()确保在屏障之后的所有读操作不会被重排序到屏障之前, 主要用于确保读取操作能看到最新的写入值,是构建更高级并发原语的基础工具。releaseFence(): 确保屏障之前的所有写操作对其他线程可见(类似于StoreStore+LoadStore)fullFence(): 同时提供获取和释放语义(类似于volatile变量的读写)
内存屏障的核心作用
1. 确保 head 字段的最新值可见
VarHandle.acquireFence();
if ((q = head) == null || key == null)return null;
 
关键问题:head 字段可能被其他线程修改(如在 doPut、tryReduceLevel 等方法中),需要确保当前线程能看到最新的值。
解决方案:acquireFence() 提供了类似 volatile 读 的语义,确保:
- 读取到 
head的最新值 - 防止编译器和处理器的指令重排序
 
2. 建立 happens-before 关系
根据代码注释中的设计说明:
This form of fence-hoisting is similar to RCU and related techniques... It minimizes overhead that may otherwise occur when using so many volatile-mode reads.
设计思路:
- 避免将每个字段都声明为 
volatile - 通过在关键方法入口处放置内存屏障,建立全局的内存可见性保证
 
为什么选择 acquireFence 而非其他屏障
acquireFence 的特性
// acquireFence 等价于:
// 确保屏障之前的读操作不会被重排序到屏障之后
// 提供 "acquire" 语义,类似于 volatile 读或 synchronized 进入
 
与 ConcurrentSkipListMap 的无锁设计契合
- 无锁遍历:
findPredecessor是纯读操作,不需要修改数据 - 弱一致性:允许看到稍微过时的数据,但必须是一致的快照
 - 性能优化:比使用多个 volatile 字段开销更小
 
场景分析
场景 1:读取跳表头节点
// 其他线程可能正在执行:
HEAD.compareAndSet(this, h, nh);  // 在 doPut 中更新头节点// 当前线程需要确保看到最新的 head 值
VarHandle.acquireFence();
if ((q = head) == null || key == null)  // 必须是最新值
 
场景 2:确保索引结构一致性
// 确保读取的索引链是一致的状态
while ((r = q.right) != null) {Node<K,V> p; K k;// 这些字段的读取都受到屏障保护if ((p = r.node) == null || (k = p.key) == null || p.val == null)
 
对比其他方法中的类似用法
可以看到相同的模式:
doGet方法:
VarHandle.acquireFence();
if (key == null)throw new NullPointerException();
 
findLast方法:
VarHandle.acquireFence();
if ((q = head) == null)break;
 
 
 
doRemove(删除元素)
- 先逻辑删除(将val设为null),再插入一个“marker”节点做物理删除,最后CAS更新前驱的next指针。
 - 删除后会考虑是否需要降低跳表高度(tryReduceLevel)。
 
    /*** Main deletion method. Locates node, nulls value, appends a* deletion marker, unlinks predecessor, removes associated index* nodes, and possibly reduces head index level.** @param key the key* @param value if non-null, the value that must be* associated with key* @return the node, or null if not found*/final V doRemove(Object key, Object value) {if (key == null)throw new NullPointerException();Comparator<? super K> cmp = comparator;V result = null;Node<K,V> b;outer: while ((b = findPredecessor(key, cmp)) != null &&result == null) {for (;;) {Node<K,V> n; K k; V v; int c;if ((n = b.next) == null)break outer;else if ((k = n.key) == null)break;else if ((v = n.val) == null)unlinkNode(b, n);else if ((c = cpr(cmp, key, k)) > 0)b = n;else if (c < 0)break outer;else if (value != null && !value.equals(v))break outer;else if (VAL.compareAndSet(n, v, null)) {result = v;unlinkNode(b, n);break; // loop to clean up}}}if (result != null) {tryReduceLevel();addCount(-1L);}return result;} 
 
 
doRemove 方法是 ConcurrentSkipListMap 中的核心删除实现,它完美体现了之前提到的三阶段删除策略。
这个方法实现了无锁并发删除,支持两种删除模式:
- 精确删除:
value != null时,只有当节点值完全匹配时才删除 - 键删除:
value == null时,删除指定键的节点(不关心值) 
核心执行流程
外层循环:定位目标节点
outer: while ((b = findPredecessor(key, cmp)) != null && result == null) {
 
关键设计:
- 使用 
findPredecessor找到目标键的前驱节点 - 外层循环处理并发冲突重试
 result == null确保删除成功后不再重试
内层循环:执行删除操作
内层循环处理多种并发场景,每个分支对应不同的节点状态:
场景1:链表结束
if ((n = b.next) == null)break outer;
 
-  
前驱节点后没有节点,目标不存在
 
场景2:遇到标记节点
else if ((k = n.key) == null)  break;
 
-  
遇到
key == null的标记节点 -  
表示链表结构正在变化,需要重新开始
 
场景3:遇到已删除节点
else if ((v = n.val) == null)unlinkNode(b, n);
 
-  
遇到
val == null的逻辑删除节点 -  
助人为乐:帮助完成物理删除
 
场景4:继续搜索
else if ((c = cpr(cmp, key, k)) > 0)b = n;
 
-  
目标键更大,向后移动搜索
 
场景5:目标不存在
else if (c < 0)break outer;
 
-  
目标键更小,说明不存在该键
 
场景6:值不匹配(精确删除)
else if (value != null && !value.equals(v))break outer;
 
-  
键匹配但值不匹配,删除失败
 
场景7:执行删除(核心逻辑)
else if (VAL.compareAndSet(n, v, null)) {result = v;unlinkNode(b, n);break;
}
 
三阶段删除的具体实现
阶段1:逻辑删除
VAL.compareAndSet(n, v, null)
 
- 原子操作:将节点值设为 null
 - 标记删除:其他线程看到 
val == null知道节点已删除 - CAS失败重试:如果失败说明有并发修改,继续循环
 
阶段2+3:物理删除
unlinkNode(b, n);
 
调用 unlinkNode 完成后续的标记节点插入和链表断开。
删除后的清理工作
if (result != null) {tryReduceLevel();     // 尝试减少跳表层级addCount(-1L);        // 更新元素计数
}
 
虽然 doRemove 没有直接清理索引,但通过以下机制保证索引一致性:
- 遍历时清理:其他方法(如 
findPredecessor、doGet)遍历时会清理指向已删除节点的索引 - 层级缩减:
tryReduceLevel()在顶层索引为空时减少跳表高度 
unlinkNode 方法详解
 
unlinkNode 方法是 ConcurrentSkipListMap 实现中用于物理删除节点的关键方法。
unlinkNode 方法的主要任务是将已逻辑删除的节点(val == null)从链表中完全移除。它通过以下步骤实现:
- 插入标记节点:在删除节点的 
next指针上插入一个标记节点,防止其他线程向该节点追加新节点。 - 断开前驱节点:将前驱节点的 
next指针直接指向删除节点的后继节点,完成物理删除。 
    /*** Tries to unlink deleted node n from predecessor b (if both* exist), by first splicing in a marker if not already present.* Upon return, node n is sure to be unlinked from b, possibly* via the actions of some other thread.** @param b if nonnull, predecessor* @param n if nonnull, node known to be deleted*/static <K,V> void unlinkNode(Node<K,V> b, Node<K,V> n) {if (b != null && n != null) {Node<K,V> f, p;for (;;) {if ((f = n.next) != null && f.key == null) {p = f.next;               // already markedbreak;}else if (NEXT.compareAndSet(n, f,new Node<K,V>(null, null, f))) {p = f;                    // add markerbreak;}}NEXT.compareAndSet(b, n, p);}} 
核心执行流程
1. 检查参数
if (b != null && n != null) {
 
-  
确保
b(前驱节点)和n(要删除的节点)不为空。 
2. 插入标记节点
Node<K,V> f, p;
for (;;) {if ((f = n.next) != null && f.key == null) {p = f.next;               // already markedbreak;}else if (NEXT.compareAndSet(n, f, new Node<K,V>(null, null, f))) {p = f;                    // add markerbreak;}
}
 
- 检查是否已标记:如果删除节点的 
next指针指向的节点key为null,说明已经有一个标记节点存在。 - 插入新标记节点:如果 
next指针没有标记节点,则使用NEXT.compareAndSet原子操作插入一个新的标记节点。 
3. 断开前驱节点
NEXT.compareAndSet(b, n, p);
 
- 将前驱节点 
b的next指针指向删除节点的后继节点p,完成物理删除。 
总结
结合并发与跳表的独特之处
- 极致的无锁化设计:所有节点和索引的增删都用CAS而非锁,实现高并发下的线程安全。
 - 懒惰删除和协作清理:任何线程遇到“已删除节点”时都会顺手帮忙清理,避免“悬挂节点”影响性能。
 - 跳表高度动态调整:插入时随机决定高度,删除时尝试降低高度,避免高度失控。
 - 弱一致性遍历:迭代器弱一致,允许并发修改时遍历不会抛异常,适合高并发场景。
 
