深入浅出跳表(SkipList)：原理、实现与代码实战-程序员充电站

引言

在有序数据结构的选型中，平衡二叉搜索树（如AVL树、红黑树）凭借O(log n)的查找性能长期占据主流。然而，它们的插入、删除操作往往伴随复杂的旋转与染色，实现难度较高。一种更“聪明”的替代方案——跳表(SkipList)，用概率化的多层链表达到了同样的时间复杂度，代码却简洁得多，Redis的有序集合正是基于跳表实现的。

本文将用通俗的语言解析跳表的设计思想，并通过一份完整的Java代码演示其核心操作，最后讨论实际应用中需要留意的细节。读完你会理解，为何跳表常常被称为“用空间换时间的艺术”。

核心概念：为链表加上“快速通道”

跳表本质上是对有序单链表的改进。在普通链表中，即使元素有序，查找一个元素也只能顺序遍历，时间复杂度O(n)。为了加速，我们可以仿照书籍的目录，为链表建立索引。最直观的做法是：取部分关键节点，组成一条上层链表，上层节点跨度更大。当我们需要查找某个值时，先在上层快速接近目标，再下降至下层精确查找。

跳表将这个思想推演为多层索引。一个包含n个元素的跳表，最高层索引会拥有约2个节点，理想情况下层数可达到O(log n)。下图展示了一个包含层数为3的跳表结构（数字代表元素值，节点间的连线表示指针）：

Level 2: head ---------> 30 -------------------------> null Level 1: head -> 10 ----> 30 ------> 50 ------> 70 --> null Level 0: head -> 5 -> 10 -> 20 -> 30 -> 40 -> 50 -> 60 -> 70 -> 80 -> null

查找元素40的过程：
1. 从最高层（Level 2）头节点开始，发现下一个节点是30，且30<40，则移动到30。
2. 在Level 2，30的下一个节点为null，向下到达Level 1。
3. 在Level 1的30节点，下一个节点50>40，向下到达Level 0。
4. 在Level 0的30节点，继续向右，依次经过40，查找成功。

这一过程将比较次数从线性级降到了对数级。

节点的“层高”并非一成不变，而是通过随机化决定。常用的策略是：每一层有固定概率p（如0.5）决定是否向上提升。这种概率化的平衡使得跳表在期望情况下表现优异，且实现远比平衡树简单。

实战示例：Java实现可运行的跳表

我们将实现一个支持泛型的跳表，要求元素可比较（实现Comparable接口）。主要操作包括search、insert、delete。代码包含完整的注释，可直接运行。

节点类定义

