跳表（Skip List）—— 一种高效的动态查找数据结构

一、什么是跳表？

跳表（Skip List） 是由 William Pugh 在 1989 年提出的一种基于链表的多层索引结构，用于解决有序链表的查找效率问题。它通过以空间换时间的思想，在普通有序链表的基础上增加多层"快速通道"（索引层），使得查找、插入、删除操作的平均时间复杂度从 O(n) 降低到 O(log n)。

跳表是一种概率性平衡的数据结构，其性能期望与平衡二叉树（如 AVL 树、红黑树）相当，但实现更简单、并发友好。

二、为什么需要跳表？

普通有序链表（Sorted Linked List）的查找操作需要从头遍历到尾，时间复杂度为 O(n)，当数据量很大时效率极低。

跳表解决了什么问题？

问题	普通链表	跳表
查找	O(n)	O(log n)
插入	O(n) + O(1)	O(log n)
删除	O(n) + O(1)	O(log n)
实现复杂度	简单	中等
空间开销	O(n)	O(n log n) 期望

平衡二叉树（如红黑树）虽然也能达到 O(log n) 的复杂度，但实现复杂，且对并发修改的支持困难。跳表实现更直观、易于调试，并且在并发场景下表现优秀（如 Java 中的 ConcurrentSkipListMap）。

三、跳表的结构

跳表由多层的有序链表组成：

第 0 层（L0）：包含所有元素的有序链表（完整数据层）
第 1 层（L1）：L0 的子集，作为 L0 的索引
第 2 层（L2）：L1 的子集，作为 L1 的索引
……
顶层只包含少数几个"关键节点"

结构示意图

Level 3:  ────────────────────────────────────────────── [head] ──────────────────────────── [tail]
Level 2:  ──────────────────── [head] ──────── 20 ──────────────────────────── [tail]
Level 1:  ────── [head] ── 10 ──────── 20 ──────── 30 ──────── 40 ────── [tail]
Level 0:  [head] ── 5 ── 10 ── 15 ── 20 ── 25 ── 30 ── 35 ── 40 ── 45 ── [tail]

每个节点包含：

一个 key（键值）
一个 forward[] 数组，指向每一层的下一个节点
（可选）value（如果是 Map）

层高的确定

节点的层高由随机化策略决定。最常用的方式是：从第 0 层开始，每次以固定概率 p（通常取 0.5 或 0.25）决定是否增加一层。

int randomLevel() {
    int level = 1;
    while (Math.random() < 0.5 && level < MAX_LEVEL) {
        level++;
    }
    return level;
}

期望层高为 1/(1-p)。当 p=0.5 时，期望层高为 2，空间开销约为 O(n)。

四、核心操作

1. 查找（Search）

查找过程从最高层开始，逐层向下：

从 head 的顶层开始向右移动
如果下一个节点的 key 小于目标 key，继续向右
如果下一个节点的 key 大于等于目标 key，下降一层继续
重复直到第 0 层
在第 0 层检查目标节点是否存在

// 查找 key=35
// 从 L3 head 开始 → 无法向右 → 下降到 L2 head
// L2 head → 向右到 20 → 35 > 20 → 继续向右 → 到达 tail → 下降到 L1 20
// L1 20 → 向右到 30 → 35 > 30 → 继续向右到 40 → 35 < 40 → 下降到 L0 30
// L0 30 → 向右到 35 → 找到！

2. 插入（Insert）

用 randomLevel() 确定新节点的层高
在每一层找到插入位置的前驱节点（类似查找过程，记录每层的前驱）
从低到高逐层插入新节点，调整指针

public void insert(int key, int value) {
    Node[] update = new Node[MAX_LEVEL];
    Node current = head;
    
    // 从顶层向下，记录每层的前驱
    for (int i = level - 1; i >= 0; i--) {
        while (current.forward[i] != null && current.forward[i].key < key) {
            current = current.forward[i];
        }
        update[i] = current;
    }
    
    current = current.forward[0];
    if (current != null && current.key == key) {
        current.value = value;  // key 已存在，更新值
    } else {
        int newLevel = randomLevel();
        if (newLevel > level) {
            for (int i = level; i < newLevel; i++) {
                update[i] = head;
            }
            level = newLevel;
        }
        Node newNode = new Node(key, value, newLevel);
        for (int i = 0; i < newLevel; i++) {
            newNode.forward[i] = update[i].forward[i];
            update[i].forward[i] = newNode;
        }
    }
}

3. 删除（Delete）

在每一层找到待删除节点的前驱（同样记录在 update[] 中）
如果第 0 层找到目标节点
从低到高逐层删除：将前驱的 forward[i] 指向待删节点的 forward[i]
可选：清理顶层空层

