如果你接手过一个需要常驻内存、按键有序、还要支持范围查询的映射结构大概率会在选型上纠结一阵哈希表查询快但无序有序数组遍历好但插入删除要搬数据红黑树理论完美但实现起来总让人头皮发麻。跳表 Skip List 是这类场景里性价比很高的选择——它在平均情况下给出 O(log n) 的查找、插入、删除代码量却比红黑树少一大截而且核心思想简单到可以用“抛硬币”来描述。这篇文章我会从选型逻辑讲起把跳表的层级结构、随机化机制、C语言完整实现、边界调试直到性能验证一次讲透。想直接抄代码的话可以跳到第三节但建议还是从头扫一遍把“为什么这样设计”带进代码里后面遇到问题才不会慌。跳表从结构上可以被看成一条有序链表叠加若干层“快速通道”每一层都是下层的一个抽样视图。最底层包含全部节点往上每层节点逐渐稀疏。查找时从最高层开始快速跳过大段距离逼近目标后再逐层下降最终落到底层完成精确匹配。整个过程既没有旋转也没有染色只靠两个动作向右看、向下走。1. 跳表到底解决什么问题有序容器选型的实际对比1.1 哈希表、有序数组、红黑树的边界在哪先把常见选项的真实边界捋清楚你才知道跳表在哪个位置填补了空白。结构点查询插入/删除有序遍历区间查询实现成本哈希表O(1) 平均O(1) 平均不支持需全量重新排序不支持低有序数组O(log n) 二分最坏 O(n) 移动元素支持支持低红黑树O(log n)O(log n)支持需要额外维护子树信息高跳表O(log n) 平均O(log n) 平均支持支持中低如果你的需求只有一条“给我一个很快的键值查询”哈希表是默认答案这也是绝大多数缓存模块选它的原因。但一旦需求变成“找出 key 在 [a, b] 范围内的所有记录”哈希表立刻失效——你只能把所有数据倒出来排序这在数据量稍大的场景下代价很高。有序数组在区间查询和顺序遍历上是强项二分查找也快但它有个致命短板插入一个元素平均要移动一半元素删除也一样。纯内存场景下如果数据变化频繁有序数组基本不可用。红黑树是很多教科书和系统模块里的标准答案。查找、插入、删除都是严格 O(log n)但它的问题只有真正实现过的人才知道插入时的变色和旋转已经够折腾删除时的双黑节点处理更是劝退主力。我见过不少团队用红黑树真出问题时没几个人能盯着树的形态把 bug 找出来。跳表正好补上这个空档平均 O(log n)实现思路直线化调试时可以把它当成“一堆有序链表”来看每一层都能打印出来核对。1.2 跳表的本质多层链表加概率化高速通道先想象一条普通的有序单链表查一个元素必须从头走到尾复杂度 O(n)。跳表的思路是在最底层链表之上每隔几个节点再拉一条“高架层”链表在更高层之上再按同样思路抽一层。查找时先用高架层快速掠过一大段发现过头了再降到下一层精确定位。这里有个关键设计点每个节点进入上一层不是“每隔固定数量抽一个”而是每个节点独立地、以概率 p 决定自己是否出现在上一层。这个随机化设计让结构在统计意义上保持均匀却避免了插入时为了维持严格比例而做的大量调整。红黑树用旋转和染色来维持平衡本质上是“强制的、确定性的平衡”跳表用概率把平衡变成“统计意义上的平衡”代价是极端情况下可能稍差但实际表现非常稳定。有人把这个结构与查字典类比你不会从第一页挨个翻到目标词而是先看目录、找到大致章节再翻到对应页精确查找。跳表的多层链表就是数据结构的“目录系统”层数越多目录级数越细查找跳过的数据就越多。1.3 什么时候选跳表什么时候不选选跳表最充分的理由是场景里同时出现“有序”“动态”“区间操作”。比如内存索引、排行榜、时间序列窗口扫描、范围分页这类需求用跳表写起来会比红黑树轻松一个量级维护成本也低。跳表对并发场景有天然的结构优势最底层是有序链表每个节点的指针可以独立修改方便做锁分离高层索引即使短暂不一致也不会影响最底层链表的正确性这是红黑树很难给的特性。不适合选跳表的场景也有内存极端紧张时每个节点平均要携带多个指针P0.5 时节点平均约 2 个 forward 指针加上配置管理字段比哈希表节点更胖对单次操作耗时要求特别苛刻的微秒级场景跳表多级指针跳转的缓存命中率不如紧凑数组不允许任何随机数、需要完全确定性上界的系统里红黑树或 B 树可能更稳妥。2. 跳表的结构与层级逻辑动手写代码前必须想清楚的三件事2.1 一个节点上要放几个指针固定数组还是柔性数组跳表节点实现上有两种主流形态固定大小数组和柔性数组。教学和多数工程选型里先用固定数组更直白。#define SKIP_MAX_LEVEL 16 typedef struct skip_node { int key; int value; struct skip_node *next[SKIP_MAX_LEVEL]; } skip_node;每个节点最多拥有 16 个 next 指针分别对应它可能出现的 16 层索引。header 哨兵节点不存数据它的 next 数组就是每层链表的头指针。一次插入时节点出现在哪些层由随机函数决定出现 3 层那它在索引 0、1、2 上都被链接进对应的链表。同一个节点在多个层同时存在这是跳表和处理树形结构最重要的视觉差异。静态数组的优点是代码简单、指针跳转没有二次计算缺点是每个节点固定带着 16 个指针16 × 8 字节等于 128 字节即使实际只用了两层空间也不释放。百万节点就是 128MB 级别的开销对大内存系统不友好。工程化一点的做法是 C99 柔性数组typedef struct skip_node_flex { int key; int value; struct skip_node_flex *next[1]; } skip_node_flex;创建节点时按实际层级分配static skip_node_flex *new_node_flex(int key, int value, int lvl) { size_t sz sizeof(skip_node_flex) (lvl - 1) * sizeof(skip_node_flex *); skip_node_flex *n (skip_node_flex *)malloc(sz); if (!n) return NULL; n-key key; n-value value; for (int i 0; i lvl; i) { n-next[i] NULL; } return n; }这样节点只分配自己实际用到的指针数组平均下来一个节点约 2 个指针空间省很多。教学代码想突出算法过程用固定数组生产代码建议直接上柔性数组或预分配内存池。2.2 为什么随机层级用“抛硬币”就够每个新节点的层级是由抛硬币决定的。把概率设为 p每次“正面”就继续向上加一层直到第一次“反面”或到达最大层级上限。这个过程会让层级分布呈现几何分布高度至少为 k 的概率是 p^(k-1)。高度期望值的计算很直观期望节点数 每层节点数之和 ≈ 1 p p² p³ ... 1 / (1 - p)。当 p0.5 时平均一个节点带约 2 个指针当 p0.25 时平均约 1.33 个指针空间更省但高层更稀疏、跳过的跨度变小查找时下钻次数变多。另一个需要提前想清楚的参数是最大层数。层数上限几乎完全由数据规模决定规模为 N 时理论最大有效层数大约在 log(1/p) N 这个量级。要多少层才够用心里要有个数数据规模log2(N) 约值建议 MAX_LEVEL1,0001016100,00017241,000,0002024~32100,000,0002732固定数组版可以直接把宏定义成 32够支撑上亿级别的数据规模。层级越高header 的 next 数组也越大但这部分只有一份开销忽略不计。2.3 查找的移动规则向右与向下跳表的查找过程必须形成肌肉记忆当前节点为 cur从 header 的最高有效层开始如果 cur-next[i] 非空且 cur-next[i]-key 目标键就向右移动否则不移动直接下降一层。循环结束后cur 就是最底层里最后一个键小于目标键的节点它的 next[0] 要么是目标节点要么是第一个大于目标键的节点。为什么判断条件用严格小于而不是小于等于因为查找不仅要负责点查询还要作为插入和删除的前驱定位工具。插入新节点时需要知道每一层里新节点的前驱是谁删除节点时需要知道每一层里被删节点的前驱是谁。用严格小于可以稳定地把 cur 停在前驱位置后续操作全部基于“前驱”展开。如果允许等于cur 可能直接停在目标节点上插入和删除时的 update 数组就会乱套。3. C语言从零实现结构体、初始化、查找、插入删除完整代码3.1 结构体与基础工具函数完整头文件和结构体定义如下。代码刻意保持简单用 int 类型承载 key 和 value实际工程里把这两个字段替换成业务类型或比较函数即可。#include stdio.h #include stdlib.h #include string.h #include time.h #define SKIP_MAX_LEVEL 32 #define SKIP_P 0.5f typedef struct skip_node { int key; int value; struct skip_node *next[SKIP_MAX_LEVEL]; } skip_node; typedef struct skip_list { int level; // 当前实际有效的最大层数 int size; // 最底层节点总数 skip_node *header; } skip_list; static int random_level(void) { int lvl 1; while (lvl SKIP_MAX_LEVEL (float)rand() / (float)RAND_MAX SKIP_P) { lvl; } return lvl; } static skip_node *new_node(int key, int value, int lvl) { skip_node *n (skip_node *)malloc(sizeof(skip_node)); if (!n) return NULL; n-key key; n-value value; for (int i 0; i SKIP_MAX_LEVEL; i) { n-next[i] NULL; } return n; } skip_list *sl_create(void) { skip_list *sl (skip_list *)malloc(sizeof(skip_list)); if (!sl) return NULL; sl-header (skip_node *)malloc(sizeof(skip_node)); if (!sl-header) { free(sl); return NULL; } memset(sl-header-next, 0, sizeof(sl-header-next)); sl-header-key 0; sl-header-value 0; sl-level 1; sl-size 0; return sl; }random_level 里的 while 循环每循环一次就是在抛一次硬币。float 比较存在极小概率的精度问题但作为教学实现完全够用生产环境更常见的做法是用一个 int 掩码或预计算概率区间来做避免随机数浮点转换的开销。初始化时把 header 的 next 全部置空跳表初始有效层级设为 1。这里有个新手容易忽略的点header 的层级上限虽然一直是 SKIP_MAX_LEVEL但真正参与查找的只有 sl-level 以下的层。level 表示“当前实际最高有效层”而不是“最高可配置层”。3.2 查找最容易被其他函数复用的骨架查找函数是后面插入、删除共同的骨架。建议先把这段逻辑刻进脑子后面看插入和删除都会轻松很多。skip_node *sl_find(skip_list *sl, int key) { skip_node *cur sl-header; for (int i sl-level - 1; i 0; i--) { while (cur-next[i] ! NULL cur-next[i]-key key) { cur cur-next[i]; } } cur cur-next[0]; if (cur cur-key key) { return cur; } return NULL; }循环里的两个条件缺一不可next[i] 非空是防止访问 NULL 的 nextkey target 保证了水平移动只在目标键之前进行。一旦条件不满足说明当前层已经走到最接近目标的节点就下降一层继续。这个函数的时间复杂度受随机层级约束。P0.5 时每一层期望跳过节点数较为恒定整体查找路径长度大约 O(log n)。如果随机函数写歪了比如一直返回 1跳表会退化成单链表复杂度变成 O(n)。这也是后面测试部分要重点检查的。3.3 插入update 数组保存每层前驱插入函数最关键的概念是 update 数组。它保存新节点在每一层的前驱节点。如果没有它新节点插进去之后你根本不知道每一层该由谁来指向它。先说一遍完整过程代码放在后面对照从 header 的最高有效层开始走把每一层最后一个小于 key 的节点记录到 update[i]检查最底层前驱的 next[0] 是不是键等于 key 的节点如果是直接更新 value 并返回随机出新节点层级 lvl如果 lvl 大于当前 sl-level说明新节点会出现在更高的全新层数这些新层的前驱都是 header需要手动补齐 update 数组从第 0 层开始到第 lvl-1 层把新节点接进链表。int sl_insert(skip_list *sl, int key, int value) { skip_node *update[SKIP_MAX_LEVEL]; skip_node *cur sl-header; for (int i sl-level - 1; i 0; i--) { while (cur-next[i] ! NULL cur-next[i]-key key) { cur cur-next[i]; } update[i] cur; } skip_node *exists cur-next[0]; if (exists exists-key key) { exists-value value; return 0; } int lvl random_level(); if (lvl sl-level) { for (int i sl-level; i lvl; i) { update[i] sl-header; } sl-level lvl; } skip_node *n new_node(key, value, lvl); if (!n) return -1; for (int i 0; i lvl; i) { n-next[i] update[i]-next[i]; update[i]-next[i] n; } sl-size; return 1; }update 数组只分配到 sl-level 层但随机 lvl 可能超过 sl-level这就是所谓的“新层接住 header”问题。如果不把超出部分的 update[i] 手动设为 header新节点不会出现在更高的层上sl-level 却被抬高了结构就会变得很奇怪实际的高层索引缺失查找性能下降。关于重复键这个版本选择“覆盖 value”。这样最底层链表的 key 唯一性不会被破坏。如果想改成拒绝重复插入只需要在检测到 exists 时返回一个特殊状态码不要修改 value。3.4 删除对称操作删除过程与插入是镜像关系先走同一套查找逻辑记录每层前驱找到目标节点后在所有层里把该节点摘除最后释放内存并收缩层级。int sl_delete(skip_list *sl, int key) { skip_node *update[SKIP_MAX_LEVEL]; skip_node *cur sl-header; for (int i sl-level - 1; i 0; i--) { while (cur-next[i] ! NULL cur-next[i]-key key) { cur cur-next[i]; } update[i] cur; } skip_node *target cur-next[0]; if (!target || target-key ! key) { return -1; } for (int i 0; i sl-level; i) { if (update[i]-next[i] target) { update[i]-next[i] target-next[i]; } } free(target); sl-size--; while (sl-level 1 sl-header-next[sl-level - 1] NULL) { sl-level--; } return 0; }注意删除时的 update[i] 是从最高有效层往下记录的但目标节点未必在每一层都出现。判断 update[i]-next[i] target 就是为了过滤掉那些没有链接 target 的层。如果直接无条件执行 update[i]-next[i] target-next[i]会把链表错误地接回 NULL 或指向不相关节点。删除后的层级收缩也很重要。假设最高的几层只剩 header-next 指向 NULL这些层已经没有任何节点继续保留只会让查找白白多跑几层。所以删除后要检查最顶层如果 header-next[level-1] 为 NULL就把 level 降下去直到顶层非空或只剩第 0 层。3.5 打印、销毁和 main 演示底层链表保存了全部节点销毁时必须从第 0 层逐节点释放绝不能从高楼层开始释放否则会漏节点或重复释放。void sl_dump(skip_list *sl) { for (int i sl-level - 1; i 0; i--) { printf(level %2d: , i); skip_node *cur sl-header-next[i]; while (cur) { printf(%d(%d) , cur-key, cur-value); cur cur-next[i]; } printf(\n); } } void sl_destroy(skip_list *sl) { if (!sl) return; skip_node *cur sl-header-next[0]; while (cur) { skip_node *tmp cur; cur cur-next[0]; free(tmp); } free(sl-header); free(sl); }外围演示可以直接写个小 main。实际做正确性验证时建议固定随机种子保证每一次跑出来的随机层级分布完全一致方便排查问题。int main(void) { srand(0); // 固定种子可复现 skip_list *sl sl_create(); sl_insert(sl, 5, 50); sl_insert(sl, 3, 30); sl_insert(sl, 9, 90); sl_insert(sl, 1, 10); sl_insert(sl, 7, 70); sl_dump(sl); skip_node *f sl_find(sl, 7); if (f) { printf(find 7 - %d\n, f-value); } sl_delete(sl, 3); printf(after delete 3:\n); sl_dump(sl); sl_destroy(sl); return 0; }4. 最容易翻车的地方空表、重复键、层数收缩与并发4.1 空表删除和找不到的键拿到一个空跳表直接执行 sl_delete或者删除一个根本不存在的键代码必须先判空再判键。最典型的错误是在 target 为 NULL 时直接访问 target-key然后崩溃在奇怪的位置。正确习惯是先检查 cur-next[0] 是否为 NULL再检查 key 是否相等。这个检查顺序不能反过来否则读野指针。4.2 重复键插入等于覆盖还是拒绝重复键有两种语义覆盖值和拒绝插入。覆盖的实现最简单在插入函数里改了 value 就直接返回不生成新节点。拒绝插入也容易return 一个特殊状态码调用方根据状态码决定提示或忽略。无论选哪种都绝对不要在同一跳表里生成两个 key 完全相同的节点。如果允许多个相同 key 的节点存在find 会随机命中某一个delete 可能只删掉其中一个底层链表有序性直接崩坏。这个点在并发场景下尤其要守住。4.3 update 数组的经典错误新层没接住 header这是跳表实现里最高频的 bug没有之一。随机函数返回 5 层但当前 sl-level 只有 2那么新节点需要出现在第 3、4 层上这两层目前只有 header 在。如果忘记给 update[3]、update[4] 赋值 header那么新节点在这两层就不会被任何节点指向相当于它只插到了低两层。后果非常隐蔽查找时从高层开始跳永远跳不到新节点只有下降到最底层才能找到它。跳表的“快”就没了。而且这种问题在测试少量数据时几乎无法发现因为数据量小顺序查找也不慢。调试方法也很简单插入数据后把每一层打印出来对照最高层是否覆盖了新插入的大多数高层节点。一旦发现高层稀疏过度先检查随机层级部分再检查 update 补齐逻辑。4.4 删除后 level 不收缩的空层问题删除节点后如果不收缩 sl-levelheader-next 会留下几个全空的高层。查找时循环从最高层开始遇到空层会直接下降相当于多跑了几个无效迭代。数据规模大时空层数量可能不多影响有限但最坏情况下如果删除把高层的节点全部清掉sl-level 仍留在高位查找的起始层会比真实有效层高很多造成不必要的性能损耗。正确的收缩逻辑是循环判断 header-next[level-1] 是否为 NULL直到顶层非空或 level 降到 1。要注意 level 下限是 1不能缩到 0因为第 0 层永远存在。4.5 并发读写与内存管理的相关注意事项跳表在并发场景下比红黑树好处理主要原因是结构由多层链表组成每个节点的指针修改只影响附近节点可以设计细粒度的锁甚至可以往无锁方向走。最直接的做法是最底层用读写锁保护高层索引允许短暂的不一致需求简单时这个方案够用。C 语言里没有内置锁需要借助平台相关线程库。实际工程里我用过两种思路一是全局读写锁插入和删除加写锁查找加读锁简单可靠二是分层锁修改底层链表时锁对应桶或相邻区域能提高并发度但实现复杂度明显上升。内存方面每个节点独立 malloc 有几个隐藏问题分配耗时高、缓存不友好、碎片多。数据量大时可以用内存池预先分配一大块连续内存节点从池子里取释放时统一还回去。这个优化在跳表里效果很明显因为节点之间在内存中连续指针跳转时缓存命中率会好很多。5. 正确性验证与性能观察如何证明你的跳表没写歪5.1 写一个不变量校验函数调试跳表时最有力的工具是一个扫描函数逐层检查有序性和层间一致性。我自己习惯写完就配上这样的校验每跑一批用例后自动验证。int sl_check_invariant(skip_list *sl) { for (int i 0; i sl-level; i) { skip_node *cur sl-header-next[i]; int prev -1; while (cur) { if (cur-key prev) { return 0; // 本层无序 } prev cur-key; cur cur-next[i]; } } // 更高层必须能看到底层链表的子序列 skip_node *low sl-header-next[0]; for (int i 1; i sl-level; i) { skip_node *high sl-header-next[i]; while (low high) { if (low-key high-key) { high high-next[i]; } low low-next[0]; } if (high ! NULL) { return 0; // 高层节点不在底层链表中 } } return 1; }这个函数体现的核心性质有两个每一层链表本身按键递增任何一层的节点集合都是底层链表节点的子集。两个性质同时成立时跳表结构基本没有问题。5.2 固定随机种子让测试可复现随机化结构最怕间歇性 bug。比如某次随机出来的高层特别少导致查找缓慢而这个现象只在特定随机种子下出现。为了避免“换台机器就复现不了”测试时必须固定随机种子。固定种子之外建议把所有批量操作后的 size、每层节点数、总指针数都统计打印出来。每次插入删除后比较实际值能很快发现指针丢失或重复链接的问题。一个常见的测试套路是先插入 N 个随机乱序 key校验一次全部找到校验一次删除一半校验一次再删除剩下全部校验一次。任何一步不通过都能在当时就定位到具体操作类型大大提高排查效率。5.3 性能观察方法性能验证不需要特别复杂的工具用 clock() 就能看出数量级。clock_t start clock(); for (int i 0; i 100000; i) { sl_insert(sl, rand() % 1000000, i); } clock_t end clock(); printf(insert 100000: %.3f ms\n, (double)(end - start) * 1000.0 / CLOCKS_PER_SEC);注意事项编译时开 -O2否则调试版本和优化版本的表现差很远用顺序插入和随机插入各测一遍因为顺序插入会让高层链路分布偏向一边性能表现不同记录“数量级”而非“精确数字”跳表的随机特性决定了不同随机种子下性能有波动查找测试要区分“成功查找”和“失败查找”失败查找会一路探到 NULL路径和成功不太一样。最值得做的对照实验是同一批数据分别用跳表和有序链表插入然后比较查找耗时。普通链表在 10 万量级已经明显变慢跳表还保持稳定。这种直观对比比任何理论推导都更能说明问题。5.4 调整参数P值和MAX_LEVEL的权衡跳表的两个关键参数随时可以调节理解它们的影响比背公式更重要。P 值越大每层节点越多索引越密查找时每层跳的距离变短总查找步数减少但内存占用线性上升。P0.25 时平均指针约 1.33 个内存最省但查找较慢P0.5 是绝大多数场景的默认平衡点P0.75 适合查找极度频繁、插入较少、内存不敏感的场景。MAX_LEVEL 设置过低会有概率截断随机层级。比如数据规模 100 万理论最大有效层约 20 层如果 MAX_LEVEL 只有 16那么随机层级超过 16 时会被强行截断个别节点缺失高层索引整体性能会有一点随机性下降。所以 MAX_LEVEL 宁可设高一些不要设低了将就。固定数组版设 32 基本无忧。5.5 进一步优化柔性数组、预分配、无锁教学版本用固定数组已经足够但生产环境的高性能跳表至少要考虑三个方向柔性数组上一节已经提过空间优化很明显配合紧凑的内存池能进一步提高缓存命中率。再进一步可以把 key 和 value 贴近节点头部存储避免无关字段占位影响缓存行利用率。无锁跳表是一个庞大的话题核心思路是高层索引可以用原子指针的 CAS 操作来插入和删除只有最底层链表的临界操作才需要更仔细的线性化控制。C 语言可以实现得很精巧但对内存序和 ABA 问题处理要求很高。普通业务场景读写锁足够别为了炫技把稳定性搭进去。6. 收尾前再交代几句几个使用习惯与扩展方向最后分享几个我自己在跳表上实际踩坑后养成的习惯算不上什么高深理论但真能省时间。第一个习惯写代码前先画三层的链表结构图。见过太多只盯着代码、结果绕进指针迷宫里的人。跳表本质是多个层级有序链表画图时把每个节点的 next 数组分别画出来更新指针的顺序就一目了然了。第二个习惯随时打印最底层链表。底层链表是唯一包含全部节点的层高层索引只是它的投影。出问题时先看最底层绝大多数 bug 都发生在底层指针链接错误上底层对了再往上逐层看。第三个习惯随机层级生成函数单独测试。插入 10 万个节点后统计各层级节点数理论上每层大约是上一层的 P 倍。如果统计值和理论差异过大大概率是随机函数或概率参数写错了。扩展方向上跳表很方便加 rank 支持给每个节点增加一个 span 字段记录它在当前层跳过多少个节点这样就能在 O(log n) 时间内按排名取元素。再加一个 backward 指针就能支持从后往前遍历配合最底层链表可以做高效的双向区间扫描。如果未来需要支持任意类型的 key把 key 的比较逻辑提取成函数指针或接口即可核心结构完全不用动。学会跳表之后再看那些用到有序容器的系统设计思路会开阔很多。它不一定是最快的却是最容易让人真正掌控的数据结构之一。