每日算法 — 使用java实现跳表：概率分层与对数级有序搜索

跳表（Skip List）是由William Pugh于1989年提出的一种概率型有序数据结构。它通过在普通有序链表之上构建多层”快速通道”索引，实现了平均O(log n)的查找、插入和删除效率，而代码实现远比红黑树或AVL树简洁。Redis的有序集合（Sorted Set）底层就采用了跳表作为核心索引结构。本文将用Java从零实现一个完整的跳表，讲解概率分层的数学原理与工程细节。

一、跳表的核心思想：用概率换平衡

普通有序链表的查找必须从头部逐个遍历，时间复杂度为O(n)。跳表的革命性思路在于：以概率p决定每个节点是否向上晋升一层，形成多级索引。顶层索引稀疏但跨度大，底层索引密集但跨度小。查找时从顶层出发，遇到大于目标值的节点则下降一层，从而在”大步跳跃”与”小步细查”之间取得平衡。

以包含7个元素的有序链表为例，若每个节点以p=0.5的概率向上晋升：

• Level 3（顶层）：包含1个节点，跨度约n/2
• Level 2：包含2~3个节点
• Level 1（底层）：包含全部7个节点

查找值9的过程：从顶层开始，发现7→跳过，遇到13→下降；在Level 2，7→跳过，13→下降；在Level 1，7→9→命中。仅需3次比较即可定位，而普通链表需要5次。

二、节点设计与数据结构

跳表的每个节点需要存储数据值，以及指向各层下一个节点的指针数组。层数（level）在插入时通过随机函数确定，期望值为 1/(1-p)，当p=0.5时每个节点平均有2层指针。

import java.util.Random;

/**
 * 跳表节点
 * forward[i] 表示该节点在第i层的下一个节点
 * level从0开始计数，0表示最底层（原始数据层）
 */
class SkipListNode<T extends Comparable<T>> {
    T value;                           // 节点存储的值
    SkipListNode<T>[] forward;         // 各层前进指针
    int level;                         // 该节点的最高层数（从0开始）

    @SuppressWarnings("unchecked")
    SkipListNode(T value, int level) {
        this.value = value;
        this.level = level;
        // forward数组长度为level+1，索引0~level分别对应各层
        this.forward = new SkipListNode[level + 1];
    }
}

三、跳表类骨架与参数配置

跳表整体维护一个头节点（哨兵节点），其层数等于当前跳表的最大层数。同时记录当前元素个数，用于控制最大层数上限（通常不超过log₂(n)）。

public class SkipList<T extends Comparable<T>> {
    private static final double P = 0.5;       // 晋升概率
    private static final int MAX_LEVEL = 16;   // 最大层数上限
    private final Random random;
    private final SkipListNode<T> head;        // 哨兵头节点
    private int level;                         // 当前跳表实际最高层数
    private int size;                          // 当前元素个数

    public SkipList() {
        this.random = new Random();
        // 头节点初始化为最大层数，所有forward初始为null
        this.head = new SkipListNode<>(null, MAX_LEVEL);
        this.level = 0;
        this.size = 0;
    }

    public int size() { return size; }
    public boolean isEmpty() { return size == 0; }
}

四、搜索算法：从顶层大步跳跃

搜索过程从当前最高层开始，沿各层前进指针查找。若下一节点的值小于目标，则继续前进；若大于或等于目标，则下降至下一层。最终在最底层确认是否命中。

    /**
     * 判断跳表中是否包含指定值
     * 时间复杂度：平均O(log n)，最坏O(n)
     */
    public boolean contains(T target) {
        SkipListNode<T> current = head;
        // 从当前最高层开始逐层下降
        for (int i = level; i >= 0; i--) {
            // 在当前层尽可能向右移动，直到下一节点值>=target
            while (current.forward[i] != null
                   && current.forward[i].value.compareTo(target) < 0) {
                current = current.forward[i];
            }
        }
        // 到达最底层，检查下一个节点是否恰好等于target
        current = current.forward[0];
        return current != null && current.value.compareTo(target) == 0;
    }