public boolean delete(int key) {
    Node[] update = new Node[MAX_LEVEL];
    Node current = head;
    
    for (int i = level - 1; i >= 0; i--) {
        while (current.forward[i] != null && current.forward[i].key < key) {
            current = current.forward[i];
        }
        update[i] = current;
    }
    
    current = current.forward[0];
    if (current == null || current.key != key) {
        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 > 1 && head.forward[level - 1] == null) {
        level--;
    }
    return true;
}

五、时间复杂度分析

操作	平均时间复杂度	最坏时间复杂度
查找	O(log n)	O(n)
插入	O(log n)	O(n)
删除	O(log n)	O(n)

平均 O(log n)：得益于多层索引结构，查找路径长度期望为 O(log n)
最坏 O(n)：当随机层高分布极度不均匀时（概率极低），退化为普通链表

为什么是 O(log n)？

从最高层开始查找，每层横向移动的期望步数为常数，而层数期望为 O(log n)。因此总步数为 O(log n)。严格证明基于概率分析，p=0.5 时平均查找长度为约 2×log₂(n)。

空间复杂度

期望空间复杂度：O(n)（因为每个节点平均有 1/(1-p) 个指针，p=0.5 时平均 2 个）
最坏空间复杂度：O(n log n)（所有节点都是最高层）

六、完整 Java 实现

以下是一个完整的跳表实现，包含泛型和基本操作：

import java.util.Random;

public class SkipList<K extends Comparable<K>, V> {

    private static final int MAX_LEVEL = 32;
    private static final double P = 0.5;
    
    private final Node<K, V> head = new Node<>(null, null, MAX_LEVEL);
    private int level = 1;
    private final Random random = new Random();

    // 节点定义
    static class Node<K, V> {
        K key;
        V value;
        Node<K, V>[] forward;

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

    // 随机生成层高
    private int randomLevel() {
        int lvl = 1;
        while (lvl < MAX_LEVEL && random.nextDouble() < P) {
            lvl++;
        }
        return lvl;
    }

    // 查找
    public V search(K key) {
        Node<K, V> current = head;
        for (int i = level - 1; i >= 0; i--) {
            while (current.forward[i] != null && 
                   current.forward[i].key.compareTo(key) < 0) {
                current = current.forward[i];
            }
        }
        current = current.forward[0];
        if (current != null && current.key.compareTo(key) == 0) {
            return current.value;
        }
        return null;
    }

    // 插入
    public void insert(K key, V value) {
        @SuppressWarnings("unchecked")
        Node<K, V>[] update = new Node[MAX_LEVEL];
        Node<K, V> current = head;

        for (int i = level - 1; 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) {
            current.value = value;
            return;
        }

        int newLevel = randomLevel();
        if (newLevel > level) {
            for (int i = level; i < newLevel; i++) {
                update[i] = head;
            }
            level = newLevel;
        }

        Node<K, V> newNode = new Node<>(key, value, newLevel);
        for (int i = 0; i < newLevel; i++) {
            newNode.forward[i] = update[i].forward[i];
            update[i].forward[i] = newNode;
        }
    }

