1. 从链表到跳表一个直观的演进思路如果你写过链表尤其是单链表一定对它的“线性”特性又爱又恨。爱的是它的插入和删除操作在已知节点位置的情况下时间复杂度是 O(1)非常高效。恨的是它的查找操作你必须从头节点开始一个节点一个节点地往后遍历直到找到目标时间复杂度是 O(n)。当数据量达到百万、千万级别时这种查找效率是无法接受的。我们自然会想有没有一种数据结构能保持链表动态插入、删除的灵活性又能拥有接近数组二分查找的高效查询能力跳表Skip List就是对这个问题的优雅回答。它的核心思想非常直观给链表加索引。想象一下你在看一本很厚的书如果只有正文你想找某个章节就得一页一页翻。但如果书前面有目录你就可以先看目录快速定位到大概的章节再翻到那附近仔细找。如果书更厚目录本身也很长那还可以给目录做一个更高级的“章节目录”。跳表就是这个思路的数字化实现。它通过在原始有序链表之上构建多层“索引”链表。最底层Level 0是包含所有元素的有序链表往上每一层都是下一层的一个“稀疏”子集相当于快速通道。查找时从最高层索引开始像坐电梯一样快速下降大幅度跳过不可能包含目标数据的区间最终在底层精确定位。通过这种“空间换时间”的策略跳表将查找、插入、删除的平均时间复杂度都降到了 O(log n)而其实现复杂度却远低于同样时间复杂度、需要严格平衡的红黑树或AVL树。2. 跳表的核心原理多级索引与概率提升理解跳表关键在于理解它的两个核心机制多级索引结构和基于概率的节点层高决定。我们先抛开代码用图解的方式彻底搞懂它。2.1 多级索引是如何工作的假设我们有一个有序链表存储了数字 1, 3, 4, 7, 9, 12, 15, 18, 19, 22。第一层索引Level 1我们从底层链表中每隔一个节点抽取一个建立一层新链表。比如抽取 1, 4, 9, 15, 19。这层链表节点数大约是底层的一半。第二层索引Level 2我们继续从第一层索引中每隔一个节点抽取一个比如抽取 1, 9, 19。节点数又少了一半。第三层索引Level 3可能只包含头节点和个别关键节点比如 1。现在这个数据结构看起来就像一个金字塔底部宽顶部窄。每一层都是一个有序链表高层链表的节点一定是低层链表节点的子集。查找过程例如查找 15从最高层Level 3的头节点开始。发现头节点指向 1且 1 15于是向右走到节点 1。在 Level 3 上节点 1 的下一个节点是 NULL或者是一个很大的尾节点值说明在 Level 3 这一层1 后面没有其他节点了。于是我们下降一层到 Level 2。在 Level 2 上节点 1 指向节点 9。9 15于是向右走到节点 9。在 Level 2 上节点 9 的下一个节点是 19。19 15说明目标 15 不可能在 9 和 19 之间于是我们从节点 9下降一层到 Level 1。在 Level 1 上节点 9 指向节点 15。15 15查找成功或者如果我们要找 14会发现 15 14则从节点 9 下降到底层 Level 0。在 Level 0 上节点 9 指向 1212 14走到1212指向1515 14查找结束确定 14 不存在。这个过程就像在一个有多条高速路和普通道路的城市里导航。你先上环线高层索引快速绕过大片区域接近目的地时下到辅路底层索引最后到达精确地点。通过高层索引的“跳跃”我们避免了在底层链表上的大量顺序比较。2.2 节点层高的概率决定为何它如此巧妙你可能会问插入新节点时如何决定它应该出现在哪几层索引中如果采用固定规则如每隔一个节点抽取那么在频繁插入删除后维护这个“每隔一个”的规则会非常昂贵需要大量调整。跳表采用了一个极其巧妙的策略概率决定。每个新节点在插入时通过一个随机过程来决定它的“高度”即它出现在多少层中。最常用的方法是“抛硬币”。具体过程如下每个节点至少存在于第 0 层底层数据层。我们开始“抛硬币”。如果硬币正面朝上那么这个节点就“晋升”到下一层索引中。我们为它创建这一层的节点。继续抛硬币如果再次正面则继续晋升到更上一层。一旦硬币反面朝上晋升过程就停止。假设硬币正反面概率各为 1/2。那么所有节点都在 Level 0。大约 1/2 的节点会出现在 Level 1。大约 1/4 的节点会出现在 Level 2。大约 1/8 的节点会出现在 Level 3。……这意味着高层索引的节点会非常稀疏。这个随机化策略带来了几个巨大好处实现简单插入时不需要全局调整结构只需要维护前后节点的指针。平衡性好虽然从单个插入操作看可能产生一个非常高的节点小概率事件但从统计意义上整个结构会趋向于平衡各层节点分布符合概率预期从而保证操作的平均时间复杂度。动态性强无论插入删除顺序如何结构都能自适应。注意在实际实现中我们通常会设定一个最大层数限制如 32 层防止因极小概率事件导致节点层高无限增长这对内存和性能都是保护。3. 手把手实现一个基础跳表理解了原理我们来实现一个支持插入、查找、删除的整型跳表。我们将使用 C 进行演示因为指针操作更贴近数据结构本质其他语言可以类比。3.1 数据结构定义首先我们需要定义节点和跳表本身的结构。#include iostream #include cstdlib #include ctime #include vector const int MAX_LEVEL 16; // 最大索引层数 // 跳表节点 struct SkipListNode { int value; std::vectorSkipListNode* forward; // 每层的前进指针数组 SkipListNode(int val, int level) : value(val), forward(level, nullptr) {} }; // 跳表 class SkipList { private: SkipListNode* header; // 头节点不存储实际数据但拥有MAX_LEVEL层指针 int currentLevel; // 当前跳表实际使用的最大层数 int randomLevel(); // 随机生成节点层高 public: SkipList(); ~SkipList(); bool search(int target); // 查找 void insert(int value); // 插入 void remove(int value); // 删除 void display(); // 打印调试用 };关键点解析forward向量这是跳表的核心。forward[i]存储了这个节点在第i层指向的下一个节点的指针。一个层高为level的节点其forward数组大小为level意味着它在 0 到level-1层都存在。header头节点它是一个哑元节点层高为MAX_LEVEL。所有查找、插入、删除操作都从header的最高层指针开始。它简化了边界条件处理。currentLevel记录当前所有节点中层高的最大值初始为 0只有头节点。查找时从这个层级开始可以避免无谓的遍历。3.2 核心操作查找、插入与删除查找操作是所有操作的基础插入和删除都需要先执行一个类似的查找过程来定位位置。bool SkipList::search(int target) { SkipListNode* current header; // 从最高层开始向下搜索 for (int i currentLevel - 1; i 0; --i) { // 在当前层 i 向前遍历直到下一个节点的值大于等于目标值 while (current-forward[i] ! nullptr current-forward[i]-value target) { current current-forward[i]; } // 循环结束时current-forward[i] 可能指向1. nullptr 2. 值 target 的节点 // 如果值等于 target在下层循环中会被精确找到。 } // 下降到第0层后current-forward[0] 就是目标位置 current current-forward[0]; return (current ! nullptr current-value target); }插入操作是最体现跳表精髓的。它需要先查找插入位置并记录下在每一层中插入点前驱节点是谁然后随机决定新节点层高最后更新指针。int SkipList::randomLevel() { int level 1; // 模拟抛硬币随机数若为偶数或某概率则增加层高 while ((rand() % 2) 0 level MAX_LEVEL) { level; } return level; } void SkipList::insert(int value) { std::vectorSkipListNode* update(MAX_LEVEL, nullptr); SkipListNode* current header; // 1. 查找插入位置并记录每层的前驱节点 for (int i currentLevel - 1; i 0; --i) { while (current-forward[i] ! nullptr current-forward[i]-value value) { current current-forward[i]; } update[i] current; // 记录第i层最后小于value的节点 } // 2. 检查值是否已存在根据需求跳表可允许或禁止重复值 current current-forward[0]; if (current ! nullptr current-value value) { // 值已存在处理策略可以更新、忽略或报错。这里选择忽略。 std::cout Value value already exists. std::endl; return; } // 3. 随机生成新节点的层高 int newLevel randomLevel(); // 4. 如果新节点层高超过当前跳表层高需要更新头节点指针和update数组 if (newLevel currentLevel) { for (int i currentLevel; i newLevel; i) { update[i] header; // 高于旧层数的部分前驱节点都是头节点 } currentLevel newLevel; } // 5. 创建新节点 SkipListNode* newNode new SkipListNode(value, newLevel); // 6. 逐层更新指针将新节点插入到每层的链表中 for (int i 0; i newLevel; i) { newNode-forward[i] update[i]-forward[i]; update[i]-forward[i] newNode; } std::cout Inserted value: value at level: newLevel std::endl; }提示update数组是插入和删除操作的关键。update[i]保存了在第i层中待插入/删除节点的前一个节点的指针。因为链表插入需要修改前驱节点的next指针。删除操作是插入的逆过程同样需要先查找并记录前驱节点。void SkipList::remove(int value) { std::vectorSkipListNode* update(MAX_LEVEL, nullptr); SkipListNode* current header; // 1. 查找目标节点并记录每层的前驱节点 for (int i currentLevel - 1; i 0; --i) { while (current-forward[i] ! nullptr current-forward[i]-value value) { current current-forward[i]; } update[i] current; } // 2. 定位到第0层的目标节点 current current-forward[0]; // 3. 如果节点存在且值匹配则进行删除 if (current ! nullptr current-value value) { // 4. 从底层到高层或任意顺序更新前驱节点的指针绕过当前节点 for (int i 0; i currentLevel; i) { if (update[i]-forward[i] ! current) { break; // 从某一层开始前驱节点不再指向current说明current不存在于更高层了 } update[i]-forward[i] current-forward[i]; } // 5. 删除节点 delete current; // 6. 可能更新currentLevel如果删除的是最高层的节点需要降低跳表层高 while (currentLevel 0 header-forward[currentLevel - 1] nullptr) { currentLevel--; } std::cout Removed value: value std::endl; } else { std::cout Value value not found. std::endl; } }3.3 一个完整的测试示例int main() { srand(time(nullptr)); // 初始化随机数种子 SkipList list; list.insert(3); list.insert(6); list.insert(7); list.insert(9); list.insert(12); list.insert(19); list.insert(17); list.insert(26); list.insert(21); list.insert(25); std::cout \nSearch for 19: (list.search(19) ? Found : Not Found) std::endl; std::cout Search for 20: (list.search(20) ? Found : Not Found) std::endl; list.remove(19); std::cout Search for 19 after removal: (list.search(19) ? Found : Not Found) std::endl; return 0; }4. 跳表的性能分析与工程实践要点跳表在理论上非常优美但在实际工程应用中有几个关键的细节和权衡点需要特别注意。4.1 时间复杂度与空间复杂度查找、插入、删除的平均时间复杂度都是 O(log n)。这里的 log 底数是多少这取决于“晋升概率” P。我们上面用的是 P1/2那么平均层高就是 log₂n。查找时每层遍历的节点数期望是 1/P 个这里是2个所以总的时间复杂度是 (log₁/ₚ n) * (1/P)常数项忽略后就是 O(log n)。当 P1/2 时性能与平衡二叉树相当。最坏情况时间复杂度O(n)。当随机数生成“运气极差”所有节点都只在第0层退化成普通链表。但概率极低且可以通过调整随机算法来避免。空间复杂度平均 O(n)。每个节点的平均层高是 1/(1-P)。当 P1/2 时平均每个节点有 2 个指针1个第0层 0.5个第1层 0.25个第2层...所以额外空间大约是 2n即 O(n)。4.2 关键参数调优晋升概率 P 与最大层数 MAX_LEVEL晋升概率 P这是跳表最重要的参数。P1/2 是最常见的选择在时间和空间上取得了很好的平衡。提高 P如 P3/4会使高层索引更密集查找时每层跳跃幅度变小但层数增长变慢。降低 P 则相反。Redis 的有序集合ZSET底层实现之一就是跳表它使用的 P1/4。更小的 P 意味着更稀疏的高层索引空间开销更小但查找时可能需要遍历更多的层。你需要根据实际的读/写比例和数据规模来权衡。最大层数 MAX_LEVEL必须设置。对于最多包含 N 个元素的跳表最大层数设为 log₁/ₚ N 是一个合理的选择。例如当 P1/2N2^32约43亿时MAX_LEVEL32 就足够了。设置过大浪费内存过小则限制性能。4.3 与平衡树的对比为何 Redis 和 LevelDB 偏爱跳表跳表常被拿来和红黑树、AVL树等平衡二叉搜索树比较。特性跳表 (Skip List)红黑树 (Red-Black Tree)平均时间复杂度查找、插入、删除 O(log n)查找、插入、删除 O(log n)最坏时间复杂度O(n) (概率极低)O(log n) (严格平衡)实现复杂度相对简单核心是链表操作非常复杂需处理多种旋转和变色情况范围查询非常高效找到起点后底层链表顺序遍历即可需要中序遍历不如跳表直观高效并发控制更容易实现无锁Lock-Free或细粒度锁。因为插入只需修改局部指针。实现无锁并发极其困难通常需要全局锁或复杂的锁机制。内存局部性较差节点内存分配随机指针跳跃访问。相对较好如果使用内存池或紧凑存储。Redis 选择跳表的原因实现简单bug 少易于维护和调试。支持高效的范围查询ZRANGE, ZREVRANGE这对于数据库场景至关重要。为并发优化提供了可能。虽然 Redis 是单线程的但简洁的结构为未来的扩展留下了空间。LevelDB/RocksDB 的 MemTable 在内存中存储近期写入的数据需要支持快速插入和查找。跳表实现简单且顺序遍历用于数据刷盘到SSTable效率高成为了比平衡树更优的选择。4.4 实现中的常见“坑”与调试技巧指针未初始化SkipListNode的forward向量初始化时必须将所有指针置为nullptr。野指针会导致程序崩溃。update 数组使用错误在插入和删除中update数组必须初始化为header并且大小至少为MAX_LEVEL。在更新指针时循环边界必须是newLevel或nodeLevel而不是currentLevel否则会漏掉或越界。内存泄漏删除节点时一定要用delete释放内存。在跳表析构函数中需要遍历底层链表删除所有数据节点。随机数质量使用rand()对于学习可以但在高性能或安全敏感场景下不够好。可以考虑使用random库中的std::mt19937。可视化调试实现一个display()函数逐层打印跳表是调试数据结构最有效的方法。它能让你一眼看出指针连接是否正确。void SkipList::display() { std::cout \n***** Skip List ***** std::endl; for (int i currentLevel - 1; i 0; --i) { SkipListNode* node header-forward[i]; std::cout Level i : ; while (node ! nullptr) { std::cout node-value ; node node-forward[i]; } std::cout std::endl; } }我个人在实现跳表时最常犯的错误是在插入操作的第6步更新指针时错误地使用了currentLevel作为循环边界。记住你只需要更新新节点所在的那newLevel层。另一个坑是在删除操作后更新currentLevel时循环条件必须是header-forward[currentLevel-1] nullptr并且要从高往低检查直到头节点在某层有后继节点为止。跳表是一种将“随机化”和“分层思想”结合得淋漓尽致的经典数据结构。它用可预期的额外空间换来了接近二分查找的效率同时保持了链表在插入删除上的优势。其简洁性使得它在并发编程和数据库系统中大放异彩。理解并实现它不仅能加深你对“空间换时间”和“概率算法”的理解更能让你在面临“需要有序且高效的数据结构”这一设计抉择时手中多出一张优雅而实用的王牌。下次当你需要快速实现一个有序容器原型时不妨先考虑一下跳表。
