跳表：高效查找的链表黑科技

引言在前面数据结构系列中我们学过二分查找——在有序数组中查找一个数时间复杂度 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有序集合的底层实现之一元素少时用压缩列表元素多时用跳表LevelDBMemTable 使用跳表Kafka索引文件使用跳表HBase内存索引结构ConcurrentSkipListMapJava 并发容器总结一、核心要点要点内容核心思想多层索引空间换时间层数生成随机抛硬币期望分布无需平衡操作查找从高层开始向右向下O(log n)插入找到每层前驱在每层插入新节点删除找到每层前驱在每层移除节点最大优势实现简单适合并发范围查询友好二、代码框架记忆查找for(ilevel; i0; i--)while(右边key) 向右判断下一个是否key插入找到每层前驱 update[i]随机层数 newLevel在 0~newLevel 各层插入删除找到每层前驱 update[i]在 0~level 各层删除更新最大层数三、一句话记忆跳表在有序链表上建多层索引用抛硬币随机决定节点层数实现概率平衡。从高层向右向下查找期望 O(log n)。比红黑树实现简单得多但性能相当是 Redis ZSet 和 LevelDB 的底层结构。