class SkipListNode<T extends Comparable<T>> { T value; // forward[i] 表示当前节点在第 i 层的下一个节点指针 SkipListNode<T>[] forward; @SuppressWarnings("unchecked") SkipListNode(T value, int level) { this.value = value; this.forward = new SkipListNode[level + 1]; } }

每个节点持有一个指针数组，forward[i]指向第i层的下一节点。注意，头节点不存储实际值，它的层高为跳表的最大层数。

跳表主类

我们设定最大层数为16（可满足绝大多数场景），概率因子为0.5。头节点初始化为最高层，后续插入时动态生成节点的随机层数。

import java.util.Random; public class SkipList<T extends Comparable<T>> { private static final int MAX_LEVEL = 16; private static final double P = 0.5; private final Random random = new Random(); private final SkipListNode<T> head; private int currentLevel; // 当前跳表实际使用的最大层数 public SkipList() { // 头节点不存值，层数初始化MAX_LEVEL head = new SkipListNode<>(null, MAX_LEVEL); currentLevel = 0; } // 随机生成新节点的层数 private int randomLevel() { int level = 0; while (random.nextDouble() < P && level < MAX_LEVEL) { level++; } return level; } // 查找：返回目标节点（若不存在则返回null） public SkipListNode<T> search(T target) { SkipListNode<T> cur = head; // 从最高层往下找 for (int i = currentLevel; i >= 0; i--) { while (cur.forward[i] != null && cur.forward[i].value.compareTo(target) < 0) { cur = cur.forward[i]; } } // 此时cur是第0层中小于target的最大节点 cur = cur.forward[0]; if (cur != null && cur.value.compareTo(target) == 0) { return cur; } return null; } // 插入元素 public void insert(T value) { // update数组记录每一层需要更新的前驱节点 SkipListNode<T>[] update = new SkipListNode[MAX_LEVEL + 1]; SkipListNode<T> cur = head; // 从最高层开始查找插入位置 for (int i = currentLevel; i >= 0; i--) { while (cur.forward[i] != null && cur.forward[i].value.compareTo(value) < 0) { cur = cur.forward[i]; } update[i] = cur; } // 移动到第0层实际位置 cur = cur.forward[0]; // 如果已存在，可选择覆盖（本示例中忽略，不允许重复值） if (cur != null && cur.value.compareTo(value) == 0) { return; // 已存在则不插入 } int newLevel = randomLevel(); // 若新节点层数超过当前最大层，则更高的层需要由head指向它 if (newLevel > currentLevel) { for (int i = currentLevel + 1; i <= newLevel; i++) { update[i] = head; } currentLevel = 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; } System.out.println("Inserted: " + value + " (level " + newLevel + ")"); } // 删除元素 public boolean delete(T value) { SkipListNode<T>[] update = new SkipListNode[MAX_LEVEL + 1]; SkipListNode<T> cur = head; for (int i = currentLevel; i >= 0; i--) { while (cur.forward[i] != null && cur.forward[i].value.compareTo(value) < 0) { cur = cur.forward[i]; } update[i] = cur; } cur = cur.forward[0]; // 未找到 if (cur == null || cur.value.compareTo(value) != 0) { return false; } // 从底层到cur所在的最高层，摘除节点 for (int i = 0; i <= currentLevel; i++) { if (update[i].forward[i] != cur) break; update[i].forward[i] = cur.forward[i]; } // 尝试降低全局最大层数（如果高层已无节点） while (currentLevel > 0 && head.forward[currentLevel] == null) { currentLevel--; } System.out.println("Deleted: " + value); return true; } // 打印跳表结构（方便调试观察） public void print() { System.out.println("SkipList (max level used: " + currentLevel + ")"); for (int i = currentLevel; i >= 0; i--) { System.out.print("Level " + i + ": H -> "); SkipListNode<T> node = head.forward[i]; while (node != null) { System.out.print(node.value + " -> "); node = node.forward[i]; } System.out.println("null"); } } // 测试主函数 public static void main(String[] args) { SkipList<Integer> skipList = new SkipList<>(); skipList.insert(30); skipList.insert(10); skipList.insert(50); skipList.insert(20); skipList.insert(40); System.out.println("\nAfter inserts:"); skipList.print(); System.out.println("\nSearch 30: " + (skipList.search(30) != null)); System.out.println("Search 100: " + (skipList.search(100) != null)); skipList.delete(20); System.out.println("\nAfter deleting 20:"); skipList.print(); skipList.delete(30); System.out.println("\nAfter deleting 30:"); skipList.print(); } }

代码要点解析

随机层数：randomLevel()以概率P递增层数，确保平均层数为1/(1-P)。当P=0.5时，平均层数约为2，符合O(log n)期望。
update数组：在查找插入/删除位置时，记录每层需要断开和重连的前驱节点，是实现对应操作的关键。
层数动态调整：插入后若新节点层数超过currentLevel，则由head补齐高层指针；删除后若高层仅剩head，则降低currentLevel，避免无效遍历。
泛型设计：通过Comparable约束可以轻松适配整数、字符串等有序类型。

运行main方法，可直观看到跳表各层的链表结构，验证操作的正确性。

常见问题与注意事项

1. 如何确定最大层数和概率因子？

最大层数MAX_LEVEL可近似取log_{1/p}(预期元素数量上限)。例如，若期望存放2^16 ≈ 65536个元素，P=0.5，则MAX_LEVEL=16足够。实际应用中，Redis使用32层、概率0.25。概率越高，节点平均层数越大，空间消耗上升但查找更快。需要根据读写比例和内存限制折衷。

2. 并发环境下的线程安全

上述实现非线程安全。在多线程并发读写时，指针的修改可能造成数据竞争或结构破坏。常见的解决方式包括：
- 使用读写锁（如Java的ReentrantReadWriteLock），适合读多写少场景。
- 采用无锁实现，如基于CAS操作更新指针。Redis中的跳表在单线程模型下无需锁，但其底层使用原子操作优化了某些访问。

3. 跳表与红黑树的选择

实现复杂度：跳表远低于红黑树，尤其是不涉及复杂的旋转与颜色维护。
范围查询：跳表天然支持顺序遍历（第0层链表即有序），而红黑树需要中序遍历，稍显不便。
空间开销：跳表的指针数组占用额外空间（平均每节点1/(1-p)个指针），但如果不介意内存，这个开销可以接受。
性能稳定性：跳表的期望时间优秀，但最坏情况可能退化到O(n)，尽管概率极低。红黑树是严格O(log n)。对于不能容忍任何延迟波动的系统，红黑树更保险。