C语言实现跳表：原理、内存布局与性能实测

跳表这个数据结构，教科书里常被归到“扩展阅读”，我第一次在 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做 key，void *做 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-free，ASan 一跑就报。

还要注意：销毁函数只释放节点结构，不会释放value指针指向的业务数据。如果 value 是 malloc 出来的，你需要自己遍历释放，否则就是内存泄漏。这也是 C 数据结构的通用坑：容器负责管理自己的结构，不负责管理用户数据。

4.2 迭代器设计与遍历顺序

跳表底层是一条完整的有序链表，所以迭代器比红黑树好做得多。最简单写法是只保存一个next指针和当前 key：

typedef 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 -fsanitize=address,undefined -o skiplist_demo main.c

ASan 会把 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/4，max_level 32，O2 编译。数据量级大致是：

这个数字只能当量级参考，不同机器差异很大。但相对关系是稳定的：插入比查找慢，因为要额外做随机层数和指针数组分配；删除比查找略快，因为删除的查找路径和查找相同，但最后修改指针的次数比插入少，不用生成随机层数。

如果连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，后来我换成跳表，插入性能提升明显，而且范围查询代码几乎没有改动。踩过几次坑之后，我总结出一个规律：凡是“有序、内存级、读写都频繁”的索引，跳表绝对值得优先考虑；凡是“数据量小、内存苛刻、要求最坏延迟”的场景，再考虑链表或平衡树。最后再分享一个小技巧：如果以后要做并发跳表，从最粗的读写锁开始，跑通正确性之后再谈无锁，否则你会在内存回收上被折磨到怀疑人生。