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

一、什么是跳跃表1.1 为什么需要跳跃表普通单链表查找元素需要 O(n)。跳跃表通过建立多层索引让查找可以“跳过”部分节点达到类似二分查找的效果。示例查找 7text第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有序集合的底层实现LevelDBLSM 树的 MemTableLucene倒排索引的跳跃表优化二、跳跃表的结构设计2.1 节点结构每个节点包含值、层高、每层的后继指针。c#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 随机生成层高cint randomLevel() { int level 0; while ((rand() / (double)RAND_MAX) P level MAX_LEVEL - 1) { level; } return level; }2.3 创建节点cSkipNode* 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 初始化跳跃表cSkipList* 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 的节点然后下降一层继续。cint 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在每层插入新节点cvoid 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 数组记录每层要删除节点的前驱如果找到要删除的节点在各层将其跳过cint 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 遍历打印所有元素cvoid 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); }四、完整代码演示c#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: value170 未找到 100 删除测试 删除 7 (value70) 删除 19 (value190) 跳跃表共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)有序遍历支持支持不支持范围查询支持支持不支持空间开销较大中等中等并发友好较好一般差七、Redis ZSet 为什么用跳跃表Redis 有序集合ZSet在元素较多时使用跳跃表 哈希表的组合哈希表提供 O(1) 的单元素查找跳跃表提供有序遍历和范围查询选择跳跃表的原因实现比红黑树简单平均 O(log n) 性能足够好范围查询ZRANGE非常高效代码量少bug 更少八、小结这一篇我们实现了跳跃表操作核心算法查找逐层下降每层跳过小于 key 的节点插入查找每层前驱 随机层高 插入删除查找每层前驱 各层跳过节点关键点随机层高保证平均性能最高层数影响空间和速度的平衡Redis ZSet 底层就是这个结构下一篇我们讲算法思想递归与分治。九、思考题为什么跳跃表的层高要用随机生成而不是固定值如果 P 值增大如 0.75对跳跃表的性能有什么影响如何实现跳跃表的范围查询如查询所有 key 在 [a, b] 之间的节点跳跃表在并发环境下比红黑树有什么优势欢迎在评论区讨论你的答案。