引言
跳表（Skip List）是由William Pugh于1990年提出的概率性数据结构，它通过在有序链表上构建多层索引，实现了与平衡树相媲美的O(log n)查找效率，同时代码实现更为简洁直观。Redis的有序集合（Sorted Set）底层就采用了跳表作为核心数据结构之一。本文将用Java实现一个完整的跳表，涵盖插入、删除、查找操作，并深入分析其概率性层级构建机制。
算法核心思想
多层索引结构
跳表的核心思想是在普通有序链表之上建立多层”快速通道”。最底层（Level 0）包含所有元素，上一层包含部分元素作为索引，再上一层包含更少的元素，以此类推。查找时从顶层开始，利用索引快速跳过大量元素。
概率性层级提升
与平衡树通过旋转维持平衡不同，跳表通过随机数决定每个新节点提升到多少层。具体来说，每个节点以概率p（通常取0.5）提升到更高一层。这种随机策略使得期望层级为O(log n)，从而保证了期望时间复杂度。
时间复杂度
- 查找：期望O(log n)，最坏O(n)
- 插入：期望O(log n)，最坏O(n)
- 删除：期望O(log n)，最坏O(n)
- 空间：期望O(n)，每个节点平均有1/(1-p)个指针
完整Java实现
import java.util.Random;
/**
* 跳表（Skip List）实现
* 一种概率性数据结构，支持O(log n)期望时间复杂度的查找、插入和删除
* @param <T> 元素类型，必须实现Comparable接口
*/
public class SkipList<T extends Comparable<T>> {
/**
* 跳表节点
* 每个节点包含一个值数组forward，forward[i]表示第i层的下一个节点
*/
private static class Node<T> {
T value;
Node<T>[] forward; // 各层的下一个节点引用
@SuppressWarnings("unchecked")
Node(T value, int level) {
this.value = value;
this.forward = new Node[level + 1];
}
}
private static final double P = 0.5; // 提升到下一层的概率
private static final int MAX_LEVEL = 16; // 最大层数限制
private final Node<T> head; // 头节点，不存储实际数据
private int level; // 当前跳表的最大层数
private int size; // 元素个数
private final Random random;
public SkipList() {
this.head = new Node<>(null, MAX_LEVEL);
this.level = 0;
this.size = 0;
this.random = new Random();
}
/**
* 随机生成节点的层级
* 以概率P逐层提升，直到不提升或达到MAX_LEVEL
* @return 生成的层级（0-based）
*/
private int randomLevel() {
int lvl = 0;
while (random.nextDouble() < P && lvl < MAX_LEVEL - 1) {
lvl++;
}
return lvl;
}
/**
* 查找目标值在跳表中的位置
* 从最高层开始查找，逐层下降
* @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是小于target的最大节点，检查下一个节点
current = current.forward[0];
return current != null && current.value.compareTo(target) == 0;
}
/**
* 查找小于目标值的最大节点在各层的位置
* 这是插入和删除操作的前置步骤
* @param target 目标值
* @return 各层前驱节点数组
*/
private Node<T>[] findPredecessors(T target) {
@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(target) < 0) {
current = current.forward[i];
}
update[i] = current; // 记录第i层的前驱节点
}
return update;
}
/**
* 插入一个新值到跳表
* 如果值已存在则更新（本实现允许重复值）
* @param value 要插入的值
*/
public void insert(T value) {
Node<T>[] update = findPredecessors(value);
Node<T> current = update[0].forward[0];
// 如果值已存在，可以选择更新或忽略
// 本实现允许重复值插入
int newLevel = randomLevel();
// 如果新节点的层级超过当前最大层级，更新头节点的forward指针
if (newLevel > level) {
for (int i = level + 1; i <= newLevel; i++) {
update[i] = head;
}
level = newLevel;
}
// 创建新节点
Node<T> newNode = new Node<>(value, newLevel);
// 在各层插入新节点：将新节点的forward指向原后继，前驱的forward指向新节点
for (int i = 0; i <= newLevel; i++) {
newNode.forward[i] = update[i].forward[i];
update[i].forward[i] = newNode;
}
size++;
}
/**
* 从跳表中删除指定值
* @param value 要删除的值
* @return 如果找到并删除返回true，否则返回false
*/
public boolean delete(T value) {
Node<T>[] update = findPredecessors(value);
Node<T> target = update[0].forward[0];
// 检查目标节点是否存在且值匹配
if (target == null || target.value.compareTo(value) != 0) {
return false;
}
// 逐层删除目标节点
for (int i = 0; i <= level; i++) {
if (update[i].forward[i] != target) {
break; // 更高层没有该节点，提前退出
}
update[i].forward[i] = target.forward[i];
}
// 如果最高层变空，降低当前层级
while (level > 0 && head.forward[level] == null) {
level--;
}
size--;
return true;
}
/**
* 查找大于等于目标值的最小元素
* @param target 目标值
* @return 大于等于目标值的最小元素，如果不存在返回null
*/
public T ceiling(T target) {
Node<T>[] update = findPredecessors(target);
Node<T> node = update[0].forward[0];
return node != null ? node.value : null;
}
/**
* 查找小于目标值的最大元素
* @param target 目标值
* @return 小于目标值的最大元素，如果不存在返回null
*/
public T floor(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];
}
}
return current.value; // head.value为null时需特殊处理
}
/**
* 获取跳表大小
*/
public int size() {
return size;
}
/**
* 检查跳表是否为空
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 打印跳表结构，用于调试和可视化
*/
public void printStructure() {
System.out.println("Skip List Structure (size=" + size + ", level=" + level + "):");
for (int i = level; i >= 0; i--) {
System.out.print("Level " + i + ": ");
Node<T> current = head.forward[i];
while (current != null) {
System.out.print(current.value + " -> ");
current = current.forward[i];
}
System.out.println("null");
}
}
/**
* 主程序：演示跳表的基本操作
*/
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 val : data) {
skipList.insert(val);
}
skipList.printStructure();
// 查找测试
System.out.println("\n查找测试:");
System.out.println("contains(12): " + skipList.contains(12));
System.out.println("contains(20): " + skipList.contains(20));
// 范围查询测试
System.out.println("\n范围查询:");
System.out.println("ceiling(15): " + skipList.ceiling(15));
System.out.println("floor(15): " + skipList.floor(15));
// 删除测试
System.out.println("\n删除测试:");
System.out.println("delete(12): " + skipList.delete(12));
System.out.println("contains(12): " + skipList.contains(12));
skipList.printStructure();
// 大量数据性能测试
System.out.println("\n性能测试 (100000次插入和查找):");
SkipList<Integer> perfTest = new SkipList<>();
long start = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
perfTest.insert(i);
}
long insertTime = System.currentTimeMillis() - start;
start = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
perfTest.contains(i);
}
long searchTime = System.currentTimeMillis() - start;
System.out.println("插入耗时: " + insertTime + "ms");
System.out.println("查找耗时: " + searchTime + "ms");
System.out.println("最终大小: " + perfTest.size());
}
}
关键算法解析
1. 概率性层级生成
randomLevel()方法以概率p=0.5决定节点层级。数学期望上，层级为0的节点占50%，层级为1的占25%，层级为k的占1/2^(k+1)。期望层级为1/(1-p)=2，最大期望层级为O(log_{1/p} n)。
2. 查找过程
查找从level层开始。在每一层尽可能向右移动，当无法继续时下降到下一层。由于高层的”跨度”大，每次可以跳过大量元素。最终在最底层精确定位。
3. 插入与删除的层间联动
插入时需要维护一个update数组，记录各层中目标位置的前驱节点。新节点创建后，只需调整这些前驱的forward指针即可完成所有层的链接。删除同理。
复杂度分析
| 指标 | 期望复杂度 | 最坏复杂度 | 说明 |
|---|---|---|---|
| 查找 | O(log n) | O(n) | 期望层级为O(log n) |
| 插入 | O(log n) | O(n) | 包含查找和指针调整 |
| 删除 | O(log n) | O(n) | 包含查找和指针调整 |
| 空间 | O(n) | O(n log n) | 每个节点平均2个指针 |
总结
跳表通过概率性层级构建，以极简单的代码实现了与红黑树、AVL树相当的时间复杂度。其核心优势在于：
- 实现简单：无需复杂的旋转操作，代码量远小于平衡树
- 并发友好：天然支持无锁并发（通过CAS操作），Redis正是利用这一特性
- 范围查询高效：有序性使得区间遍历非常自然
本文实现的跳表支持基本的增删查操作以及ceiling/floor范围查询，可作为有序集合数据结构的Java实现参考。