五、插入算法：随机晋升与指针重链

插入是跳表最精妙的操作，分为三步：

1. 定位插入位置：逐层查找，记录每一层需要修改指针的节点（update数组）
2. 随机决定新节点层数：通过抛硬币式随机函数生成层数
3. 重链指针：如果新节点层数超过当前跳表层数，需要提升头节点层数；然后将update数组中对应层的前驱指向新节点，新节点指向原后继

    /**
     * 随机生成节点层数
     * 以概率P晋升一层，期望层数 = 1 / (1 - P)
     * 当P=0.5时，50%概率0层，25%概率1层，12.5%概率2层...
     */
    private int randomLevel() {
        int lvl = 0;
        while (random.nextDouble() < P && lvl < MAX_LEVEL) {
            lvl++;
        }
        return lvl;
    }

    /**
     * 插入元素。若已存在则更新（此处选择不更新，保持唯一性）
     * 时间复杂度：平均O(log n)
     */
    public void insert(T value) {
        SkipListNode<T>[] update = new SkipListNode[MAX_LEVEL + 1];
        SkipListNode<T> current = head;

        // 第一步：逐层查找插入位置，记录每一层需要修改的前驱节点
        for (int i = level; i >= 0; i--) {
            while (current.forward[i] != null
                   && current.forward[i].value.compareTo(value) < 0) {
                current = current.forward[i];
            }
            update[i] = current;  // 第i层的前驱节点
        }

        // 检查是否已存在
        current = current.forward[0];
        if (current != null && current.value.compareTo(value) == 0) {
            return; // 已存在，不重复插入
        }

        // 第二步：随机生成新节点层数
        int newLevel = randomLevel();

        // 如果新节点层数超过当前跳表层数，更新头节点的对应层指针
        if (newLevel > level) {
            for (int i = level + 1; i <= newLevel; i++) {
                update[i] = head;  // 头节点是这些新层的前驱
            }
            level = newLevel;
        }

        // 第三步：创建新节点并重链指针
        SkipListNode<T> newNode = new SkipListNode<>(value, newLevel);
        for (int i = 0; i <= newLevel; i++) {
            newNode.forward[i] = update[i].forward[i];  // 新节点指向原后继
            update[i].forward[i] = newNode;             // 前驱指向新节点
        }
        size++;
    }

六、删除算法：逐层解链

删除与插入对称：先找到目标节点在各层的前驱（update数组），然后逐层将前驱的forward直接指向目标节点的后继。若删除后某层变空，还需降低跳表当前层数。

    /**
     * 删除指定值。若不存在则返回false
     * 时间复杂度：平均O(log n)
     */
    public boolean delete(T value) {
        SkipListNode<T>[] update = new SkipListNode[MAX_LEVEL + 1];
        SkipListNode<T> current = head;

        // 逐层查找前驱
        for (int i = level; i >= 0; i--) {
            while (current.forward[i] != null
                   && current.forward[i].value.compareTo(value) < 0) {
                current = current.forward[i];
            }
            update[i] = current;
        }

        // 定位到待删除节点（最底层）
        current = current.forward[0];
        if (current == null || current.value.compareTo(value) != 0) {
            return false; // 不存在
        }

        // 逐层解链
        for (int i = 0; i <= current.level; i++) {
            // 安全检查：确保update[i]确实指向current
            if (update[i].forward[i] != current) {
                break; // 更高层可能没有current，自然停止
            }
            update[i].forward[i] = current.forward[i];
        }

        // 如果最高层变空，降低跳表层数
        while (level > 0 && head.forward[level] == null) {
            level--;
        }

        size--;
        return true;
    }

七、辅助方法：范围查询与遍历

