背景与痛点

在被 Redis 版的跳表实现折磨了 20 多天 之后终于在元宝的帮助下完成了自己的简易版实现。整个过程充满了抽象的迷雾——每一次思考都像是抓住了一根线，却又永远无法完全握紧。没有元宝的指引，我几乎不可能在这段时间内突破。更别说真正把跳表的全貌呈现出来了。

如果你也想学习 Redis 版的跳表，请务必仔细阅读以下注释。这些都是我在 20 多天血泪交织中留下的痕迹，能为你的学习提供实质性的帮助。怎么说呢，

主要实现思路

1️⃣ 数据结构设计

我们使用 Node 保存键值对。并通过一个固定长度的指针数组 next 实现多层索引。头结点 head 永远不变，负责管理所有层级。

2️⃣ 随机层级生成

采用经典的几何分布：

private int randomLevel {
int level = 1;while 

这一步决定了节点在跳表中的高度，也是保证平均 O 性能的关键。

3️⃣ 插入操作

痛点：最初我在遍历和更新指针时总是陷入「指针数组下标错位」的死循环。甚至一度放弃游戏、种田，只想逃离这段抽象代码。最终，我通过以下步骤理清思路：

1. 从最高层向下寻找每层的前驱节点。记录在 update 中。
2. 如果键已存在仅更新值。
3. 若键不存在根据随机层级创建新节点，并使用 update 完成多层指针的插入。

4️⃣ 删除操作（remove)

痛点：删除逻辑最难理解，因为它涉及到“当前节点已经是目标节点”的概念。如果没有正确使用 update。删除后会导致链路断裂，甚至出现层高不一致的问题。下面是关键实现：

for {
update.next = current.next;}
// 调整层高
for {
if {
currentLevel = i;break，}
}

完整代码实现

