每日算法 — 使用java实现跳表：概率性多层链表与对数级搜索优化

跳表（Skip List）是一种由William Pugh于1990年提出的概率性数据结构，它通过在有序链表之上构建多层索引，实现了与平衡二叉搜索树相当的平均时间复杂度——查找、插入、删除均为O(log n)。跳表的核心思想简单却优雅：以概率p决定节点是否晋升到更高层，从而形成金字塔式的多层结构，使得搜索时可以”跳跃”前进，避免逐一遍历。

核心原理与概率分析

跳表的基础是一个有序链表。在此基础上，每个节点有概率p（通常取0.5）拥有一条指向更高层的指针。最底层包含所有元素，向上逐层节点数量呈指数级递减。理想情况下，第k层约有n·p^k个节点。

搜索过程从顶层头节点开始，向右比较直到遇到大于目标值的节点，然后下降到下一层继续搜索，如此反复直到最底层。由于每层可以”跳过”大量节点，期望搜索步数为O(log n)。

Java完整实现

import java.util.Random;

/**
 * 跳表实现 - 概率性多层索引数据结构
 * 支持有序集合的快速查找、插入、删除操作
 * @param <T> 元素类型，需实现Comparable接口
 */
public class SkipList<T extends Comparable<T>> {
    /** 最大层数上限，防止极端情况下层数过高 */
    private static final int MAX_LEVEL = 16;
    /** 节点晋升到更高层的概率，通常取0.5 */
    private static final double P = 0.5;
    /** 随机数生成器，用于决定节点层数 */
    private final Random random;
    /** 当前跳表的实际最大层数 */
    private int level;
    /** 头节点，不存储实际数据，仅作为多层索引起点 */
    private final Node<T> head;
    /** 当前跳表中元素总数 */
    private int size;

    /**
     * 跳表节点内部类
     * 每个节点包含数据值和指向各层下一个节点的指针数组
     */
    private static class Node<T> {
        T value;
        /** forward[i]表示第i层的下一个节点 */
        Node<T>[] forward;

        @SuppressWarnings("unchecked")
        Node(T value, int level) {
            this.value = value;
            // 数组大小为level+1，索引0对应最底层
            this.forward = new Node[level + 1];
        }
    }

    public SkipList() {
        this.random = new Random();
        // 头节点初始化为最大层数，方便后续扩展
        this.head = new Node<>(null, MAX_LEVEL);
        this.level = 0;
        this.size = 0;
    }

    /**
     * 通过随机抛硬币决定新节点的层数
     * 以概率P递增层数，直到概率判定失败或达到最大层数
     * @return 新节点应拥有的层数（从0开始计数）
     */
    private int randomLevel() {
        int lvl = 0;
        // 当随机数小于P且未达到最大层数时，继续晋升
        while (random.nextDouble() < P && lvl < MAX_LEVEL - 1) {
            lvl++;
        }
        return lvl;
    }

    /**
     * 查找目标值是否在跳表中
     * 时间复杂度：平均O(log n)，最坏O(n)
     * @param target 待查找的目标值
     * @return 存在返回true，否则false
     */
    public boolean contains(T target) {
        Node<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];
            }
        }
        // 到达最底层，检查下一个节点是否等于目标值
        current = current.forward[0];
        return current != null && current.value.compareTo(target) == 0;
    }

    /**
     * 向跳表中插入新元素
     * 若元素已存在则不重复插入
     * 时间复杂度：平均O(log n)
     * @param value 待插入的值
     * @return 插入成功返回true，已存在返回false
     */
    public boolean insert(T value) {
        // update数组记录各层中待插入位置的前驱节点
        @SuppressWarnings("unchecked")
        Node<T>[] update = new Node[MAX_LEVEL];
        Node<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; // 元素已存在，不重复插入
        }

        // 第二阶段：生成随机层数并插入新节点
        int newLevel = randomLevel();
        // 若新节点层数超过当前跳表层数，更新头节点对应层的前驱
        if (newLevel > level) {
            for (int i = level + 1; i <= newLevel; i++) {
                update[i] = head;
            }
            level = newLevel;
        }

        Node<T> newNode = new Node<>(value, newLevel);
        // 在各层中插入新节点：调整指针连接
        for (int i = 0; i <= newLevel; i++) {
            newNode.forward[i] = update[i].forward[i];
            update[i].forward[i] = newNode;
        }
        size++;
        return true;
    }

    /**
     * 从跳表中删除指定元素
     * 时间复杂度：平均O(log n)
     * @param value 待删除的值
     * @return 删除成功返回true，不存在返回false
     */
    public boolean delete(T value) {
        @SuppressWarnings("unchecked")
        Node<T>[] update = new Node[MAX_LEVEL];
        Node<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 <= level; i++) {
            if (update[i].forward[i] != current) {
                break; // 更高层不存在该节点
            }
            update[i].forward[i] = current.forward[i];
        }

        // 若最高层变为空，则降低当前层数
        while (level > 0 && head.forward[level] == null) {
            level--;
        }
        size--;
        return true;
    }

    /**
     * 获取跳表中元素总数
     */
    public int size() {
        return size;
    }

    /**
     * 打印跳表结构，用于调试和可视化
     */
    public void display() {
        System.out.println("===== Skip List Structure =====");
        for (int i = level; i >= 0; i--) {
            Node<T> node = head.forward[i];
            System.out.print("Level " + i + ": head");
            while (node != null) {
                System.out.print(" -> " + node.value);
                node = node.forward[i];
            }
            System.out.println(" -> null");
        }
        System.out.println("===============================");
    }

    /**
     * 主方法：演示跳表的基本操作
     */
    public static void main(String[] args) {
        SkipList<Integer> skipList = new SkipList<>();
        int[] data = {3, 6, 7, 9, 12, 19, 17, 26, 21, 25};

        System.out.println("插入元素: " + java.util.Arrays.toString(data));
        for (int num : data) {
            skipList.insert(num);
        }
        skipList.display();

        System.out.println("\n查找测试:");
        System.out.println("contains(12): " + skipList.contains(12));
        System.out.println("contains(15): " + skipList.contains(15));

        System.out.println("\n删除元素 12");
        skipList.delete(12);
        System.out.println("contains(12) after delete: " + skipList.contains(12));
        skipList.display();

        System.out.println("\n当前元素总数: " + skipList.size());
    }
}

复杂度分析

空间复杂度为O(n)，因为每个节点期望拥有 1/(1-p) 个指针。当p=0.5时，期望指针数为2，即额外空间开销约为2n。

应用场景

跳表在工业界有广泛应用：Redis的有序集合（Sorted Set）底层使用跳表实现；LevelDB和RocksDB的MemTable也采用跳表作为内存数据结构。相较于红黑树，跳表的实现更为简洁，且支持高效的区间查询和并发操作。