跳表（Skip List）是一种基于概率的数据结构，由William Pugh于1990年提出。它通过在有序链表上构建多层索引，实现了与平衡树相当的O(log n)平均时间复杂度，同时代码实现远比红黑树、AVL树简单直观。跳表被广泛应用于Redis的有序集合（ZSet）、LevelDB等高性能系统中。
核心思想
跳表的核心思想是在有序链表上随机建立”快速通道”。底层是一个完整的有序链表，向上每一层都是下一层的子集，节点以一定概率（通常为1/2或1/4）晋升到更高层。查询时从顶层开始，利用索引快速跳过大量节点，逐层下沉至底层定位目标。
算法设计
节点结构
每个节点包含值、多层前向指针数组。层数通过随机函数决定，期望层数为O(log n)。
class SkipListNode {
int value;
SkipListNode[] forward; // 前向指针数组，forward[i]表示第i层的下一个节点
public SkipListNode(int value, int level) {
this.value = value;
this.forward = new SkipListNode[level + 1];
}
}
随机层数生成
使用几何分布决定节点层数，确保高层节点稀疏、低层节点密集。
private int randomLevel() {
int level = 0;
while (random.nextDouble() < P && level < MAX_LEVEL) {
level++;
}
return level;
}
查找算法
从最高层开始，比较当前节点与目标值，若小于目标则向右移动，否则下沉一层。
public boolean search(int target) {
SkipListNode current = head;
for (int i = level; i >= 0; i--) {
while (current.forward[i] != null && current.forward[i].value < target) {
current = current.forward[i];
}
}
current = current.forward[0];
return current != null && current.value == target;
}
插入算法
先找到每一层的前驱节点，再生成随机层数，最后逐层插入并更新前驱指针。
public void insert(int value) {
SkipListNode[] update = new SkipListNode[MAX_LEVEL + 1];
SkipListNode current = head;
// 从顶层向下查找每一层的前驱节点
for (int i = level; i >= 0; i--) {
while (current.forward[i] != null && current.forward[i].value < value) {
current = current.forward[i];
}
update[i] = current;
}
current = current.forward[0];
// 若值已存在，可选择更新或忽略
if (current == null || current.value != value) {
int newLevel = randomLevel();
// 若新节点层数超过当前最大层数，更新头节点指针
if (newLevel > level) {
for (int i = level + 1; i <= newLevel; i++) {
update[i] = head;
}
level = newLevel;
}
SkipListNode newNode = new SkipListNode(value, newLevel);
// 逐层插入新节点
for (int i = 0; i <= newLevel; i++) {
newNode.forward[i] = update[i].forward[i];
update[i].forward[i] = newNode;
}
}
}
删除算法
类似插入，先找到各层前驱，再逐层断开指针连接。
public boolean delete(int value) {
SkipListNode[] update = new SkipListNode[MAX_LEVEL + 1];
SkipListNode current = head;
for (int i = level; i >= 0; i--) {
while (current.forward[i] != null && current.forward[i].value < value) {
current = current.forward[i];
}
update[i] = current;
}
current = current.forward[0];
if (current != null && current.value == value) {
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--;
}
return true;
}
return false;
}
完整可运行代码
import java.util.Random;
/**
* 跳表实现 - 支持查找、插入、删除操作
* 平均时间复杂度: O(log n)
* 空间复杂度: O(n)
*/
public class SkipList {
private static final double P = 0.5; // 晋升概率
private static final int MAX_LEVEL = 16; // 最大层数
private final SkipListNode head;
private int level;
private final Random random;
private static class SkipListNode {
int value;
SkipListNode[] forward;
SkipListNode(int value, int level) {
this.value = value;
this.forward = new SkipListNode[level + 1];
}
}
public SkipList() {
this.head = new SkipListNode(-1, MAX_LEVEL);
this.level = 0;
this.random = new Random();
}
private int randomLevel() {
int lvl = 0;
while (random.nextDouble() < P && lvl < MAX_LEVEL) {
lvl++;
}
return lvl;
}
public boolean search(int target) {
SkipListNode current = head;
for (int i = level; i >= 0; i--) {
while (current.forward[i] != null && current.forward[i].value < target) {
current = current.forward[i];
}
}
current = current.forward[0];
return current != null && current.value == target;
}
public void insert(int value) {
SkipListNode[] update = new SkipListNode[MAX_LEVEL + 1];
SkipListNode current = head;
for (int i = level; i >= 0; i--) {
while (current.forward[i] != null && current.forward[i].value < value) {
current = current.forward[i];
}
update[i] = current;
}
current = current.forward[0];
if (current == null || current.value != value) {
int newLevel = randomLevel();
if (newLevel > level) {
for (int i = level + 1; i <= newLevel; i++) {
update[i] = head;
}
level = newLevel;
}
SkipListNode newNode = new SkipListNode(value, newLevel);
for (int i = 0; i <= newLevel; i++) {
newNode.forward[i] = update[i].forward[i];
update[i].forward[i] = newNode;
}
}
}
public boolean delete(int value) {
SkipListNode[] update = new SkipListNode[MAX_LEVEL + 1];
SkipListNode current = head;
for (int i = level; i >= 0; i--) {
while (current.forward[i] != null && current.forward[i].value < value) {
current = current.forward[i];
}
update[i] = current;
}
current = current.forward[0];
if (current != null && current.value == value) {
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--;
}
return true;
}
return false;
}
public void printList() {
for (int i = level; i >= 0; i--) {
SkipListNode node = head.forward[i];
System.out.print("Level " + i + ": ");
while (node != null) {
System.out.print(node.value + " -> ");
node = node.forward[i];
}
System.out.println("null");
}
}
public static void main(String[] args) {
SkipList skipList = new SkipList();
int[] values = {3, 6, 7, 9, 12, 17, 19, 21, 25, 26};
for (int v : values) {
skipList.insert(v);
}
System.out.println("跳表结构:");
skipList.printList();
System.out.println("\n查找 19: " + skipList.search(19));
System.out.println("查找 100: " + skipList.search(100));
System.out.println("\n删除 19");
skipList.delete(19);
System.out.println("查找 19: " + skipList.search(19));
}
}
复杂度分析
| 操作 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 查找 | O(log n) | O(n) | O(n) |
| 插入 | O(log n) | O(n) | O(n) |
| 删除 | O(log n) | O(n) | O(n) |
跳表通过概率保证平均性能，实际工程中可通过调整晋升概率P来平衡时间与空间：P越小，层数越少，空间越省但查询稍慢；P越大，索引越密集，查询越快但空间开销增加。
应用场景
- Redis ZSet有序集合的底层实现
- LevelDB、RocksDB等LSM-Tree存储引擎的MemTable
- 需要高效范围查询的有序数据场景
- 作为平衡树的简化替代方案
