跳表实现（java版本）

1.一句话理解跳表

跳表 = 有序链表 + 多层索引。

底层是一条完整的有序单链表，上面又盖了几层”稀疏的索引”。查找时从最高层开始，能跳就跳，跳不动了再往下一层，平均时间复杂度 O(log n)。它用”以空间换时间”的思路，把一个慢查询的链表变成了接近二分查找的速度。

2.为什么需要跳表

先看一个朴素的对比：

结构	查找	插入	删除	备注
有序数组	O(log n)（二分）	O(n)（搬数据）	O(n)	插入删除太慢
有序链表	O(n)	O(1)（找到后）	O(1)（找到后）	查找太慢
平衡二叉搜索树	O(log n)	O(log n)	O(log n)	实现复杂，易写错
跳表	O(log n)	O(log n)	O(log n)	实现简单，范围查询友好

有序链表插入删除快，但查找要从头遍历。跳表的思路是：既然从头遍历慢，那就每隔几个结点建一条”快车道”，上层快车道更稀疏、跨度更大，查找时先走快车道，逼近目标后再往下层细找。

3.结构是多层索引

想象一条有序链表：

3 -> 6 -> 7 -> 9 -> 12 -> 17 -> 19 -> 21 -> 25 -> 26

我们在部分结点上”抽头”建索引（第 1 层）：

第1层:  7 --------> 17 ------------> 25
底层 : 3 -> 6 -> 7 -> 9 -> 12 -> 17 -> 19 -> 21 -> 25 -> 26

查找 19：在第 1 层从 7 跳到 17，发现 17 的下一个 25 已经大于 19，于是下到底层从 17 往后走，一步就到 19。

每层索引的结点数量约为下一层的一半，所以层数约为 log n，查找步数也约为 log n。

关键问题：哪些结点该进索引？ 跳表用随机化的方式——每个新结点”抛硬币”，正面就升一层，直到反面或到达上限。这样索引分布是概率均衡的，不需要像平衡树那样做旋转调整。

4.三个核心操作

三个操作的主干完全一样，就是查找：先自顶向下找到目标在每一层的前驱，只是”找到了之后做什么”不同。这个”找前驱”被抽成了一个 findPrev(target) 方法，返回一个 prev[] 数组，其中 prev[i] 是第 i 层里”目标应该插在它后面”的那个结点。

查找

从 MAX_LEVEL 层出发，当前层向右走（只要下一个结点的值 < 目标），走不动了就下到下一层，重复直到最底层。最后看第 0 层 prev[0].next[0] 的值是否等于目标。

插入

1. findPrev(num) 拿到 prev[]。
2. 抛硬币得到新结点的层数 lvl。
3. 像普通链表插入一样，把新结点挂到 0..lvl 每一层里（前驱就是 prev[i]）。

删除

1. 同样先 findPrev(num) 拿到 prev[]。
2. 看 prev[0].next[0] 是否等于目标：不是就说明不存在，直接返回 false。
3. 是的话，把它从每一层摘掉；遇到某一层 prev[i].next[i] 不再指向它（说明它压根没那一层），停止即可。

5.Java简洁实现

下面是可直接编译运行的版本，三个操作共用 findPrev。

import java.util.Random;

/**
 * 跳表的简洁实现
 *   - add(num)    插入一个数字（允许重复）
 *   - search(num) 是否存在
 *   - erase(num)  删除一个数字，成功返回 true
 */
public class Skiplist {

    // 最大层数。层数越大索引越稀疏，但指针占用越多；16 层足以支撑 2^16 规模的数据。
    private static final int MAX_LEVEL = 16;

    // 头结点不存业务数据（val 用 -1 占位，且永远不参与比较，任意占位值均可），
    // 它的 next 数组长度 = MAX_LEVEL + 1，相当于一条贯穿所有层的"虚拟起点"。
    private final Node head = new Node(-1, MAX_LEVEL);
    private final Random random = new Random();

    /** 跳表结点：一个值 + 多层 next 指针。层数 = next.length - 1，无需单独存 level。 */
    private static class Node {
        int val;
        Node[] next; // next[i] 指向第 i 层的下一个结点

        Node(int val, int level) {
            this.val = val;
            this.next = new Node[level + 1];
        }
    }

