引言
在前面数据结构系列中，我们学过二分查找——在有序数组中查找一个数，时间复杂度 O(log n)，非常快。但如果数据存储在链表中呢？链表不支持随机访问，只能从头一个个找，查找退化到 O(n)。
有没有办法让链表也能"二分查找"？跳表（Skip List）就是答案。它在原始链表之上建立多层索引，高层索引跳过大量节点，底层索引精确定位，从而实现 O(log n) 的查找效率。
跳表由 William Pugh 于 1990 年提出，论文标题就是"Skip Lists: A Probabilistic Alternative to Balanced Trees"——它是平衡树的概率替代方案。相比红黑树，跳表实现简单得多，但性能相当，因此被 Redis ZSet、LevelDB、Kafka 等众多系统采用。
第一部分：跳表的核心原理
一、多层索引 = "空间换时间"
想象一本书的目录：要找到第 7 章，你不会从第 1 页开始翻。你会先看大目录（章标题），定位到第 7 章大概在书的中间位置，然后再翻到那一页。
跳表就是这样：原始链表是"书的正文"，每一层索引就是一个"目录"。层数越高，索引越稀疏，"跳"得越远。
二、节点层数如何确定
跳表的关键问题：一个节点应该建几层索引？
答案：随机决定。这正是跳表最巧妙的地方——不需要复杂的平衡算法，用概率保证整体效率。
#define MAX_LEVEL 16 // 最大层数 // 随机生成层数（抛硬币） int randomLevel() { int level = 0; while (rand() % 2 == 0 && level < MAX_LEVEL) { level++; } return level; }第二部分：跳表的操作
一、数据结构定义
#include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <limits.h> #define MAX_LEVEL 16 typedef struct SkipNode { int key; // 键值 int value; // 值 struct SkipNode* forward[MAX_LEVEL + 1]; // 各层的后继指针 } SkipNode; typedef struct { SkipNode* header; // 头节点（哨兵） int level; // 当前跳表的最大层数 } SkipList;forward数组：forward[i]表示该节点在第 i 层的下一个节点。forward[0]就是原始链表的下一个节点。
二、初始化
SkipList* createSkipList() { SkipList* list = (SkipList*)malloc(sizeof(SkipList)); list->level = 0; // 创建头节点，所有层的 forward 初始为 NULL list->header = (SkipNode*)malloc(sizeof(SkipNode)); list->header->key = INT_MIN; // 哨兵，最小键值 for (int i = 0; i <= MAX_LEVEL; i++) { list->header->forward[i] = NULL; } return list; }三、查找
// 查找，返回 key 对应的 value，未找到返回 -1 int search(SkipList* list, int key) { SkipNode* cur = list->header; // 从最高层开始 for (int i = list->level; i >= 0; i--) { // 在这一层一直向右，直到碰到比 key 大的节点 while (cur->forward[i] != NULL && cur->forward[i]->key < key) { cur = cur->forward[i]; } // 如果这一层不能再向右了，下一层 } // 此时 cur 在第 0 层的下一个节点，要么是目标，要么不存在 cur = cur->forward[0]; if (cur != NULL && cur->key == key) { return cur->value; } return -1; }四、插入
插入需要做两件事：随机生成新节点的层数，然后在每一层找到插入位置并插入。
// 插入（如果 key 已存在则更新 value） void insert(SkipList* list, int key, int value) { // update[i] = 在第 i 层插入新节点时，新节点的前驱是谁 SkipNode* update[MAX_LEVEL + 1]; SkipNode* cur = list->header; // 1. 从最高层开始，找到每层的插入位置（前驱节点） for (int i = list->level; i >= 0; i--) { while (cur->forward[i] != NULL && cur->forward[i]->key < key) { cur = cur->forward[i]; } update[i] = cur; // 记录这一层的前驱 } cur = cur->forward[0]; // 2. key 已存在 → 更新 value if (cur != NULL && cur->key == key) { cur->value = value; return; } // 3. 随机生成新节点的层数 int newLevel = randomLevel(); if (newLevel > list->level) { // 新节点层数超过当前最大层数 → 更新头节点的 forward for (int i = list->level + 1; i <= newLevel; i++) { update[i] = list->header; } list->level = newLevel; } // 4. 创建新节点 SkipNode* newNode = (SkipNode*)malloc(sizeof(SkipNode)); newNode->key = key; newNode->value = value; // 5. 在每一层插入（和链表插入一样：新节点指向前驱的后继，前驱指向新节点） for (int i = 0; i <= newLevel; i++) { newNode->forward[i] = update[i]->forward[i]; update[i]->forward[i] = newNode; } }插入过程图解：
五、删除
// 删除 void delete(SkipList* list, int key) { SkipNode* update[MAX_LEVEL + 1]; SkipNode* cur = list->header; // 找到每层的前驱 for (int i = list->level; i >= 0; i--) { while (cur->forward[i] != NULL && cur->forward[i]->key < key) { cur = cur->forward[i]; } update[i] = cur; } cur = cur->forward[0]; // 如果找到了，在每一层删除 if (cur != NULL && cur->key == key) { for (int i = 0; i <= list->level; i++) { if (update[i]->forward[i] == cur) { update[i]->forward[i] = cur->forward[i]; } else { break; // 这一层没有了，上面层也不会有了 } } free(cur); // 如果最高层变空了，降低跳表层级 while (list->level > 0 && list->header->forward[list->level] == NULL) { list->level--; } } }第三部分：完整代码与测试
#include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <limits.h> #include <time.h> #define MAX_LEVEL 16 typedef struct SkipNode { int key; int value; struct SkipNode* forward[MAX_LEVEL + 1]; } SkipNode; typedef struct { SkipNode* header; int level; } SkipList; int randomLevel() { int level = 0; while (rand() % 2 == 0 && level < MAX_LEVEL) { level++; } return level; } SkipList* createSkipList() { SkipList* list = (SkipList*)malloc(sizeof(SkipList)); list->level = 0; list->header = (SkipNode*)malloc(sizeof(SkipNode)); list->header->key = INT_MIN; for (int i = 0; i <= MAX_LEVEL; i++) { list->header->forward[i] = NULL; } return list; } int search(SkipList* list, int key) { SkipNode* cur = list->header; for (int i = list->level; i >= 0; i--) { while (cur->forward[i] != NULL && cur->forward[i]->key < key) { cur = cur->forward[i]; } } cur = cur->forward[0]; if (cur != NULL && cur->key == key) return cur->value; return -1; } void insert(SkipList* list, int key, int value) { SkipNode* update[MAX_LEVEL + 1]; SkipNode* cur = list->header; for (int i = list->level; i >= 0; i--) { while (cur->forward[i] != NULL && cur->forward[i]->key < key) { cur = cur->forward[i]; } update[i] = cur; } cur = cur->forward[0]; if (cur != NULL && cur->key == key) { cur->value = value; return; } int newLevel = randomLevel(); if (newLevel > list->level) { for (int i = list->level + 1; i <= newLevel; i++) { update[i] = list->header; } list->level = newLevel; } SkipNode* newNode = (SkipNode*)malloc(sizeof(SkipNode)); newNode->key = key; newNode->value = value; for (int i = 0; i <= newLevel; i++) { newNode->forward[i] = update[i]->forward[i]; update[i]->forward[i] = newNode; } } void delete(SkipList* list, int key) { SkipNode* update[MAX_LEVEL + 1]; SkipNode* cur = list->header; for (int i = list->level; i >= 0; i--) { while (cur->forward[i] != NULL && cur->forward[i]->key < key) { cur = cur->forward[i]; } update[i] = cur; } cur = cur->forward[0]; if (cur != NULL && cur->key == key) { for (int i = 0; i <= list->level; i++) { if (update[i]->forward[i] == cur) { update[i]->forward[i] = cur->forward[i]; } else break; } free(cur); while (list->level > 0 && list->header->forward[list->level] == NULL) { list->level--; } } } void printSkipList(SkipList* list) { printf("跳表（最大层数=%d）：\n", list->level); for (int i = list->level; i >= 0; i--) { SkipNode* cur = list->header->forward[i]; printf("第%d层：", i); while (cur != NULL) { printf("%d -> ", cur->key); cur = cur->forward[i]; } printf("NULL\n"); } printf("\n"); } void freeSkipList(SkipList* list) { SkipNode* cur = list->header->forward[0]; while (cur != NULL) { SkipNode* tmp = cur; cur = cur->forward[0]; free(tmp); } free(list->header); free(list); } int main() { srand(time(NULL)); SkipList* list = createSkipList(); printf("===== 插入 1~10 =====\n"); for (int i = 1; i <= 10; i++) { insert(list, i, i * 10); } printSkipList(list); printf("===== 查找测试 =====\n"); printf("查找 5：%d\n", search(list, 5)); printf("查找 15：%d\n", search(list, 15)); printf("\n===== 删除 5 =====\n"); delete(list, 5); printSkipList(list); printf("===== 更新 3 =====\n"); insert(list, 3, 999); printf("查找 3：%d\n", search(list, 3)); freeSkipList(list); return 0; }第四部分：复杂度分析
| 操作 | 平均 | 最坏 | 说明 |
|---|---|---|---|
| 查找 | O(log n) | O(n) | 最坏发生在所有节点都在同一层 |
| 插入 | O(log n) | O(n) | 找位置 O(log n)，插入 O(层级) |
| 删除 | O(log n) | O(n) | 找位置 O(log n)，删除 O(层级) |
| 空间 | O(n) | O(n log n) | 每层约 n/(2^level) 个节点 |
第五部分：跳表 vs 平衡树
| 对比项 | 跳表 | 红黑树 |
|---|---|---|
| 查找 | O(log n) | O(log n) |
| 实现难度 | 简单（核心 100 行） | 复杂（核心 300+ 行） |
| 插入/删除 | 概率平衡，无需旋转 | 需要旋转和变色 |
| 范围查询 | 高效（第 0 层链表直接遍历） | 需要中序遍历 |
| 并发友好 | 容易加锁（每层独立） | 需要锁整棵树 |
| 内存占用 | 稍多（索引指针） | 较少 |
第六部分：实际应用
| 系统 | 用途 |
|---|---|
| Redis ZSet | 有序集合的底层实现之一（元素少时用压缩列表，元素多时用跳表） |
| LevelDB | MemTable 使用跳表 |
| Kafka | 索引文件使用跳表 |
| HBase | 内存索引结构 |
| ConcurrentSkipListMap | Java 并发容器 |
总结
一、核心要点
| 要点 | 内容 |
|---|---|
| 核心思想 | 多层索引，空间换时间 |
| 层数生成 | 随机抛硬币，期望分布，无需平衡操作 |
| 查找 | 从高层开始，向右+向下，O(log n) |
| 插入 | 找到每层前驱，在每层插入新节点 |
| 删除 | 找到每层前驱，在每层移除节点 |
| 最大优势 | 实现简单，适合并发，范围查询友好 |
二、代码框架记忆
查找：for(i=level; i>=0; i--)
while(右边<key) 向右
判断下一个是否==key插入：找到每层前驱 update[i]
随机层数 newLevel
在 0~newLevel 各层插入删除：找到每层前驱 update[i]
在 0~level 各层删除
更新最大层数
三、一句话记忆
跳表在有序链表上建多层索引，用"抛硬币"随机决定节点层数，实现概率平衡。从高层向右向下查找，期望 O(log n)。比红黑树实现简单得多，但性能相当，是 Redis ZSet 和 LevelDB 的底层结构。
