当前位置：首页 > news >正文

【数据结构与算法】第45篇：跳跃表（Skip List）

news 2026/4/15 2:04:32

一、什么是跳跃表

1.1 为什么需要跳跃表

普通单链表查找元素需要 O(n)。跳跃表通过建立多层索引，让查找可以“跳过”部分节点，达到类似二分查找的效果。

示例：查找 7

text

第2层: 1 ----------> 9 第1层: 1 -----> 5 -----> 9 第0层: 1 -> 3 -> 5 -> 7 -> 9 从第2层开始：1 < 7，到9 > 7，下降到第1层 第1层：5 < 7，到9 > 7，下降到第0层 第0层：7 找到

1.2 特点

优点	缺点
平均 O(log n) 查找	空间复杂度 O(n log n)
实现比平衡树简单	最坏情况 O(n)（但概率极低）
支持范围查询	随机数依赖
并发友好	内存开销较大

1.3 应用场景

Redis ZSet：有序集合的底层实现
LevelDB：LSM 树的 MemTable
Lucene：倒排索引的跳跃表优化

二、跳跃表的结构设计

2.1 节点结构

每个节点包含：值、层高、每层的后继指针。

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h> #define MAX_LEVEL 16 // 最大层数 #define P 0.5 // 概率因子（每上升一层的概率） // 跳跃表节点 typedef struct SkipNode { int key; // 键 int value; // 值 struct SkipNode **forward; // 每层的后继指针数组 } SkipNode; // 跳跃表 typedef struct { SkipNode *header; // 头节点（不存储数据） int level; // 当前最大层数 int size; // 节点个数 } SkipList;

2.2 随机生成层高

int randomLevel() { int level = 0; while ((rand() / (double)RAND_MAX) < P && level < MAX_LEVEL - 1) { level++; } return level; }

2.3 创建节点

SkipNode* createNode(int key, int value, int level) { SkipNode *node = (SkipNode*)malloc(sizeof(SkipNode)); node->key = key; node->value = value; node->forward = (SkipNode**)malloc((level + 1) * sizeof(SkipNode*)); for (int i = 0; i <= level; i++) { node->forward[i] = NULL; } return node; }

2.4 初始化跳跃表

SkipList* createSkipList() { SkipList *list = (SkipList*)malloc(sizeof(SkipList)); list->level = 0; list->size = 0; list->header = createNode(0, 0, MAX_LEVEL); return list; }

三、基本操作实现

3.1 查找

从最高层开始，每层找到最后一个小于 key 的节点，然后下降一层继续。

int search(SkipList *list, int key, int *value) { 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) { *value = cur->value; return 1; } return 0; }

3.2 插入

用 update 数组记录每层插入位置的前驱节点
随机生成新节点的层高
如果层高超过当前最大层，更新 update 中超出部分为 header
在每层插入新节点

void insert(SkipList *list, int key, int value) { 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]; // 如果 key 已存在，更新 value if (cur != NULL && cur->key == key) { cur->value = value; return; } // 2. 随机生成层高 int newLevel = randomLevel(); if (newLevel > list->level) { for (int i = list->level + 1; i <= newLevel; i++) { update[i] = list->header; } list->level = newLevel; } // 3. 创建新节点并插入 SkipNode *newNode = createNode(key, value, newLevel); for (int i = 0; i <= newLevel; i++) { newNode->forward[i] = update[i]->forward[i]; update[i]->forward[i] = newNode; } list->size++; }

3.3 删除

用 update 数组记录每层要删除节点的前驱
如果找到要删除的节点，在各层将其跳过