    public Skiplist() {}

    // 抛硬币决定新结点的层数：每一层有 1/2 概率继续往上，直到反面或到达 MAX_LEVEL。
    private int randomLevel() {
        int level = 0;
        while (random.nextDouble() < 0.5 && level < MAX_LEVEL) {
            level++;
        }
        return level;
    }

    // 自顶向下，找到 target 在每一层的前驱结点，返回它们组成的数组。
    // 查找 / 插入 / 删除都先走这一步，是跳表所有操作的主干。
    private Node[] findPrev(int target) {
        Node[] prev = new Node[MAX_LEVEL + 1];
        Node curr = head;
        for (int i = MAX_LEVEL; i >= 0; i--) {
            while (curr.next[i] != null && curr.next[i].val < target) {
                curr = curr.next[i];
            }
            prev[i] = curr;
        }
        return prev;
    }

    // 复用 findPrev：拿到每层前驱后，第 0 层的 prev[0].next[0] 就是第一个 val >= target 的结点。
    // 等于 target 即存在，否则不存在。
    public boolean search(int target) {
        Node[] prev = findPrev(target);
        Node node = prev[0].next[0];
        return node != null && node.val == target;
    }

    public void add(int num) {
        Node[] prev = findPrev(num);
        Node node = new Node(num, randomLevel());
        int top = node.next.length - 1; // 层数 = 数组长度 - 1，无需单独字段
        for (int i = 0; i <= top; i++) {
            node.next[i] = prev[i].next[i];
            prev[i].next[i] = node;
        }
    }

    public boolean erase(int num) {
        Node[] prev = findPrev(num);
        Node node = prev[0].next[0];
        if (node == null || node.val != num) {
            return false; // 不存在
        }
        // 把 node 从它出现的每一层里摘掉；遇到某一层没有 node 就停止。
        for (int i = 0; i <= MAX_LEVEL; i++) {
            if (prev[i].next[i] != node) {
                break;
            }
            prev[i].next[i] = node.next[i];
        }
        return true;
    }

    // 本地验证用：跑一遍 LeetCode 示例
    public static void main(String[] args) {
        Skiplist sl = new Skiplist();
        sl.add(1); sl.add(2); sl.add(3);
        System.out.println("search(0) = " + sl.search(0)); // false
        sl.add(4);
        System.out.println("search(1) = " + sl.search(1)); // true
        System.out.println("erase(0)  = " + sl.erase(0));  // false
        System.out.println("erase(1)  = " + sl.erase(1));  // true
        System.out.println("search(1) after erase = " + sl.search(1)); // false
    }
}

跑一遍 main 的输出：

search(0) = false
search(1) = true
erase(0)  = false
erase(1)  = true
search(1) after erase = false

6.时间复杂度

• 查找 / 插入 / 删除：平均 O(log n)，最坏 O(n)（极端情况下所有结点都堆在同一层）。
• 空间：平均 O(n)（每个结点期望层数约为 2，索引额外占用约 n 个指针）。
• 概率保证下，层数超过 3 log n 的概率极小，MAX_LEVEL = 16 足以支撑千万级数据。

7.跳表 vs 红黑树

Redis 的 ZSet 用跳表而不是红黑树，主要因为：

1. 范围查询友好：跳表找到起点后，沿底层链表顺序遍历即可拿到一段区间；红黑树需要中序遍历，缓存局部性差。
2. 实现简单、不易写错：跳表没有旋转、变色等平衡操作，代码量小一半以上（上面这版只有 70 行左右）。
3. 性能相当：两者增删查都是 O(log n)，跳表在范围操作上更自然。

代价是跳表空间占用略高（多存索引指针），以及最坏情况退化为 O(n)——但概率极低，工程中可接受。

8.小结

• 跳表 = 有序链表 + 随机多层索引，平均 O(log n)。
• 核心难点在 prev[] 数组：插入 / 删除 / 查找前先自顶向下记录每层前驱，抽成 findPrev 后三个操作都很短。
• 层数靠抛硬币随机，天然平衡，不需要旋转。
• 一句话：跳表用概率换实现简单，用空间换查询快，最适合带范围查询的有序集合。

end……