广州外贸网站公司网络服务商怎么咨询
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而非锁，实现高并发下的线程安全。
- 懒惰删除和协作清理：任何线程遇到“已删除节点”时都会顺手帮忙清理，避免“悬挂节点”影响性能。
- 跳表高度动态调整：插入时随机决定高度，删除时尝试降低高度，避免高度失控。
- 弱一致性遍历：迭代器弱一致，允许并发修改时遍历不会抛异常，适合高并发场景。