int delete(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) { return 0; // 不存在 } *value = cur->value; // 在各层删除节点 for (int i = 0; i <= list->level; i++) { if (update[i]->forward[i] != cur) break; update[i]->forward[i] = cur->forward[i]; } // 更新最高层数 while (list->level > 0 && list->header->forward[list->level] == NULL) { list->level--; } free(cur->forward); free(cur); list->size--; return 1; }

3.4 遍历（打印所有元素）

void printSkipList(SkipList *list) { printf("跳跃表（共%d个节点，当前最高层=%d）:\n", list->size, list->level); printf("第0层: "); SkipNode *cur = list->header->forward[0]; while (cur != NULL) { printf("(%d:%d) ", cur->key, cur->value); cur = cur->forward[0]; } printf("\n"); }

四、完整代码演示

#include <stdio.h> #include <stdlib.h> #include <time.h> #define MAX_LEVEL 16 #define P 0.5 typedef struct SkipNode { int key; int value; struct SkipNode **forward; } SkipNode; typedef struct { SkipNode *header; int level; int size; } SkipList; int randomLevel() { int level = 0; while ((rand() / (double)RAND_MAX) < P && level < MAX_LEVEL - 1) { level++; } return level; } SkipNode* createNode(int key, int value, int level) { SkipNode *node = (SkipNode*)malloc(sizeof(SkipNode)); node->key = key; node->value = value; node->forward = (SkipNode**)malloc((level + 1) * sizeof(SkipNode*)); for (int i = 0; i <= level; i++) { node->forward[i] = NULL; } return node; } SkipList* createSkipList() { SkipList *list = (SkipList*)malloc(sizeof(SkipList)); list->level = 0; list->size = 0; list->header = createNode(0, 0, MAX_LEVEL); return list; } int search(SkipList *list, int key, int *value) { 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) { *value = cur->value; return 1; } return 0; } 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 = createNode(key, value, newLevel); for (int i = 0; i <= newLevel; i++) { newNode->forward[i] = update[i]->forward[i]; update[i]->forward[i] = newNode; } list->size++; } int delete(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) { return 0; } *value = cur->value; for (int i = 0; i <= list->level; i++) { if (update[i]->forward[i] != cur) break; update[i]->forward[i] = cur->forward[i]; } while (list->level > 0 && list->header->forward[list->level] == NULL) { list->level--; } free(cur->forward); free(cur); list->size--; return 1; } void printSkipList(SkipList *list) { printf("跳跃表（共%d个节点，当前最高层=%d）:\n", list->size, list->level); for (int i = list->level; i >= 0; i--) { printf("第%d层: ", i); SkipNode *cur = list->header->forward[i]; while (cur != NULL) { printf("%d ", cur->key); cur = cur->forward[i]; } printf("\n"); } } void destroySkipList(SkipList *list) { SkipNode *cur = list->header->forward[0]; while (cur != NULL) { SkipNode *temp = cur; cur = cur->forward[0]; free(temp->forward); free(temp); } free(list->header->forward); free(list->header); free(list); } int main() { srand(time(NULL)); SkipList *list = createSkipList(); printf("=== 插入测试 ===\n"); int keys[] = {3, 6, 7, 9, 12, 17, 19, 21, 25, 26}; for (int i = 0; i < 10; i++) { insert(list, keys[i], keys[i] * 10); printf("插入 %d\n", keys[i]); } printSkipList(list); printf("\n=== 查找测试 ===\n"); int val; if (search(list, 17, &val)) { printf("找到 17: value=%d\n", val); } else { printf("未找到 17\n"); } if (search(list, 100, &val)) { printf("找到 100: value=%d\n", val); } else { printf("未找到 100\n"); } printf("\n=== 删除测试 ===\n"); if (delete(list, 7, &val)) { printf("删除 7 (value=%d)\n", val); } if (delete(list, 19, &val)) { printf("删除 19 (value=%d)\n", val); } printSkipList(list); destroySkipList(list); return 0; }

运行结果：

text

=== 插入测试 === 插入 3 插入 6 ... 跳跃表（共10个节点，当前最高层=4）: 第4层: 12 第3层: 3 12 25 第2层: 3 6 12 17 25 第1层: 3 6 7 9 12 17 19 21 25 第0层: 3 6 7 9 12 17 19 21 25 26 === 查找测试 === 找到 17: value=170 未找到 100 === 删除测试 === 删除 7 (value=70) 删除 19 (value=190) 跳跃表（共8个节点，当前最高层=4）: 第4层: 12 第3层: 3 12 25 第2层: 3 6 12 17 25 第1层: 3 6 9 12 17 21 25 第0层: 3 6 9 12 17 21 25 26

五、复杂度分析

操作	平均时间复杂度	最坏时间复杂度
查找	O(log n)	O(n)
插入	O(log n)	O(n)
删除	O(log n)	O(n)
空间	O(n log n)	O(n log n)

最坏情况概率极低（随机层高保证）

六、跳跃表 vs 平衡树 vs 哈希表

对比项	跳跃表	平衡树（AVL/红黑树）	哈希表
实现复杂度	简单	复杂	中等
平均查找	O(log n)	O(log n)	O(1)
有序遍历	支持	支持	不支持
范围查询	支持	支持	不支持
空间开销	较大	中等	中等
并发友好	较好	一般	差