package test;import java.util.concurrent.*;import java.util.*;public class MyConcurrentSkipListMapTest {
public static void main throws Exception {
System.out.println;System.out.println;basicTest，System.out.println;concurrentPutTest;System.out.println;concurrentMixedTest;System.out.println;performanceTest;}
/** 基本功能验证 */
static void basicTest {
MyConcurrentSkipListMap map = new MyConcurrentSkipListMap<>;// 插入
System.out.println);System.out.println);System.out.println);System.out.println);System.out.println);System.out.println: " + map.put);// 覆盖
// 查询
System.out.println;System.out.println: " + map.get);System.out.println: " + map.get);System.out.println: " + map.get);System.out.println: " + map.get);// 不存在
// 大小
System.out.println);// 包含性
System.out.println);System.out.println);// 删除
System.out.println;System.out.println);System.out.println);// 已不存在
System.out.println);// 遍历验证有序性
System.out.println;MyConcurrentSkipListMap.Node cur = map.head.next;while {
System.out.print;cur = cur.next;}
// 清空
System.out.println);map.clear，System.out.println);System.out.println);}
/** 并发写入压力测试 */
static void concurrentPutTest throws Exception {
System.out.println;MyConcurrentSkipListMap map = new MyConcurrentSkipListMap<>;int threadCount = 10;说起来，int perThread = 1000;int totalOps = threadCount * perThread;ExecutorService executor = Executors.newFixedThreadPool;CountDownLatch latch = new CountDownLatch;for {
final int id=t;executor.execute -> {
for {
int key=id*perThread+j;map.put，}
latch.countDown;})，}
latch.await;executor.shutdown;System.out.println;System.out.printf);// 数据一致性检查
int correct=0;for {
Integer v=map.get;if correct++;}
System.out.printf;// 有序性检查
int last=Integer.MIN_VALUE;MyConcurrentSkipListMap.Node next=map.head.next;
按理说，boolean sorted=true;for {
if {sorted=false;break，}
last=cur.key;}
System.out.println);}
/** 并发混合读写 */
static void concurrentMixedTest throws Exception{
System.out.println;老实说，MyConcurrentSkipListMap map=new MyConcurrentSkipListMap<>;int threadCount=5,ops=2000;// 初始填充
for map.put;System.err.printf);ExecutorService ex=Executors.newFixedThreadPool;CountDownLatch l=new CountDownLatch;Random r=new Random;for{
final int id=t;ex.execute ->{
Random rand=new Random;for{
int op=rand.nextInt;怎么说呢，int key=rand.nextInt;if{
map.put，}else if{
map.get;}else{
map.remove;}
}
l.countDown;})，说起来，}
l.await;ex.shutdown，System.err.printf);// 有序性校验
int last=Integer.MIN_VALUE;boolean ok=true;其实，for{
if{ok=false;break，}
last=cur.key;}
System.err.println);}
/** 吞吐量基准 */
static void performanceTest throws Exception{
int threads={1。2,4,8,16}，for{
long time=testMySkipListThroughput;long ops=t*10000L*1000/time;System.err.printf;}
}
static long testMySkipListThroughputthrows Exception{
MyConcurrentSkipListMap m=new MyConcurrentSkipListMap<>;ExecutorService ex=Executors.newFixedThreadPool;CountDownLatch l=new CountDownLatch;long start=System.currentTimeMillis;话说回来，for{
final int id=i;ex.execute ->{
Random rand=new Random;for{
int op=rand.nextInt,key=rand.nextInt;if m.put，else if m.get;else m.remove;话说回来，}
l.countDown;})，}
l.await;说起来，ex.shutdown;return System.currentTimeMillis-start;}
/** 跳表主体实现 */
static class MyConcurrentSkipListMap{
private final Comparator comparator;private static final int MAX_LEVEL = 32;private static final Random RANDOM = new Random;说起来，private static final double PROBABILITY = 0.25;private volatile int size = 0;private volatile int currentLevel = 1;final Node head = new Node;按理说，@SuppressWarnings
public MyConcurrentSkipListMap{ this.comparator=null;说起来，initHead;}
public MyConcurrentSkipListMap{ this.comparator=b;怎么说呢，initHead;}
@SuppressWarnings
private void initHead{
head=new Node<>;// 所有层共享同一数组实例
for head=head;}
/** 比较函数：支持自定义 comparator 或自然顺序 */
@SuppressWarnings
private int cpr{
return c!=null，c.compare:k1).compareTo;}
/** 随机层级 */
private int randomLevel{
int lvl=1;老实说，while update=new Node;怎么说呢，NodeKcurr=head;// 从最高层向下寻找前驱节点
for{
while<0){
               Kcurr=Kcurr.next;
          }
          update=Kcurr;                 // 保存每层的前驱位置
    }
    Kcurr=Kcurr.next;                    // 第零层候选位置
    if==0){
          Kcurr.value=value;               // 键已存在直接覆盖
          return true;
    }else{
          int lvl=randomLevel;            // 为新节点生成随机层数
          if{           // 若新节点高度超过当前最大层级，需要
 update
               for update=head;
               currentLevel=lvl;
          }
          NodetagNode=new Node<>;// 在每一层完成指针重连
for{
tagNode.next=update.next;update.next=tagNode;}
size++，return true;说起来，}
}
** remove 方法 **
java
@SuppressWarnings
public synchronized boolean remove{
if throw new NullPointerException;Node update=new Node;NodeKcurr=head;怎么说呢，for{
while<0){
              Kcurr=Kcurr.next;
         }
         update=Kcurr;
    }
    Kcurr=Kcurr.next;
    if!=0)
         return false;                       // 未找到
    // 重连各层指针
    for{
         update.next=Kcurr.next;
    }
    // 调整最高层级
    while{
            currentLevel--;
    }
    size--;
    return true;
}
** get、containsKey、size、clear 等辅助方法 **  
java
public synchronized V get{
   if throw new NullPointerException;
   NodeKc=head;for{
while<0)
            Kc=Kc.next;
   }
   Kc=Kc.next;
   return ==0)?Kc.value:null;
}
public synchronized boolean containsKey{return get!=null;}
public synchronized void clear{
   Arrays.fill;
   size=currentLevel=1;
}
public synchronized boolean isEmpty{return size==0;}
** 节点内部类 **  
java
static final class Node{
final K key;// 键不可变且唯一
volatile V value;// 值需要对所有线程可见
final Node next;@SuppressWarnings
Node{
this.key=k;this.value=v;this.next=new Node;}
}
*** End of Insert ***
}

常见问题与调试技巧

• Pain Point – 层级越界：If you see an {@link ArrayIndexOutOfBoundsException},double‑check that you always iterate up to #currentLevel。not node’s own level.
• Pain Point – 更新指针时忘记同步：The whole skip‑list is protected by method‑level synchronized. Removing it will cause subtle race conditions that manifest as lost nodes during iteration.
• Pain Point – 随机层过低导致性能下降：You can tune #PROBABILITY and #MAX_LEVEL
• Pain Point – 删除后未降级層級：The loop at end of #remove) ensures that dangling top layers are collapsed.

& 鼓励语句 🚀

"只要坚持把每一行注释都写清楚，你终将能够站在跳表之巅". 把这篇文章中的注释当作你的“血泪笔记”，当你 面对 Redis 的源码时你会发现那些曾经让人抓狂的抽象已经不再是障碍，而是通往更高性能数据结构的大门。

)

---