每日算法 — 使用java实现跳表：概率性多层链表与O(log n)高效查找

引言

跳表（Skip List）是一种由 William Pugh 于1990年提出的概率性数据结构，它通过在有序链表上建立多级索引，实现了与平衡二叉搜索树相媲美的平均 O(log n) 查找、插入和删除性能，同时代码实现远比红黑树或 AVL 树简洁。Redis 的有序集合（ZSet）底层就采用了跳表实现。

本文将用 Java 从零实现一个完整的跳表，深入讲解其概率性建层机制、搜索路径优化以及在实际场景中的应用。

核心思想

普通有序链表的查找需要从头遍历，时间复杂度为 O(n)。跳表的核心改进在于：

1. 多层索引：从原始数据层开始，每隔一定间隔抽取节点构建更高层的快速通道
2. 概率性建层：每个节点通过随机抛硬币决定是否晋升到上一层，层数期望为 O(log n)
3. 逐层搜索：从最高层开始，利用索引快速”跳过”大量节点，定位到目标附近再下沉到下层精确查找

Java 实现

节点定义

public class SkipListNode<K extends Comparable<K>, V> {
    K key;
    V value;
    // forward[i] 表示第 i 层的下一个节点
    SkipListNode<K, V>[] forward;

    @SuppressWarnings("unchecked")
    public SkipListNode(K key, V value, int level) {
        this.key = key;
        this.value = value;
        this.forward = new SkipListNode[level + 1];
    }
}

跳表核心类

import java.util.Random;

public class SkipList<K extends Comparable<K>, V> {
    // 最大层数，Redis 中使用 32
    private static final int MAX_LEVEL = 16;
    // 晋升概率，Redis 中使用 0.25，经典实现为 0.5
    private static final double P = 0.5;

    private final SkipListNode<K, V> head;
    private int level; // 当前最高层数
    private int size;
    private final Random random;

    public SkipList() {
        // 头节点层数为 MAX_LEVEL，key 为 null 作为哨兵
        this.head = new SkipListNode<>(null, null, MAX_LEVEL);
        this.level = 0;
        this.size = 0;
        this.random = new Random();
    }

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

    /**
     * 查找键对应的值
     * 时间复杂度：平均 O(log n)，最坏 O(n)
     */
    public V search(K key) {
        SkipListNode<K, V> current = head;

        // 从最高层开始，逐层向下搜索
        for (int i = level; i >= 0; i--) {
            // 在当前层向右移动，直到下一个节点的 key 大于目标 key
            while (current.forward[i] != null && 
                   current.forward[i].key.compareTo(key) < 0) {
                current = current.forward[i];
            }
        }

        // 现在 current 是第 0 层中 key 小于目标 key 的最后一个节点
        current = current.forward[0];

        if (current != null && current.key.compareTo(key) == 0) {
            return current.value;
        }
        return null;
    }

    /**
     * 插入键值对
     * 如果 key 已存在则更新 value
     * 时间复杂度：平均 O(log n)
     */
    public void insert(K key, V value) {
        // update[i] 记录每一层需要修改的前驱节点
        @SuppressWarnings("unchecked")
        SkipListNode<K, V>[] update = new SkipListNode[MAX_LEVEL + 1];
        SkipListNode<K, V> current = head;

        // 第一步：从高层到低层搜索，记录每一层的前驱节点
        for (int i = level; i >= 0; i--) {
            while (current.forward[i] != null && 
                   current.forward[i].key.compareTo(key) < 0) {
                current = current.forward[i];
            }
            update[i] = current;
        }

        current = current.forward[0];

        // 如果 key 已存在，直接更新 value
        if (current != null && current.key.compareTo(key) == 0) {
            current.value = value;
            return;
        }

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

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

        // 第三步：创建新节点并插入到各层链表中
        SkipListNode<K, V> newNode = new SkipListNode<>(key, value, newLevel);
        for (int i = 0; i <= newLevel; i++) {
            newNode.forward[i] = update[i].forward[i];
            update[i].forward[i] = newNode;
        }

        size++;
    }

    /**
     * 删除指定键
     * 时间复杂度：平均 O(log n)
     */
    public boolean delete(K key) {
        @SuppressWarnings("unchecked")
        SkipListNode<K, V>[] update = new SkipListNode[MAX_LEVEL + 1];
        SkipListNode<K, V> current = head;

        for (int i = level; i >= 0; i--) {
            while (current.forward[i] != null && 
                   current.forward[i].key.compareTo(key) < 0) {
                current = current.forward[i];
            }
            update[i] = current;
        }

        current = current.forward[0];

        if (current == null || current.key.compareTo(key) != 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 boolean isEmpty() {
        return size == 0;
    }

    /**
     * 打印跳表结构，用于调试
     */
    public void printStructure() {
        for (int i = level; i >= 0; i--) {
            System.out.print("Level " + i + ": ");
            SkipListNode<K, V> node = head.forward[i];
            while (node != null) {
                System.out.print("[" + node.key + "] ");
                node = node.forward[i];
            }
            System.out.println();
        }
    }
}

测试与验证

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

        // 插入数据
        int[] keys = {3, 6, 7, 9, 12, 17, 19, 21, 25, 26};
        for (int key : keys) {
            skipList.insert(key, "value-" + key);
        }

        System.out.println("=== 跳表结构 ===");
        skipList.printStructure();

        System.out.println("\n=== 查找测试 ===");
        System.out.println("查找 17: " + skipList.search(17));
        System.out.println("查找 100: " + skipList.search(100));

        System.out.println("\n=== 更新测试 ===");
        skipList.insert(17, "updated-17");
        System.out.println("更新后查找 17: " + skipList.search(17));

        System.out.println("\n=== 删除测试 ===");
        skipList.delete(17);
        System.out.println("删除后查找 17: " + skipList.search(17));
        System.out.println("当前大小: " + skipList.size());
    }
}

复杂度分析

跳表的最坏情况发生在每次随机都晋升到 MAX_LEVEL 或完全不晋升时，但这种情况的概率极低（指数级衰减）。

与平衡树的对比

实际应用场景

1. Redis 有序集合：Redis 的 ZSet 同时使用了跳表和哈希表，跳表负责按分数排序，哈希表负责 O(1) 按成员查找
2. LevelDB/RocksDB：内存中的 MemTable 使用跳表维护有序键值对
3. 排行榜系统：利用跳表的有序性天然支持排名查询
4. 倒排索引：在搜索引擎中用于维护有序的文档 ID 列表

总结

跳表以简洁的实现达成了与平衡树相近的性能，其核心魅力在于用概率代替确定性平衡。理解跳表不仅能掌握一种高效的数据结构，更能体会”用随机化换取简洁性”这一重要的算法设计思想。