跳表这个数据结构教科书里常被归到“扩展阅读”我第一次在 C 语言里完整实现它之前也觉得这东西不过是个花哨的链表。真动手写了才发现跳表在工程里远比想象中能打有序集合的查找、插入、删除期望复杂度全部压到 O(log n)实现思路却比红黑树直白得多。这篇分享适合正在啃数据结构、想搞懂跳表原理的人也适合要在嵌入式环境或底层服务里手写内存索引的同学。我不打算只贴一份能跑的代码就结束而是会把设计思路、内存布局、随机层高这些最容易出问题的地方全部拆开再用常见报错和性能实测收尾。1. 跳表设计思路与原理拆解1.1 有序链表为什么不够用先看最朴素的做法一个有序单向链表查找某个 key 只能从头遍历平均复杂度 O(n)。插入数据也一样先要找到合适位置再改两个指针哪怕插入本身是 O(1)找位置已经把你拖回 O(n)。删除更麻烦还得记录前驱节点工程代码越写越脏。那数组呢数组可以二分查找复杂度 O(log n)但插入删除要搬动大量元素内存还得是连续的一大块一旦数据量上去扩容和碎片都让人头疼。平衡树比如 AVL、红黑树复杂度确实漂亮可实现细节繁琐旋转、着色、双亲指针任何一个环节写错都很难排。跳表就是另一种折中不追求完全平衡用概率和冗余指针换取简单直观的增删查。这结构早在 1990 年就有人提出Redis 的有序集合、不少存储引擎的内存索引都在用它。1.2 跳表是怎么“跳”起来的跳表的底层仍然是一个有序链表但每个节点不只有next还可能有一根、两根甚至更多根“跳跃指针”分别指到后面更远的位置。用图说话level 3: head ---------------------------------------- 99 level 2: head ------ 25 -------------- 77 ---------- 99 level 1: head - 10 - 25 - 41 - 60 - 77 - 88 - 99要找 77普通链表得走 6 步从 level 2 出发head 直接跳 25再从 25 跳到 77两步就到。越高的层节点越稀疏相当于高速上的快车道底层则保留全部节点保证任何元素都不会漏。每一层仍然是有序的所以查找时可以从最高层开始向右推进遇到下一个 key 大于目标就往下跳一层如此反复最后落到底层时要么找到要么确认不存在。这里的关键是“哪些节点能出现在高层”不能人为硬算否则一旦数据分布变化跳表就退化成链表。标准做法是随机每个节点独立地决定自己有多少层理论上已经证明只要随机函数合格跳表的查找期望复杂度就是 O(log n)和平衡树同一量级。1.3 为什么用 C 语言实现跳表用高级语言写很容易很多细节会被标准库容器隐藏掉。C 语言没有这些东西你得自己管理内存、自己处理指针数组、自己计算层高上限。这个过程其实特别适合用来搞懂数据结构本身。跳表的实际主力场景也往往就在 C 这一层嵌入式设备的查找表、网络服务的缓存索引、存储引擎里替代平衡树的内存表这些地方没有 GC没有运行时容器性能和内存可控是第一位的。用 C 写跳表还能直观感受到一个容易被忽略的成本指针数组分配。一次插入就要随机生成层数、分配节点、分配 forward 数组这些代码写不好内存碎片和分配器开销会比数据结构本身的算法复杂度更致命。所以后面我会重点讲内存布局这部分才是“能跑”和“好用”的分水岭。2. 核心数据结构与内存布局2.1 节点结构设计与头节点的特殊性先给一个基础结构。为了演示方便我用int64_t做 keyvoid *做 value后面会讨论怎么改成通用比较器。#include stdint.h #include stdlib.h #define SL_MAX_LEVEL 32 typedef struct sl_node { int32_t level; int64_t key; void *value; struct sl_node *forward[]; } sl_node; typedef struct { sl_node *head; int max_level; size_t length; double prob; } skiplist;这里最值得注意的是forward[]。它是一个柔性数组flexible array member每个节点只分配level个指针不写死固定大小。如果每个节点都定义成sl_node *forward[32]32 个指针就是 256 字节100 万个节点等于白白多占两百多 MB纯属浪费。头节点单独说。它不存有效数据只是用来提供每一层的起点。工程上我建议头节点的forward数组直接按SL_MAX_LEVEL一次性分配避免插入时因为层数涨了还要 realloc。头节点只有一个多占点内存无所谓但能省掉大量边界判断。static sl_node *create_head(void) { sl_node *h malloc(sizeof(sl_node) sizeof(sl_node *) * SL_MAX_LEVEL); h-level SL_MAX_LEVEL; h-key 0; h-value NULL; for (int i 0; i SL_MAX_LEVEL; i) { h-forward[i] NULL; } return h; }普通节点创建时用malloc(sizeof(sl_node) sizeof(sl_node *) * level)一次性把节点和指针数组都申请好。这样释放的时候只需要free(node)不用分两步也能减少一次 malloc 调用内存局部性更好。2.2 层高上限怎么定随机层数不是无限大的否则极端情况下一个节点可能随机出 1000 层浪费内存。层高上限通常按数据规模估算第 k 层期望有大约n * p^(k-1)个节点n 是元素数量p 是每层保留的概率。当 n 到 100 万、p 取 0.25 时log4(100万) 约等于 10所以理论上层高到 16 已经极其罕见地够用。工程上我习惯直接给 32留足余量也不至于让头节点付出太明显的内存代价。你可能会问层高上限是不是越大越好不是的。查找时要从max_level - 1往下走如果高层指针几乎全是 NULL那不过是多做了几次空判断对正确性没影响但对性能是纯损失。真正该避免的是把上限设到 64 甚至更高因为每次访问head-forward[i]都要跨缓存行扫描无效层的时间会被放大。2.3 随机层数的概率与实现随机层数的经典逻辑是这样每个节点至少 1 层然后以概率 p 增加一层再以概率 p 增加再上一层直到超过上限。p 的选择有讲究。p 1/2 时层更多查找路径短但节点平均指针数是1 / (1-p) 2内存多一些p 1/4 时节点平均指针数降到约 1.33内存更省但查找时每层能跳过的节点数变少常数略大。做内存索引我会优先选 1/4。随机数质量很重要。直接用rand() % 2生成层高问题很大不少库的rand()低位周期很短连续调用时结果并不独立会让跳表层高分布出现肉眼可见的偏差极端情况下甚至退化成链表。我常用一个简单的 xorshift 截断版本当练习用随机源static uint64_t rng_state 0x9E3779B97F4A7C15ULL; static uint32_t next_rand(void) { uint64_t x rng_state; x ^ x 12; x ^ x 25; x ^ x 27; rng_state x; return (uint32_t)((x * 0x2545F4914F6CDD1DULL) 32); } static int random_level(void) { int level 1; while ((next_rand() 0xFF) 64 level SL_MAX_LEVEL) { level; } return level; }这里 0xFF取低 8 位近似表示 [0, 255) 的随机数小于 64 的概率正好是 1/4。注意这只是演示写法低 8 位虽然能满足跳表需求但如果你要做密码学或者统计模拟应该换更严格验证过的随机数生成器。重点是跳表的正确性不依赖随机数“绝对均匀”但性能高度依赖它。宁可多花几行写一个靠谱生成器也别用一句rand() % 4糊弄过去。3. C 语言实现核心操作与关键细节3.1 查找从最高层滑下去查找逻辑一句话从最高层开始只要当前层下一个节点的 key 还小于目标 key就向右走走不动了就降到下一层。到底层后向右看一眼如果 key 恰好相等说明找到了。sl_node *sl_find(skiplist *sl, int64_t key) { sl_node *cur sl-head; for (int i sl-max_level - 1; i 0; i--) { while (cur-forward[i] ! NULL cur-forward[i]-key key) { cur cur-forward[i]; } } cur cur-forward[0]; return (cur ! NULL cur-key key) ? cur : NULL; }注意cur-forward[i]-key key用的是严格小于而不是小于等于。如果等于目标就停下落到下一层后我们才能确认这个节点是不是我们要找的。用小于等于会让你多跳一步虽然最后结果一样但代码语义绕排查问题时不直观。这个版本返回的是节点指针调用方可以读 value。如果想实现“找到后更新值”直接拿返回值改即可。3.2 插入先找前驱再接线插入比查找多一步需要知道每一层应该把新节点接在哪个节点后面所以先准备一个update数组记录每一层最后一个 key 小于新 key 的节点。然后随机生成新节点的层数把新节点逐层挂到update[i]后面。static sl_node *create_node(int level, int64_t key, void *value) { sl_node *n malloc(sizeof(sl_node) sizeof(sl_node *) * level); n-level level; n-key key; n-value value; return n; } int sl_insert(skiplist *sl, int64_t key, void *value) { sl_node *update[SL_MAX_LEVEL]; sl_node *cur sl-head; for (int i sl-max_level - 1; 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 0; } int lvl random_level(); if (lvl sl-max_level) { for (int i sl-max_level; i lvl; i) { update[i] sl-head; sl-head-forward[i] NULL; } sl-max_level lvl; } sl_node *node create_node(lvl, key, value); for (int i 0; i lvl; i) { node-forward[i] update[i]-forward[i]; update[i]-forward[i] node; } sl-length; return 1; }这里最容易漏掉的是random_level()返回值可能会超过当前的sl-max_level。如果新层比跳表现有最高层还高那么旧的高层上根本没有待插入的前驱所以update[i]必须填成头节点同时把头节点对应层的 next 置空。很多人的跳表越界崩溃就发生在这一步——去访问update[i]时发现它是未初始化的栈垃圾然后顺着垃圾地址写指针现场非常难看。如果 key 已经存在这里我选择更新 value 后返回 0。你也可以改成返回 1 表示冲突具体看你做的是 map 语义还是 set 语义。3.3 删除真删还是惰性删除删除有两种路线。一种是惰性删除给节点打个删除标记真正清理留到以后统一做。好处是删除操作很快也不用动那么多指针坏处是被删节点还留在底层链表里查找和遍历会持续看到过期数据内存压力也不会自动下降。另一种就是标准跳表删除找到节点把每一层前驱的指针绕过它然后释放内存。先说结论单线程环境下用真删。惰性删除更适合并发环境里的标记清理单线程做它纯属给自己加戏。int sl_delete(skiplist *sl, int64_t key) { sl_node *update[SL_MAX_LEVEL]; sl_node *cur sl-head; for (int i sl-max_level - 1; 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; } for (int i 0; i sl-max_level; i) { if (update[i]-forward[i] cur) { update[i]-forward[i] cur-forward[i]; } } free(cur); sl-length--; while (sl-max_level 1 sl-head-forward[sl-max_level - 1] NULL) { sl-max_level--; } return 1; }删除后要收缩sl-max_level。原因很实在如果最高两层都空了下次查找还会从这两层出发每层进去先判断 NULL纯浪费时间。收缩逻辑就是从头节点最高层往下数遇到空的就减一层。因为头节点的 forward 数组始终按SL_MAX_LEVEL分配这里不需要 realloc也不会丢数据。4. 工程化内存管理、迭代器与重复键处理4.1 内存申请与释放的常见坑单写一个sl_delete容易但一个完整的跳表一定还要有销毁函数。销毁整张表时别用递归节点可能有 100 万层深递归释放直接爆栈。正确做法是沿底层链表迭代释放void sl_free(skiplist *sl) { sl_node *cur sl-head-forward[0]; while (cur ! NULL) { sl_node *next cur-forward[0]; free(cur); cur next; } free(sl-head); slider free? free(sl); }这个函数里我用了柔性数组结构所以free(cur)一次就能把节点和它的 forward 数组全释放掉不用像分开 malloc 的实现那样先free(cur-forward)再free(cur)。如果你没有用柔性数组释放顺序写错就是 classic use-after-freeASan 一跑就报。还要注意销毁函数只释放节点结构不会释放value指针指向的业务数据。如果 value 是 malloc 出来的你需要自己遍历释放否则就是内存泄漏。这也是 C 数据结构的通用坑容器负责管理自己的结构不负责管理用户数据。4.2 迭代器设计与遍历顺序跳表底层是一条完整的有序链表所以迭代器比红黑树好做得多。最简单写法是只保存一个next指针和当前 keytypedef struct { sl_node *next; int64_t current_key; } sl_iter; sl_iter sl_iter_begin(skiplist *sl) { sl_iter it; it.next sl-head-forward[0]; it.current_key 0; return it; }每次迭代时先取it.next然后移动it.next it.next-forward[0]。这个设计的最大优势是遍历严格按 key 升序不会像平衡树那样需要维护栈或 parent 指针。但迭代器有一个大坑如果迭代过程中删除了当前节点it.next可能已经悬空。我通常建议迭代时只读不写真要边遍历边删除就把删除对象先记录到一个临时列表里遍历完再统一删。这个习惯能救你很多次。4.3 重复键、自定义比较器与范围查询当前实现遇到重复 key 是“覆盖更新”。如果业务需要同一个 key 挂多个值也就是 multiset 或者 multimap 语义可以在这个 key 底下再挂一个链表不过代码量会明显上涨。老实说真要做到生产级 multimap我会重新设计value字段而不是硬塞进跳表核心。更常见的需求是自定义比较器比如按字符串、按结构体字段排序。做法是把跳表里的 key 从int64_t改成void *在skiplist结构里加一个比较函数指针typedef int (*sl_compare_fn)(const void *a, const void *b); typedef struct { sl_node *head; int max_level; size_t length; double prob; sl_compare_fn cmp; } skiplist;查找和插入里的cur-forward[i]-key key改成sl-cmp(cur-forward[i]-key, key) 0即可。注意此时头节点里的 key 字段就没有业务含义了纯粹占位比较时别拿它参与运算。范围查询是跳表一个特别亮的功能。要找[lo, hi)之间的所有元素先按 lo 找到第一个不小于它的节点然后沿底层链表一路往后遍历到 hi 为止复杂度是 O(log n 输出数量)。这段代码可以直接加进库里void sl_range(skiplist *sl, int64_t lo, int64_t hi, void (*cb)(int64_t key, void *value, void *arg), void *arg) { sl_node *cur sl-head; for (int i sl-max_level - 1; i 0; i--) { while (cur-forward[i] ! NULL cur-forward[i]-key lo) { cur cur-forward[i]; } } cur cur-forward[0]; while (cur ! NULL cur-key hi) { cb(cur-key, cur-value, arg); cur cur-forward[0]; } }这个模式在做数据库范围扫描时很好用比平衡树实现起来省事得多。5. 常见问题与排查实录5.1 随机层高导致性能退化跳表最阴险的问题不是逻辑错误而是随机源看起来没问题、实际却让性能崩掉。之前调试过一个跳表插入 10 万数据时开始变慢后来发现是测试代码里每次插入前都重新srand(固定种子)导致所有节点随机出来的层高完全一样。表面上看每个节点都正常实际上高层指针全都在同一批节点上跳表退化成了链表查找复杂度变成 O(n)。排查思路很简单写一段统计代码把所有节点的 level 分布打出来。size_t level_count[SL_MAX_LEVEL] {0}; sl_node *p sl-head-forward[0]; while (p ! NULL) { level_count[p-level - 1]; p p-forward[0]; }如果 p 1/4理论上 level 为 1 的节点约占 75%level 为 2 的约占 18.75%逐层递减。如果统计结果出现大量相同 level或者高层节点比例异常先怀疑随机数别怀疑跳表逻辑。5.2 野指针与越界跳表崩溃点通常就两个地方插入新层时update[i]未初始化删除收缩层数后还去访问已经不存在的层。前者我在 3.2 里已经强调了后者比较隐蔽如果你删除代码里收缩了sl-max_level但某些历史节点还保留了高层的 forward 指针下一次插入时update数组可能没有覆盖到这些层于是旧指针残留在新链表结构里后续查找就可能走到已经 free 的节点。这类问题用 AddressSanitizer 很快就能暴露。编译时加gcc -g -O1 -fsanitizeaddress,undefined -o skiplist_demo main.cASan 会把 use-after-free 和堆越界直接拦下来并给你出错的调用栈。我建议所有实验代码都开 ASan 跑一遍单元测试别等线上崩了再对着 core dump 头疼。5.3 可视化打印辅助还有一个很土但很有效的调试手段把跳表每一层打出来。小数据量下肉眼扫一遍就能看出层的分布是否单调、指针是否断链。void sl_dump(skiplist *sl) { for (int i sl-max_level - 1; i 0; i--) { sl_node *cur sl-head-forward[i]; printf(L%d: , i 1); while (cur ! NULL) { printf(%lld - , (long long)cur-key); cur cur-forward[i]; } printf(nil\n); } }插入 16 个测试 key 后如果每一层都能看到完全递增的序列基本说明 insert 的指针操作没问题。我写跳表时的标准流程是先小规模随机插入dump 出来对照再随机删除一半再次 dump最后用 ASan 跑一遍 100 万级数据压力测试没问题才算过。6. 实测对比与性能表现6.1 三个核心操作的基准我自己在台式机上用随机 key 测过 10 万和 100 万两个规模p 取 1/4max_level 32O2 编译。数据量级大致是操作10 万随机 key100 万随机 key插入约 20 ms约 0.3 s查找约 15 ms约 0.25 s删除约 13 ms约 0.2 s这个数字只能当量级参考不同机器差异很大。但相对关系是稳定的插入比查找慢因为要额外做随机层数和指针数组分配删除比查找略快因为删除的查找路径和查找相同但最后修改指针的次数比插入少不用生成随机层数。如果连random_level的随机数生成换成最朴素的rand() % 2在 100 万规模下插入时间会明显上涨因为链表退化后查找路径变长这也侧面印证了随机源的重要性。6.2 空间开销实测柔性数组实现下每个节点需要存储 level、key、value以及平均约 1.33 个 forward 指针。算上 malloc 头开销和对齐单个节点约 40 字节左右。100 万节点大约占用 40 MB 多点比同样存 8 字节 key 的红黑树红黑树每个节点通常要 3 个指针左、右、父亲加颜色标记节点本身 48 字节起跳表在这个场景反而略省。但这里有个前提必须用柔性数组一次分配。如果每个节点拆成malloc(node)加malloc(forward_array)两次分配分配器 overhead 会让总内存直接多出 16 到 32 字节每节点100 万节点就是 16 MB 到 32 MB 的额外开销这还没算内存碎片。6.3 什么时候不要用跳表跳表不是万能银弹。数据量只有几十个时普通有序链表最简单何必引入随机和指针数组。如果内存极其紧张且分配器 overhead 敏感一个实现良好的红黑树可能更紧凑。如果你的场景要求最坏情况延迟有严格上界跳表的随机性会让 p99 不太稳定这时候需要确定性结构或者用带预算的确定性跳表变体。还有一个工程上的考量跳表的 forward 全是单向的。如果你频繁需要从后往前遍历比如要做倒序输出那最好在节点里加一个prev指针实现双向跳表代码会多一截。否则在给定一个节点时想找它的前驱就非常尴尬只能从头查一遍。我个人在实际开发里被跳表救过不少次。某个内存索引组件最初用的是排序数组插入频繁导致大量 memmove后来我换成跳表插入性能提升明显而且范围查询代码几乎没有改动。踩过几次坑之后我总结出一个规律凡是“有序、内存级、读写都频繁”的索引跳表绝对值得优先考虑凡是“数据量小、内存苛刻、要求最坏延迟”的场景再考虑链表或平衡树。最后再分享一个小技巧如果以后要做并发跳表从最粗的读写锁开始跑通正确性之后再谈无锁否则你会在内存回收上被折磨到怀疑人生。