数据结构引入
在有序数据集合中，查找、插入和删除的效率至关重要。平衡二叉搜索树（如红黑树、AVL树）能在 $O(\log n)$ 时间内完成这些操作，但实现复杂。跳表（Skip List）由 William Pugh 于1990年提出，它以概率方式构建多层索引链表，在期望意义下达到与平衡二叉树相同的 $O(\log n)$ 时间复杂度，而实现却像链表一样简洁直观。Redis 的有序集合（ZSET）底层正是基于跳表实现。
核心思想
跳表的核心思想是”空间换时间”——在原始有序链表之上，构建若干层稀疏的索引链表：
- 最底层（Level 0）包含所有元素的有序链表
- 上一层只包含下层中部分元素，作为”快速通道”
- 越往上层元素越稀疏，类似高速公路的出入口
- 查找时从顶层开始，大步跳跃，遇到大于目标值的节点则下降到下一层
每个节点是否出现在上一层由随机决定（通常以 1/2 概率晋升），这种随机化策略以极高概率保证各层分布均匀，从而实现对数级查找效率。
完整Java实现
import java.util.Random;
/**
* 跳表（Skip List）实现
* 概率平衡的多层链表结构，期望时间复杂度O(log n)
* 支持快速查找、插入、删除操作
*/
public class SkipList<K extends Comparable<K>, V> {
/** 最大层数，影响性能和空间占用 */
private static final int MAX_LEVEL = 16;
/** 节点晋升到上层的概率（p=0.5时最均衡） */
private static final double P = 0.5;
private final Random random;
/** 当前跳表的实际最高层数 */
private int levelCount;
/** 头节点，不存储实际数据，层数为MAX_LEVEL */
private final Node<K, V> head;
/**
* 跳表节点定义
* 每个节点包含数据以及多层前向指针（forward[i]表示第i层的下一个节点）
*/
private static class Node<K, V> {
K key;
V value;
/** 前向指针数组，大小为该节点的层数 */
Node<K, V>[] forward;
@SuppressWarnings("unchecked")
Node(K key, V value, int level) {
this.key = key;
this.value = value;
this.forward = new Node[level];
}
}
public SkipList() {
this.random = new Random();
// 头节点初始化，层数为MAX_LEVEL
this.head = new Node<>(null, null, MAX_LEVEL);
this.levelCount = 1;
}
/**
* 随机生成节点层数
* 以概率P逐层晋升，直到不晋升或达到MAX_LEVEL
*
* @return 生成的层数（1到MAX_LEVEL之间）
*/
private int randomLevel() {
int level = 1;
// 以概率P决定是否晋升到下一层
while (random.nextDouble() < P && level < MAX_LEVEL) {
level++;
}
return level;
}
/**
* 查找指定key对应的value
* 从最高层开始，逐层缩小搜索范围
*
* @param key 查找的键
* @return 对应的值，不存在则返回null
*/
public V search(K key) {
Node<K, V> current = head;
// 从当前最高层开始查找
for (int i = levelCount - 1; i >= 0; i--) {
// 在当前层向右移动，直到下一个节点的key大于等于目标key
while (current.forward[i] != null
&& current.forward[i].key.compareTo(key) < 0) {
current = current.forward[i];
}
}
// 现在current.forward[0]就是可能的目标节点
current = current.forward[0];
if (current != null && current.key.compareTo(key) == 0) {
return current.value;
}
return null;
}
/**
* 插入键值对到跳表
* 若key已存在则更新value
*
* @param key 键
* @param value 值
*/
public void insert(K key, V value) {
// update数组记录每一层中，待插入位置的前一个节点
@SuppressWarnings("unchecked")
Node<K, V>[] update = new Node[MAX_LEVEL];
Node<K, V> current = head;
// 第一步：查找每一层的插入位置前驱节点
for (int i = levelCount - 1; i >= 0; i--) {
while (current.forward[i] != null
&& current.forward[i].key.compareTo(key) < 0) {
current = current.forward[i];
}
update[i] = current;
}
// 第二步：检查key是否已存在
current = current.forward[0];
if (current != null && current.key.compareTo(key) == 0) {
// 已存在，更新value
current.value = value;
return;
}
// 第三步：生成随机层数，创建新节点
int newLevel = randomLevel();
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;
}
// 第五步：更新跳表当前层数
if (newLevel > levelCount) {
levelCount = newLevel;
}
}
/**
* 从跳表中删除指定key的节点
*
* @param key 待删除的键
* @return 是否删除成功
*/
public boolean delete(K key) {
@SuppressWarnings("unchecked")
Node<K, V>[] update = new Node[MAX_LEVEL];
Node<K, V> current = head;
// 查找待删除节点在各层的前驱
for (int i = levelCount - 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 < levelCount; i++) {
if (update[i].forward[i] != current) {
break; // 更高层没有该节点
}
update[i].forward[i] = current.forward[i];
}
// 更新当前层数（去除空层）
while (levelCount > 1 && head.forward[levelCount - 1] == null) {
levelCount--;
}
return true;
}
/**
* 查找大于等于key的最小元素
* 即跳表中的lower_bound操作
*
* @param key 目标键
* @return 大于等于key的最小节点的key，不存在则返回null
*/
public K ceiling(K key) {
Node<K, V> current = head;
for (int i = levelCount - 1; i >= 0; i--) {
while (current.forward[i] != null
&& current.forward[i].key.compareTo(key) < 0) {
current = current.forward[i];
}
}
Node<K, V> target = current.forward[0];
return (target != null) ? target.key : null;
}
/**
* 打印跳表结构（用于调试和理解）
*/
public void printStructure() {
System.out.println("=== Skip List Structure ===");
for (int i = levelCount - 1; i >= 0; i--) {
System.out.print("Level " + i + ": ");
Node<K, V> current = head.forward[i];
while (current != null) {
System.out.print("[" + current.key + "]->");
current = current.forward[i];
}
System.out.println("null");
}
System.out.println("===========================");
}
/**
* 主方法：演示跳表的基本操作
*/
public static void main(String[] args) {
SkipList<Integer, String> skipList = new SkipList<>();
// 插入数据
int[] keys = {3, 6, 7, 9, 12, 19, 17, 26, 21, 25};
for (int k : keys) {
skipList.insert(k, "value_" + k);
}
System.out.println("插入元素后:");
skipList.printStructure();
// 查找测试
System.out.println("\n查找 19: " + skipList.search(19));
System.out.println("查找 100: " + skipList.search(100));
// ceiling测试
System.out.println("\nceiling(10): " + skipList.ceiling(10));
System.out.println("ceiling(19): " + skipList.ceiling(19));
// 删除测试
System.out.println("\n删除 19: " + skipList.delete(19));
System.out.println("删除后查找 19: " + skipList.search(19));
skipList.printStructure();
// 更新测试
skipList.insert(12, "updated_12");
System.out.println("\n更新后查找 12: " + skipList.search(12));
}
}
复杂度分析
| 操作 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 查找 | $O(\log n)$ | $O(n)$ | $O(n)$ 期望 |
| 插入 | $O(\log n)$ | $O(n)$ | $O(n)$ 期望 |
| 删除 | $O(\log n)$ | $O(n)$ | $O(n)$ 期望 |
最坏情况发生在所有节点都晋升到最高层（或都不晋升），但由于随机化，这种概率极低。期望空间复杂度为 $O(n)$，因为每个节点期望层数为 $1/(1-p)$（当 $p=0.5$ 时为 2），总节点数期望为 $2n$。
跳表 vs 平衡二叉树
| 特性 | 跳表 | 红黑树/AVL树 |
|---|---|---|
| 实现难度 | 简单，代码量少 | 复杂，需要处理多种旋转情况 |
| 范围查询 | 天然支持（链表遍历） | 需要中序遍历 |
| 并发控制 | 锁粒度细，仅影响局部 | 旋转可能涉及全局调整 |
| 常数因子 | 略大（随机数和指针数组） | 较小 |
| 确定性 | 概率性保证 | 确定性保证 |
Redis 选择跳表而非红黑树实现有序集合，正是因为跳表实现简单、范围查询高效且支持细粒度锁。跳表以优雅的概率化设计，证明了”随机性”本身就是一种强大的数据结构平衡手段。