跳表作为有序数据结构，天然支持范围查询和有序遍历。

    /**
     * 查找大于等于target的最小值（lower_bound）
     */
    public T lowerBound(T target) {
        SkipListNode<T> current = head;
        for (int i = level; i >= 0; i--) {
            while (current.forward[i] != null
                   && current.forward[i].value.compareTo(target) < 0) {
                current = current.forward[i];
            }
        }
        SkipListNode<T> result = current.forward[0];
        return result != null ? result.value : null;
    }

    /**
     * 按升序输出所有元素
     */
    public void printAll() {
        SkipListNode<T> current = head.forward[0];
        System.out.print("SkipList(" + size + "): ");
        while (current != null) {
            System.out.print(current.value);
            if (current.forward[0] != null) System.out.print(" -> ");
            current = current.forward[0];
        }
        System.out.println();
    }

    /**
     * 打印跳表的层级结构，便于可视化理解
     */
    public void printStructure() {
        System.out.println("=== 跳表层级结构 ===");
        for (int i = level; i >= 0; i--) {
            System.out.print("Level " + i + ": ");
            SkipListNode<T> current = head.forward[i];
            while (current != null) {
                System.out.print(current.value);
                if (current.forward[i] != null) System.out.print(" -> ");
                current = current.forward[i];
            }
            System.out.println();
        }
    }

八、完整可运行示例

public class SkipListDemo {
    public static void main(String[] args) {
        SkipList<Integer> list = new SkipList<>();

        // 批量插入测试数据
        int[] data = {3, 6, 7, 9, 12, 17, 19, 21, 25, 26};
        for (int v : data) {
            list.insert(v);
        }

        System.out.println("插入完成后：");
        list.printAll();
        list.printStructure();

        // 搜索测试
        System.out.println("\n搜索 12: " + list.contains(12));
        System.out.println("搜索 15: " + list.contains(15));
        System.out.println("Lower bound of 10: " + list.lowerBound(10));

        // 删除测试
        System.out.println("\n删除 12: " + list.delete(12));
        System.out.println("删除后：");
        list.printAll();
        list.printStructure();

        // 性能测试：10万次插入与查找
        System.out.println("\n=== 性能测试 ===");
        SkipList<Integer> perf = new SkipList<>();
        long start = System.nanoTime();
        for (int i = 0; i < 100000; i++) {
            perf.insert(i);
        }
        long insertTime = System.nanoTime() - start;

        start = System.nanoTime();
        for (int i = 0; i < 100000; i++) {
            perf.contains(i);
        }
        long searchTime = System.nanoTime() - start;

        System.out.println("10万插入耗时: " + insertTime / 1_000_000 + " ms");
        System.out.println("10万查找耗时: " + searchTime / 1_000_000 + " ms");
        System.out.println("最终大小: " + perf.size());
    }
}

九、复杂度分析

期望层数的数学推导：每个节点以概率p向上晋升，层数为k的概率为pᵏ(1-p)。期望层数 E = Σ k·pᵏ(1-p) = p/(1-p)。当p=0.5时，E=1，即每个节点平均有2层指针（Level 0和Level 1）。

期望空间开销：n个节点，每个节点平均持有 1/(1-p) 个指针。当p=0.5时，总指针数约为2n，空间开销为O(n)。

与平衡树的对比：

十、总结与延伸

跳表用概率思维优雅地解决了有序数据的高效检索问题。其核心启示在于：不必追求确定性平衡，概率意义上的平衡已足够高效。Redis选择跳表而非红黑树作为有序集合的底层实现，正是因为跳表的代码简洁性、范围查询的天然优势，以及并发修改时更小的锁粒度。

延伸方向包括：

• 并发跳表：通过细粒度锁或无锁CAS操作实现高并发安全（如Java的ConcurrentSkipListMap）
• 确定性跳表：用伪随机序列替代真随机，使层数分布完全可预测，便于调试与测试
• 压缩跳表：对连续整数值进行Run-Length编码，减少内存占用（Redis 5.0引入的ziplist优化）
• MemSQL中的跳表索引：将跳表用于分布式数据库的内存索引层，实现亚毫秒级点查