跳表 SkipList：有序链表上的多层索引

学“跳表 SkipList：有序链表上的多层索引”时，我走过的弯路可以概括成一句话：跳表刚开始给我的感觉是“链表上随便加几层”，真正困惑的是随机层高为什么还能得到稳定的平均查询效率。问题不在于知识点有多难，而在于我一开始只盯着结果，没有看到它在维护什么关系。下面是我重新补这块基础时留下的笔记。

跳表是一种有序数据结构，可以看成“带多层索引的链表”。它的代码通常比红黑树简单，但平均查询、插入、删除也能达到 O(log n)。

它从哪里来

William Pugh 在 1989 年提出跳表，并在随后论文中系统介绍。它不通过旋转维持严格平衡，而是用随机层级给有序链表增加“快速通道”，用概率保证期望性能，因实现简单而进入 Redis 等工程系统。

为什么需要跳表

普通链表查找一个值，只能从头走到尾，复杂度是 O(n)。如果给链表加几层索引，就可以先在高层跳跃定位，再下降到低层精确查找。

图：高层索引跨得远，低层链表保存完整顺序

查找过程

查找 key=30 时：

1. 从最高层头节点开始。
2. 如果右边节点值小于目标，就向右走。
3. 如果右边节点值大于目标或不存在，就下降一层。
4. 到最底层后判断是否命中。

这个过程很像在高速路上先走远，再下匝道找具体位置。

插入过程

插入时先找到每一层的前驱节点，然后随机决定新节点有多少层。

class SkipNode {
    int value;
    SkipNode[] next;
    SkipNode(int value, int level) {
        this.value = value;
        this.next = new SkipNode[level];
    }
}

伪代码：

void add(int value) {
    SkipNode[] update = findPredecessors(value);
    int level = randomLevel();
    SkipNode node = new SkipNode(value, level);
    for (int i = 0; i < level; i++) {
        node.next[i] = update[i].next[i];
        update[i].next[i] = node;
    }
}

随机层数通常按照概率逐层上升，比如每次有一半概率多升一层。这样高层节点少，低层节点全。

删除过程

删除和插入类似，也需要先找到每层前驱节点。如果某层前驱的下一个节点就是目标，就跳过它。

void remove(int value) {
    SkipNode[] update = findPredecessors(value);
    for (int i = 0; i < update.length; i++) {
        if (update[i].next[i] != null && update[i].next[i].value == value) {
            update[i].next[i] = update[i].next[i].next[i];
        }
    }
}

跳表与红黑树

跳表依赖随机化，所以理论最坏情况可能退化，但工程上通过概率控制可以得到稳定表现。

我的分析

跳表的美感在于它没有复杂旋转，却能用多层索引获得接近平衡树的效果。它非常适合理解“索引层”的思想：不是每个结构都要严格平衡，有时候概率平衡也足够好。

面试题

1. 跳表为什么能达到平均 O(log n)？
2. 跳表插入时为什么需要随机层数？
3. 跳表和红黑树各有什么优缺点？
4. Redis ZSet 为什么适合使用跳表？
5. 跳表范围查询为什么比较方便？