    // 删除
    public boolean delete(K key) {
        @SuppressWarnings("unchecked")
        Node<K, V>[] update = new Node[MAX_LEVEL];
        Node<K, V> current = head;

        for (int i = level - 1; 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 > 1 && head.forward[level - 1] == null) {
            level--;
        }
        return true;
    }

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

使用示例

public class SkipListDemo {
    public static void main(String[] args) {
        SkipList<Integer, String> skipList = new SkipList<>();
        
        skipList.insert(10, "Ten");
        skipList.insert(20, "Twenty");
        skipList.insert(5, "Five");
        skipList.insert(15, "Fifteen");
        skipList.insert(30, "Thirty");

        System.out.println("search(10): " + skipList.search(10));  // Ten
        System.out.println("search(7): " + skipList.search(7));    // null
        
        skipList.delete(20);
        System.out.println("After delete 20:");
        skipList.print();
    }
}

七、Java 中的 ConcurrentSkipListMap 和 ConcurrentSkipListSet

Java 在 java.util.concurrent 包中提供了基于跳表实现的并发集合：

ConcurrentSkipListMap

ConcurrentSkipListMap<K, V> — 并发安全的有序 Map

基于跳表（不是锁分段），采用无锁（Lock-Free）CAS 操作
保证 线程安全 和 有序性（按 key 的自然顺序或 Comparator 排序）
支持 putIfAbsent、replace、remove 等原子操作
提供 subMap、headMap、tailMap 等范围视图

import java.util.concurrent.ConcurrentSkipListMap;

public class ConcurrentSkipListMapExample {
    public static void main(String[] args) {
        ConcurrentSkipListMap<Integer, String> map = 
            new ConcurrentSkipListMap<>();
        
        map.put(3, "C");
        map.put(1, "A");
        map.put(2, "B");
        
        // 自动排序输出
        System.out.println(map);  // {1=A, 2=B, 3=C}
        
        // 范围查询
        System.out.println(map.subMap(1, 3));  // {1=A, 2=B}
        
        // 原子操作
        map.putIfAbsent(2, "X");
        System.out.println(map.get(2));  // B (未替换)
    }
}

ConcurrentSkipListSet

ConcurrentSkipListSet<E> — 基于 ConcurrentSkipListMap 的 NavigableSet

线程安全的有序 Set
所有操作与 ConcurrentSkipListMap 类似

import java.util.concurrent.ConcurrentSkipListSet;

public class ConcurrentSkipListSetExample {
    public static void main(String[] args) {
        ConcurrentSkipListSet<Integer> set = 
            new ConcurrentSkipListSet<>();
        
        set.add(5);
        set.add(1);
        set.add(3);
        
        System.out.println(set);  // [1, 3, 5]
        System.out.println(set.lower(3));   // 1
        System.out.println(set.higher(3));  // 5
    }
}

性能特点

特性	ConcurrentSkipListMap	ConcurrentHashMap
有序性	✅ 天然有序	❌ 无序
并发度	高（无锁 CAS）	高（分段锁/CAS）
查找	O(log n)	O(1) 平均
范围查询	✅ 高效	❌ 需遍历

何时使用 ConcurrentSkipListMap？

需要有序的并发 Map

需要范围查询（range query）

需要 NavigableMap 接口提供的导航方法（ceilingKey、floorEntry 等）

八、跳表 vs 平衡二叉树

比较维度	跳表	红黑树 / AVL 树
实现复杂度	简单（~100 行）	复杂（旋转、颜色调整）
平均查找	O(log n)	O(log n)
插入/删除	简单，仅需调整指针	复杂，需旋转保持平衡
范围查询	高效（链表结构天然支持）	需中序遍历（需要 stack）
并发友好	非常友好（锁分离、CAS 友好）	较困难（需精细锁）
内存占用	平均约 2n 个指针	约 2n 个指针+颜色位
最坏性能	O(n) 概率极低	O(log n) 严格保证
常数因子	稍大（多层遍历）	较小（2-3 次比较）

核心差异详解

1. 平衡机制

跳表：概率平衡（随机的层高），无需额外操作
红黑树：确定性平衡（通过旋转和染色），保证绝对平衡

2. 实现难度

跳表的核心逻辑约 100 行代码即可实现
红黑树的插入和删除有 6 种旋转情况，实现约 300-500 行

3. 并发场景

跳表的节点指针修改只影响相邻节点，天然适合无锁编程
树的旋转操作涉及多个节点的指针重排，并发控制复杂

4. 内存局部性

跳表的链表结构导致缓存不友好（节点在内存中分散）
平衡树（如果用数组试）的局部性可能更好

九、总结

跳表是一种多层有序链表，通过随机化层高实现 O(log n) 的查找性能
相比平衡树，实现更简单（约 100 行代码），插入/删除逻辑直观
天然并发友好，Java 的 ConcurrentSkipListMap 是生产级的实现
适用于需要有序性和范围查询的并发场景
虽然最坏情况可能退化为 O(n)，但概率极低（指数级衰减），实际中可忽略

一句话总结：跳表是以少量空间冗余为代价，让链表飞起来的数据结构。

参考文献

William Pugh, “Skip Lists: A Probabilistic Alternative to Balanced Trees” (1990)
Java 17 java.util.concurrent.ConcurrentSkipListMap 源码
《算法导论》第 13 章 — 跳表

菜单

分享

跳表 (Skip List)

跳表（Skip List）—— 一种高效的动态查找数据结构

一、什么是跳表？

二、为什么需要跳表？

三、跳表的结构

结构示意图

层高的确定

四、核心操作

1. 查找（Search）

2. 插入（Insert）

3. 删除（Delete）

五、时间复杂度分析

空间复杂度

六、完整 Java 实现

使用示例

七、Java 中的 ConcurrentSkipListMap 和 ConcurrentSkipListSet

ConcurrentSkipListMap

ConcurrentSkipListSet

性能特点

八、跳表 vs 平衡二叉树

核心差异详解

九、总结

参考文献

评论

GitHub热点追踪（2026-05-20）

RuView（π RuView）：用 WiFi 信号感知世界的革命 — 无摄像头的人体姿态检测与生命体征监测

Agent Harness 是什么？—— 从概念到 OpenCode 实践

Anthropic Cybersecurity Skills：754 个结构化网络安全技能 — 让 AI Agent 成为安全分析师

Multica：开源多智能体协作平台 — 把编码 Agent 变成真正的队友

GitHub热点追踪（2026-05-22）

GitHub热点追踪（2026-05-24）

Presenton：开源 AI 演示文稿生成器 — Gamma/Beautiful AI 的完全自托管替代

Understand-Anything：将代码库变为交互式知识图谱 — AI Agent 的代码理解革命

单例模式