前面我们先后认识了平衡二叉搜索树里的 AVL 树和红黑树，它们靠"旋转 + 平衡因子 / 颜色"硬生生把一棵会退化的二叉搜索树压回对数高度。可是你有没有想过：查找结构一定要是"树"吗？我们能不能在链表上，也做出"二分查找"的体验？本期的主角跳表（Skiplist）就是一个"敢在链表的底盘上做多层索引"的异类。它不用旋转、不用颜色，只靠"掷硬币"式的随机，就把查找稳稳地维持在 O(logN)。更妙的是，它实现起来比红黑树简单得多，还偏偏被 Redis 看中去当了有序集合的底层。今天我们就把它掰开揉碎，从"为什么要做多层"一路写到"一行行把代码敲出来"。
为什么需要跳表：有序链表的困境
先说跳表的本质。跳表本质上是一种查找结构，解决的是"查找"问题——给定一个 key，找出它对应的数据。这个定位跟平衡搜索树、哈希表的价值是一样的：既可以只存 key，做"在不在集合里"的判定；也可以存 key/value 的映射，做"由 key 找 value"。跳表是 William Pugh 在 1990 年发表的论文《Skip Lists: A Probabilistic Alternative to Balanced Trees》中提出的，它要给"平衡树"提供一个基于概率的替代品。
那么相比平衡树，它凭什么值得被当作"替代品"？先别急着回答，等你学完它怎么实现、怎么保证效率，我们再回头把三种结构摆到同一张桌子上对比。
跳表的名字很有画面感：先是一个 list。没错，它的地基就是有序链表——所有元素按 key 从小到大串成一个链表。问题是，在纯有序链表里查找一个元素，只能从头往后一个个比较，时间复杂度是 O(N)。你想想，10 万个节点、要找的是最后一个，得摸完 9 万多个节点才见到它，太慢了。
到这里你的第一反应可能是：那用有序数组不就得了，数组可以二分查找，O(logN)。对，但数组二分有两个前提换来代价：要么是静态数据（建好后不增删），要么增删都要 O(N) 地搬移元素。链表的增删（定位后）是 O(1) 的，但它找到了头却没法"跳"。跳表的野心就是：保留链表的便利，却在链表的表象上，长出数组二分那样的"跳跃能力"。
思考题 1：为什么有序链表查找是 O(N)？既然数组能二分到 O(logN)，为什么不干脆用数组？
详解答案：有序链表是线性结构，任意两个相邻节点之间没有"跳过一段"的捷径，要从头找第 k 个必须走 k 步，所以最坏要比较 N 个节点、走 O(N) 步，即 O(N)。有序数组虽然支持下标随机访问、可以二分到 O(logN)，但二分有一个隐藏前提——你必须先知道"中点在哪"，而这要求常数时间访问任意位置。链表做不到"常数时间访问任意位置"（你要访问中间节点，得一路走过去）。更致命的是，数组一旦要插入/删除元素，就要把其后所有元素整段搬移，是 O(N)。跳表想要的，正是"拿数组二分的速度 + 链表增删的便利"两头的优点。
第一层优化：让相邻节点升高一层
William Pugh 的出发点很朴素：我们能不能在有序链表上，人为地"架设"一些跳过中间节点的指针，让查找少比较几次？
他的第一个设想是这样：假如让每相邻两个节点升高一层，在这两个节点的"上一层"之间连一条新指针，让这条新指针直接从第 k 个节点指向第 k+2 个节点（即下下个节点）。如图 b：
（a）普通有序链表 （b）隔一个升高一层
19 -> 22 -> 28 -> 33 -> 38 -> 44 -> 56 *----> 22 --------> 33 ----> ...
| | | |
19 -> 22 -> 28 -> 33 -> 38 -> 44 -> 56 19 -> 22 -> 28 -> 33...
// 更直白地看第二层：
┌─────────────────────────────────────────────┐
│ L1: 22 ─────▶ 33 ─────▶ 44 ─────▶ ... │ ← 新加的高层指针，指向下下个
│ L0: 19 ─ 22 ─ 28 ─ 33 ─ 38 ─ 44 ─ 56 │ ← 原来的有序链表
└─────────────────────────────────────────────┘
所有新加的指针，在视觉上连成了一条新的链表，它包含的节点个数只有原来的一半（因为跳过了偶数位）。当我们要查找一个目标时，不再需要和原来链表里的每个节点都逐个比较——先在高层的这条"稀疏链表"上大步走，走到差不多位置再降回底层精确定位。这样需要比较的节点数，"大概只要原来的一半"。这就是"少比较"的第一个来源。
继续升高：多层链表的两分思想
既然升高一层就能省一半，那以此类推：在第二层新产生的链表上，继续让每相邻两个节点再升高一层、加一条指针，又产生第三层链表。如图 c：
L2: 28 ─────────────▶ 56 ─▶ ...
L1: 22 ─────▶ 33 ─────▶ 44 ───▶ ...
L0: 19 ─ 22 ─ 28 ─ 33 ─ 38 ─ 44 ─ 56 ─ ...
一层层叠上去，你就得到了一个多层的"目录表"。观察这个结构会发现一个漂亮的性质：按照这种"每层都隔一个升一层"的生成方式，上面每一层链表的节点个数，恰好是下面一层的一半。这跟二分查找的切割方式一模一样——每往上一层，相当于跨过了底层的两个"单位"。因此，查找的过程就非常类似二分查找：从最上层出发，目标太大就往右、目标比下一个元素小就往下降，逐层逼近，从而把查找的复杂度从 O(N) 压到了 O(logN)。
这个"目录式"直觉非常重要，你要在心里把它定格成这两句口诀：
- 能往右就尽量往右走（这一层的下一个节点还小于目标，说明目标还在更后面，向右最能加速）。
- 走不过去就往下掉（这一层的下一个节点大于目标或已经到尾部，说明目标夹在当前节点和下一个节点之间，只能降到更细的层级去定位）。
严格比例的代价：插入删除会把理想打回原形
上面这套"每层半减"的结构，理论上很完美，可它有一个几乎不可饶恕的缺陷——插入和删除会把它搅得一团糟。
你想，我们之所以能维持"上层节点数 = 下层的一半"，靠的是严格的 2:1 对应关系：每相邻两个第一层节点，才允许一个节点升级到第二层。一旦插入一个节点或者删除一个节点，这个"隔一个升一层"的节奏就被打破了：
- 删除一个节点，它可能正好是那些"充当上层指针端点"的节点之一，删掉它，上面的指针就会指向错误的邻居。
- 插入一个节点，等于在底层"插队"，那么从它开始往后的相邻关系全都变了——原本"逢二升一"的配对整段失效。
为了恢复这种严格的 2:1 关系，你就必须把新插入节点后面所有的节点（也包括新插入节点自己）全部重新调整一遍——重新决定谁升谁不升、重新改上面的指针。这可就糟了：一次看似 O(1) 的链表插入，因为要"修补上层目录"，代价又回到了 O(N)。我们费力压下去的复杂度，在增删面前全线崩溃。这正是"理想结构"和"现实需求"之间的根本矛盾：比例太严格的结构，增删就太脆弱。
思考题 2：为什么不能让"上层节点数 = 下层节点数的一半"变成一条硬性维护的规则？
详解答案：因为这条规则是全局性的、跨层的。它要求"哪些节点应该出现在上层"由"它在底层的编号"决定（逢偶数位才出现），而一旦增删一个节点，底层所有节点的"编号"都会变化，随之"谁该出现在哪一层"这一整套映射都要重算。最坏情况（比如删除第一个节点）会触发断层，波及后续几乎全部节点，导致每次增删需要调整 O(N) 个指针、代价瞬间回到 O(N)。也就是说，严格比例换来的低搜索复杂度，被增删的高维护成本彻底抵消，得不偿失。所以跳表必须找到一个"不依赖全局编号"的新机制。
破除执念：随机层数
为了逃脱"全局编号"这个枷锁，跳表做了一个非常大胆、甚至有点反直觉的设计——不再严格要求上下层之间的比例关系。取而代之的是：当插入一个节点时，随机地给它摇出一个层数。新节点该有多高，跟它前面、后面的节点一点关系都没有，它想高就高、想低就低。
这个改动的好处立竿见影：每次插入和删除，都只关心"我这一条竖线上的前后几个指针该怎么接"，完全不需要考虑其他节点的层数。不存在"你影响了我的编号所以要重排"这种连锁反应。插入就是插入，删除就是删除，周围该接谁接谁，干净利落。之前把我们逼到 O(N) 的"全局一致性"，就这样被一个"每个节点自己随机决定高度"的机制彻底拆解掉了。
一听"随机"两个字，你肯定要皱眉了：这也太随意了吧？效率不就是看运气了？ 别急，随机不等于乱来——"掷硬币"的结果虽然是随机的，但概率分布是受控的。下一节我们就精确地挖一挖，这个"随机层数"到底是怎么摇出来的、它的分布长什么样，从而说明为什么"看似随意"却依然稳定快。
随机层数是怎么算出来的：maxLevel 与概率 p
跳表的随机层数绝不是"从天而降"的均匀随机，它由两个参数精确定义：
- maxLevel（最大层数）：一个上限，防止极端情况下层数无限高。任何节点最高的层数都不会超过它。
- p（概率）：一个 0 到 1 之间的数，表示"在已有当前高度基础上，再升高一层的概率"。
随机算法（伪代码）如下：
int RandomLevel():
level = 1
while random() < p 且 level < maxLevel:
level += 1
return level
翻译成人话：从第 1 层出发，掷一次"有偏硬币"（以概率 p 成功）。成功了就升到第 2 层，再掷一次；又成功就再升到第 3 层……一旦哪次失败（概率 1-p），或者已经摸到 maxLevel 的上限，就停止，当前层数就是该节点的层数。
读几遍这个循环你会品出关键一句：产生的节点层数越高，需要的"连续成功"次数越多，概率就越低。这是一个典型的几何分布——越往上越稀缺。它保证了"绝大多数节点都很矮、只有极少数节点长得很高"，而恰恰是这些耸立的高个节点，为查找提供了"跨层跳跃"的骨架。
那么，Redis 实际是怎么取这两个参数的呢？在 Redis 的跳表实现中，取的是 p = 1/4、maxLevel = 32（源码里 ZSKIPLIST_P 为 0.25、ZSKIPLIST_MAXLEVEL 为 32）。maxLevel=32 不是随便定的：当 p=1/4 时，期望最高层 ≈ log_{1/p} N = log₄ N，而要容纳 N=2⁶⁴（一个天文数字级的数据量）也只需要 log₄ 2⁶⁴ = 32 层，所以 32 层对任何"真实世界"的跳表都绰绰有余。（这条结论在后面"概率分布"一节会给出依据。）
思考题 3：为什么说"越高的层越稀缺"？请用 p=1/4 推一推"恰好有 2 层"和"恰好有 3 层"的概率分别是多少。
详解答案：因为升高到下一层需要一次成功的"掷硬币"。一个节点要恰好停留在第 k 层，意味着它要连续成功 k-1 次（升到第 k 层），然后第 k 次失败。所以 P(恰好 k 层) = p^(k-1)·(1-p)。以 p=1/4 代入：恰好 2 层 = p·(1-p) = (1/4)·(3/4) = 3/16 ≈ 0.1875；恰好 3 层 = p²·(1-p) = (1/16)·(3/4) = 3/64 ≈ 0.0469。可以看到，每向上一层，概率就缩小到原来的 p（这里是 1/4），层数越高越稀有，这就是"稀缺"的定量含义。
概率分布与平均层数（期望高度）
现在把随机层数的概率分布完整列出来（设 p = 单次升高概率，且暂时忽略 maxLevel 的截断，认为"无限高"）——这对于理解"为什么 O(logN)"和"每个节点平均占多少指针"都至关重要。
设节点层数为 L，则：
| 事件 | 概率 |
|---|---|
| L ≥ 1 | 1（层数至少为 1，这是起点） |
| L ≥ 2 | p |
| L ≥ 3 | p² |
| L ≥ 4 | p³ |
| … | … |
| L ≥ k | p^(k-1) |
用"恰好等于"来表述更清楚：节点层数恰好等于 k 的概率是 p^(k-1)·(1-p)。这个式子我们对 思考题 3 已经用过了。而"至少"行里的 p^(k-1)，是从"恰好"累加而来的：L ≥ k 意味着 k-1 次连续成功，即 p^(k-1)。
接着算一个非常有用的量——一个节点的平均层数（也就是平均包含的 forward 指针个数）、也叫期望高度。用著名的"期望 = ∑ 各正整数取到的概率"这条恒等式：
E[L] = Σ_{k=1}^{∞} P(L ≥ k) = 1 + p + p² + p³ + … = 1/(1-p)
（这里用到了等比级数求和，公比 p < 1。）这个结果漂亮又干净：
- p = 1/2 时，平均层数 = 1/(1 - 1/2) = 2，即每个节点平均有 2 个指针。
- p = 1/4 时，平均层数 = 1/(1 - 1/4) = 1/(3/4) = 4/3 ≈ 1.33，即每个节点平均只有 1.33 个指针。
这个"平均指针数"几乎决定了一个跳表的内存开销，也直接参与后面与红黑树的对比。你留意到没有：p 越小，节点越"矮"，跨度越大——因为升级更难，高层节点更稀疏。p=1/4 时平均每节点才 1.33 个指针，内存非常省。
思考题 4：请用"期望 = ∑ P(L ≥ k)"精确证明：一个节点的期望层数是 1/(1-p)。
详解答案：对非负整数值随机变量 L，有一个求和恒等式 E[L] = Σ_{k=1}^{∞} P(L ≥ k)（它把"值求和"换成了"累积生存概率求和"，两者一致，可用画网格图或归纳验证）。由跳表的分布，P(L ≥ k) = p^(k-1)，代入：E[L] = Σ_{k=1}^{∞} p^(k-1) = 1 / (1-p)。这正是首项为 1、公比为 p 的无穷等比级数之和。当 p=1/4 时它就是 4/3 ≈ 1.33。总之外层平均高度只由 p 决定，与数据规模 N 无关——这个"恒定的小常数"正是跳表内存代价的定值。
为何平均查找是 O(log N)
前面我们聊了"平均层数 = 1/(1-p)"这个内存侧的结论，现在补上查找侧最关键的 O(logN)。严格推导跳表的期望查找代价，其实比层数推导复杂一些，需要一定的概率功底，这里给你一条直觉 + 一个结论，想深究的老铁可以去看文末列的 Pugh 论文和铁蕾大佬的博客。
直觉是这样的：一个节点是"高个"的概率随层数指数衰减。当跳表里有 N 个节点时，绝大多数节点很矮（1~2 层），而能达到第 k 层的节点大约只有 N / p^(k-1) 个。于是第 k 层这条"高速路"上平均只有 N·p^(k-1) 个节点。当这个数字接近常数（比如几个）时——也就是 k ≈ log_{1/p} N——再往上的层基本是空的，没什么加速价值。因此查找时"从顶层向下穿透"的总步数，被这个"有效层数 ≈ log_{1/p} N"加上"每层最右走几步就下降"的常数上界所约束。
把两部分的期望求和，Pugh 证明了：跳表的期望查找/插入/删除时间都是 O(logN)，而且这个"期望"不依赖数据本身的长相（不像二叉搜索树的最坏情况取决于插入顺序），只取决于随机数的公平性。更厉害的是，它不会像平衡树那样有一个"必须时刻保持某种结构"的最坏情况——即便某次随机出现了很差的层数分配，也只会导致单次操作稍慢，整体期望依然是对数，且可以通过调大 p（让更高层存在）来压低常数。这是"概率平衡"独有的从容。
思考题 5：为什么"最高有效层 ≈ log_{1/p} N"具有直觉上的合理性？
详解答案：第 k 层平均约含 N·p^(k-1) 个节点。当 k 增大到使 N·p^(k-1) ≈ 常数（比如约等于 1~几 个）时，该"层"基本参量已稀疏到无太多跳跃价值，可以视为"实际能达到的顶"。取 N·p^(k-1) = 1，解得 k - 1 = log_{1/p} N，即 k ≈ log_{1/p} N + 1。例如 log₄ N：N=10⁶ 时约为 10 层，N=10⁹ 时约为 15 层，增长极其缓慢——这正说明了为什么跳表的层数与 N 是"对数"关系，而不是线性关系。直观上，"层数随 N 按对数增长"就让查找步数也具有对数上界。
节点结构：forward 指针数组与"层"
说了这么多理论，我们终于要动真格写代码了。第一个要设计的是节点。
在普通单链表里，一个节点只有一个 next 指针，它只属于"一条链"。但跳表的一个节点可能同时出现在多层链里（比如第 0 层、第 2 层），它在不同层上的"下一个节点"是不一样的。比如一个节点在第 0 层的 next 是它的直接后继，在第 2 层的 next 可能是隔了好几个的后继。
因此，跳表的节点不能只有一个 next，而得用一个forward 指针数组——数组的下标就是"层"，第 i 个元素就是"该节点在第 i 层的前进指针"。
约定两个首现术语：
- 层（level）：跳表中一条条水平链表；第 0 层（最底层）是"全量有序链表"，层数越高越稀疏。一个节点占据 1 到 maxLevel 之间的若干层。
- forward 指针：节点在第 i 层指向"右边下一个节点"的指针。一堆 forward 指针构成了"多层前进的骨架"。
在 C++ 里，节点定义成这样的结构体（对应《算法导论》式跳表，也是课件和 LeetCode 的 Design Skiplist 用的形式）：
#include <vector>
using namespace std;
// 跳表节点
struct SkiplistNode
{
int _val; // 节点存放的值（key）
vector<SkiplistNode*> _nextV; // forward 指针数组：第 i 个元素 = 该节点在第 i 层指向的下一个节点
// 构造：给定值和层数，开 n 个 forward 指针，全部先指向空
SkiplistNode(int val, int level)
: _val(val)
, _nextV(level, nullptr)
{}
};用 vector<SkiplistNode*> _nextV 而非固定长度数组，是因为每个节点的层数是随机、各不相同的——长尾分布决定了绝大多数节点只有 1~2 层，只有极少数节点有很多层。用变长 vector 按需分配，既省内存又灵活：高个节点拥有更多 forward 指针，矮个节点持有一个就够。节点的高度（_nextV.size()）就是它被随机出来的层数；_nextV[i] 就是它在第 i 层的 forward 指针。
头哨兵与空表的边界
跳表需要一个头节点（head）作为所有查找的起点。绝大多数实现里这个头节点是一个哨兵（sentinel）：它存放一个"比任何真实 key 都小"的占位值，自己不算有效数据，只负责提供一个"所有层的起点"。哨兵的好处是让"从整体第一层往下找"和"空表"这两种情况不用写额外的 if 分支。
在课件/LeetCode 实现里，头节点是一个值为 -1 的节点（LeetCode 的约定值），它有一个不错的地方：-1 比所有合法的 key 都小，于是查找时"下一个比 target 小就往右走"这个判断，从头节点出发就永远能顺滑地向右，不用为头节点单独开特例。
Skiplist()
{
srand((unsigned)time(nullptr)); // 用当前时间做随机种子，让每次运行 randomLevel 都不一样
_head = new SkiplistNode(-1, 1); // 头哨兵：值 -1，一开始只有第 0 层
}这里要特别厘清一个空表/只有头的边界：跳表构造出来时一个有效元素都没有，只有个体头节点，此时头节点只有第 0 层，底层链上除头节点外全是空（_head->_nextV[0] == nullptr）。所有操作（search/add/erase）在这种状态下都必须工作正常——尤其注意，当我们不断 add 再 erase，头节点的层数会像"电梯"一样先升上去、再降下来，最坏会降到"只剩第 0 层甚至 0 层"，这在"删除"一节会专门细抠。
（注：课件里只定义了 head 哨兵，没有花哨的"尾哨兵"；尾有多重语义冲突的文末会提一句，主流实现通常不单独设尾哨兵，这里先不引入。）
查找 search
查找的目标：给定 target，判断它是否存在于跳表中。思路就是我们两节前那句口诀的落地——从最高层出发，能往右就往右，走不动就往下。画成伪逻辑：
cur = head
level = head 的层数 - 1 // 从 head 的最高层开始
while level >= 0:
if cur 在第 level 层的下一个存在 且 它的值 < target:
cur 向右走到下一个 // 还能往右，加速
else if cur 在第 level 层的下一个为空 或 它的值 > target:
level 减一 // 走不过去，往下降一层
else:
return true // 下一个恰好 == target，找到了
return false // 走到最底层都没找到
我们把判断写成三段式，依次落到代码：
// 查找 target 是否存在，存在返回 true，否则返回 false
bool search(int target)
{
Node* cur = _head; // 从 head 出发
int level = (int)_head->_nextV.size() - 1; // 从 head 的最高一层往下开始
while (level >= 0) // 只要还没到第 0 层之下
{
if (cur->_nextV[level] // 该层存在下一个节点
&& cur->_nextV[level]->_val < target) // 且下一个值仍小于 target
{
cur = cur->_nextV[level]; // 太靠前，向右走到下一个，继续加速
}
else if (cur->_nextV[level] == nullptr // 该层已到链尾
|| cur->_nextV[level]->_val > target) // 或下一个值已经大于 target
{
--level; // 走不过去了，往下降一层精确定位
}
else
{
return true; // 走到这，说明下一个恰好等于 target，命中
}
}
return false; // 降到第 0 层之下仍未见，说明不存在
}留意 search 里一个精妙的判定顺序：每次先看"向右"是否可行（下一步比 target 小），若不行再看是否"该降落"（下一步为空或已大于 target）。由于跳表底层是有序的，"下一步不可能既小于又大于 target"，所以三个 if 分支互斥，else 分支必然对应"相等命中"。这个三段式是整个跳表的"心法"，插入和删除的前驱查找都会复用它，只是微调。
前驱集合 FindPrevNode
插入和删除都要做一件事：把一个节点接到链表里 / 从链表里摘下来。但跳表是"多层链"——一个节点可能横跨好几层，所以它的"前驱"不是一个节点，而是一串：在每一层上，它左边紧挨着它的那个节点，都需要记下来。这一串前驱，我们用 FindPrevNode 找出来。
FindPrevNode(num) 的功能：返回一个数组 prevV，prevV[i] 是在第 i 层上"值小于 num 的最靠右（即最接近 num）的节点"。换句话说，把要插入/查找的那个位置，想成"将来新节点的位置"，prevV[i] 就是它在第 i 层左邻。
// 找出"值 < num 且在各自层上尽量靠右"的前驱集合
vector<Node*> FindPrevNode(int num)
{
Node* cur = _head; // 从 head 出发
int level = (int)_head->_nextV.size() - 1; // 从最高层开始
// prevV 大小与 head 当前层数一致；先默认每个前驱都是 head（占位）
vector<Node*> prevV(level + 1, _head);
while (level >= 0)
{
// 还能向右加速就到右边去
if (cur->_nextV[level] && cur->_nextV[level]->_val < num)
{
cur = cur->_nextV[level]; // 同 search：向右边跳
}
else if (cur->_nextV[level] == nullptr // 链尾
|| cur->_nextV[level]->_val >= num) // 或下一个 >= num
{
prevV[level] = cur; // 记录：第 level 层的前驱就是当前 cur
--level; // 降到下一层，继续找更低层的前驱
}
}
return prevV; // 返回每层各自的前驱（头尾 & 中间各层）
}注意 FindPrevNode 与 search 有一处微妙差别：向下走的条件是 >= num（而不是 > num）。原因后面"插入/删除"会说——因为我们采用的是 "允许重复值"的语义（对应 LeetCode 的 Design Skiplist，同一个 key 可以 insert 多次、erase 删一个）。所以当遇到"下一个节点的值恰好等于 num"时，也要在它的左边停住（记录 prevV[level] = cur），这样下一个 num 插进来会排在旧 num 之前，而删除时才能通过"第 0 层前驱的下一个"定位到某个 num 节点。
思考题 6：为什么
FindPrevNode里向下走的判定用>= num，而search里用> target？两者互换会出什么问题？详解答案：
search的目标是"判是否存在"，当某个 next 恰好等于 target 时就应直接命中返回，所以它要"平等地拦下并检查相等的节点"。而FindPrevNode的目标是"拿到每个 value < num 的最右前驱"。若用>而不是>=，遇到 next == num 时会把它当成"可向右"继续走，从而跳过相等节点，前驱就落在第一个 num 之后，之后插入就会出现"新节点插到所有相等节点之后"，删除时也无法稳定定位到"待删的那一个"。用>=才能让前驱停在"小于 num 的最右"，把相等节点留在"前驱的右侧"，这样既不破坏顺序又可插入到相等序列正前方，删除也能确定地摘掉那一个。简单说：search 负责"找到即止"，FindPrevNode 负责"停在严格小于的位置"。
插入 add
插入分四步走：找前驱 → 摇层数 → 必要时拔高 head → 逐层接上前驱与后继。
先看前两步与后两步：
// 插入一个值 num（允许重复，同值可插多次）
void add(int num)
{
// 1. 先找到每一层的前驱集合
vector<Node*> prevV = FindPrevNode(num);
// 2. 随机摇出新节点的层数
int n = RandomLevel();
// 3. 如果新层数超过 head 当前的层数，把 head 升高，补几层新指针
// head 是所有层的"起点"，新高的层只有 head 这个起点才能"长出"指针
if (n > (int)_head->_nextV.size())
{
_head->_nextV.resize(n, nullptr); // head 再加 (n - 原size) 个空指针
prevV.resize(n, _head); // 新多出来的层，前驱默认设为 head
}
// 4. 创建新节点，逐层把 forward 指针串起来
Node* newnode = new Node(num, n);
for (size_t i = 0; i < (size_t)n; ++i) // 第 0..n-1 层都要链接
{
newnode->_nextV[i] = prevV[i]->_nextV[i]; // 新节点第 i 层指向"原前驱的后继"
prevV[i]->_nextV[i] = newnode; // 前驱第 i 层的新后继就是新节点
}
}第 3 步是这个函数里最容易忽略却必不可少的一处：新节点被摇出了 n 层，而如果 head 目前只有 height 层（height < n），那么上面 n - height 这些更新的层，除了 head 之外再没有任何节点，所以必须先把 head 的 forward 数组扩到 n，让它成为那些新层的起点，同时把新增层的前驱占位设为 head,新节点的这些高层的 forward 才能正确地指到它该去的地方。漏掉 resize(head) 这一句，新节点会带上几条"悬空的 forward"且无法从任何入口访问到，是一个隐蔽的 bug。
删除 erase 与头节点缩减
删除的思路：先找前驱；判一下第 0 层的前驱的下一个到底是不是 num——如果在，就把它从它出现的每一层都摘下来、释放内存；如果不在，说明 num 根本不在表里，返回 false。
// 删除一个值为 num 的节点；删成功返回 true，不存在则返回 false
bool erase(int num)
{
// 1. 找每一层的前驱（前驱的下一个可能就是要删的节点）
vector<Node*> prevV = FindPrevNode(num);
// 2. 判断第 0 层（全量有序链）上前驱的下一个是不是 num
// 因为一个节点只要能找到，在第 0 层必然能看到它
if (prevV[0]->_nextV[0] == nullptr // 第 0 层前驱后面是空
|| prevV[0]->_nextV[0]->_val != num) // 或者不是 num
{
return false; // num 不在跳表中，什么都不用删
}
// 3. 摘下"待删节点 del"，把它在每一层都从前驱的链里解出来
Node* del = prevV[0]->_nextV[0]; // 拿到待删节点的指针
for (size_t i = 0; i < del->_nextV.size(); ++i) // del 出现在哪些层就处理哪些层
{
prevV[i]->_nextV[i] = del->_nextV[i]; // 前驱第 i 层的 next 直接"越过" del
}
delete del; // 释放节点内存
// 4. 关键收尾：如果删的是最高层的节点，可能 head 下面的高层全部空了，
// 要把 head 的层数也"降下来"，否则 head 会顶着一堆永远为空的 high 指针
int i = (int)_head->_nextV.size() - 1; // 从 head 的最高层往下
while (i >= 0 && _head->_nextV[i] == nullptr) // 找到"第一个非空的高层"
{
--i;
}
_head->_nextV.resize(i + 1); // 收缩 head 到"最高非空层 + 1"，等于去掉空的天花板
return true;
}第 4 步是另一个很容易被跳过的坑，值得单独展开讲（这里也是课件里反复强调的"删除最高层节点后要把头节点的层数也降一下"）。为什么需要？
- 正确性：head 的层数代表"查找时从多高起步"。如果最高层的节点全被删光，head 的顶层指针就永远指向空。此时如果不去掉这些空的指针，后续
search/FindPrevNode会从这些空的高层开始：cur->_nextV[level] == nullptr→ 直接--level往下掉。虽然最终结果仍然正确（空层会立刻被跳过），但从性能上讲，等于每次操作都白白多踩几脚空层。 - 整洁与一致：head 永远只保留"到下一位真正还有节点"的层数，能让 prevV 的大小和现实保持一致，避免在 add 时面对一团冗长的空头。
思考题 7：删除后把 head 收缩层数，最多能缩到多少层？收缩到"只剩 0 层甚至空指针"时，后面的 add/search 还能正常工作吗？
详解答案：最多能缩到 0 层——即当跳表被删空（只剩 head 且 head 的每一层 next 都为空）时，
while会把 i 一路减到 -1，resize(0)让_head->_nextV变成一个空数组。此时 head 没有 forward 指针。后续操作都能正常工作：search里level = size() - 1 = -1，while(level >= 0)一次都不进，直接返回 false——空表当然搜索不到，正确；add里FindPrevNode返回空 prevV，随后的if (n > size())一定为真（n ≥ 1 > 0），会resize(n)重新把 head 撑起来并prevV.resize(n, _head)（不足的新层前驱默认 head），再逐层链接，照样能插入成功。所以"head 可以缩到 0 层"不是 bug，而是设计允许的极端边界，只要代码对size()==0（level == -1）的情形有正确兜底就安全。这也是为什么课件坚持用有符号的int变量来当level和i——若用size_t无符号去减到负数，会退化成天文数字，直接踩空指针，这是一类必踩的坑。
打印：让跳表真实可"见"
调试跳表最痛苦的就是"看不见"。我们定义一个能把跳表"画"出来的方法：逐层打印，每一行显示一路节点值，中间的层信息用竖线示意。这样你一眼就能看出谁高谁矮、指针怎么跨层。
// 逐层打印跳表的形状（visualize）
void Print()
{
int h = (int)_head->_nextV.size(); // 当前 head 的高度
for (int level = h - 1; level >= 0; --level) // 从最高层往下打
{
Node* cur = _head; // 每层都从 head 开始
printf("L%d: ", level); // 标出层级
cur = cur->_nextV[level]; // 越过 head 本身（head 是哨兵，不打）
while (cur)
{
printf("%d -> ", cur->_val);
cur = cur->_nextV[level]; // 沿该层的 forward 走
}
printf("null\n");
}
}一层一行，从最高层到最低层，你就能直观看到"上面的层稀疏、L0 全量"的典型形态。供你脑补一个小例子（插入 19,22,28,33,38,44,56 后，假设随机让它们的层数分别为 1,1,2,1,3,1,2）：
L2: 38 -> null
L1: 28 -> 38 -> 56 -> null
L0: 19 -> 22 -> 28 -> 33 -> 38 -> 44 -> 56 -> null
对照层数看：28、56 都是 2 层，所以它们出现在 L1；38 是唯一高度 3 的节点，独占 L2；其余全是 1 层，只出现在 L0。每一层的指针都严格保持"从左到右递增"的顺序，这正是跳表能快速跳跃的底气。
完整可编译的跳表实现
把散落各节的东西——节点、构造、查找、前驱集合、随机层数、插入、删除、打印、析构——全部拼成一个可以独立编译运行的完整程序。为了稳妥，我在这里把真实可用的随机层数、析构函数、以及能感知层高的打印都补全了。直接复制到 skiplist.cpp 就能跑：
#include <iostream>
#include <vector>
#include <cstdlib> // rand / srand
#include <ctime> // time
using namespace std;
// 跳表节点：forward 数组下标即"层"，第 i 个元素是该节点在第 i 层的前进指针
struct SkiplistNode
{
int _val; // 节点值（key）
vector<SkiplistNode*> _nextV; // forward 指针数组
SkiplistNode(int val, int level)
: _val(val), _nextV(level, nullptr) {}
};
class Skiplist
{
typedef SkiplistNode Node;
public:
Skiplist()
{
srand((unsigned)time(nullptr)); // 每次运行随机种子不同
_head = new Node(-1, 1); // 头哨兵 -1，初始只有第 0 层
}
~Skiplist() // 释放所有节点，防止内存泄漏
{
Node* cur = _head;
while (cur)
{
Node* toDelete = cur;
cur = cur->_nextV[0]; // 沿第 0 层全量链遍历
delete toDelete;
}
}
// 随机摇层数：p=1/4，上限 maxLevel
int RandomLevel()
{
size_t level = 1;
// 以概率 p 升一层；注意用浮点比较避免整型截断偏差
while ((double)rand() / RAND_MAX < _p && level < _maxLevel)
{
++level;
}
return (int)level;
}
// 查找 target 是否存在
bool search(int target)
{
Node* cur = _head;
int level = (int)_head->_nextV.size() - 1;
while (level >= 0)
{
if (cur->_nextV[level] && cur->_nextV[level]->_val < target)
cur = cur->_nextV[level]; // 向右加速
else if (cur->_nextV[level] == nullptr
|| cur->_nextV[level]->_val > target)
--level; // 走不过去，下降
else
return true; // 恰好相等
}
return false;
}
// 返回每一层"值 < num 的最右前驱"集合
vector<Node*> FindPrevNode(int num)
{
Node* cur = _head;
int level = (int)_head->_nextV.size() - 1;
vector<Node*> prevV(level + 1, _head);
while (level >= 0)
{
if (cur->_nextV[level] && cur->_nextV[level]->_val < num)
cur = cur->_nextV[level];
else if (cur->_nextV[level] == nullptr
|| cur->_nextV[level]->_val >= num)
{
prevV[level] = cur;
--level;
}
}
return prevV;
}
// 插入 num（允许重复）
void add(int num)
{
vector<Node*> prevV = FindPrevNode(num); // 各层前驱
int n = RandomLevel(); // 摇层数
if (n > (int)_head->_nextV.size()) // 层数超过 head，先拔高 head
{
_head->_nextV.resize(n, nullptr);
prevV.resize(n, _head);
}
Node* newnode = new Node(num, n);
for (size_t i = 0; i < (size_t)n; ++i) // 逐层接线
{
newnode->_nextV[i] = prevV[i]->_nextV[i];
prevV[i]->_nextV[i] = newnode;
}
}
// 删除一个 num；存在并删除则 true，否则 false
bool erase(int num)
{
vector<Node*> prevV = FindPrevNode(num);
if (prevV[0]->_nextV[0] == nullptr
|| prevV[0]->_nextV[0]->_val != num)
return false; // 第 0 层前驱后面不是 num
Node* del = prevV[0]->_nextV[0];
for (size_t i = 0; i < del->_nextV.size(); ++i)
prevV[i]->_nextV[i] = del->_nextV[i]; // 每一层都越过 del
delete del;
// 收缩 head：去掉顶部那些已经全空的层
int i = (int)_head->_nextV.size() - 1;
while (i >= 0 && _head->_nextV[i] == nullptr)
--i;
_head->_nextV.resize(i + 1);
return true;
}
// 逐层打印跳表形态
void Print()
{
int h = (int)_head->_nextV.size();
printf("----------- skiplist top=%d ----------\n", h);
for (int level = h - 1; level >= 0; --level)
{
Node* cur = _head->_nextV[level]; // 跳过哨兵
printf("L%d: ", level);
while (cur)
{
printf("%d -> ", cur->_val);
cur = cur->_nextV[level];
}
printf("null\n");
}
printf("---------------------------------\n");
}
private:
Node* _head; // 头哨兵
size_t _maxLevel = 32; // 最大层数（与 Redis 一致）
double _p = 0.25; // 升层概率（与 Redis 一致 p=1/4）
};
int main()
{
Skiplist sl;
// 插入一组
int a[] = {19, 22, 28, 33, 38, 44, 56};
for (int v : a)
{
sl.add(v);
cout << "add " << v << " -> search(" << v << ")="
<< (sl.search(v) ? "yes" : "no") << "\n";
}
sl.Print();
// 查找存在/不存在
cout << "search 33 = " << (sl.search(33) ? "yes" : "no") << "\n";
cout << "search 99 = " << (sl.search(99) ? "yes" : "no") << "\n";
// 重复插入并删除其中一个
sl.add(33);
cout << "add(33) again -> search 33 = " << (sl.search(33) ? "yes" : "no") << "\n";
cout << "erase 33 = " << (sl.erase(33) ? "success" : "fail") << "\n";
cout << "erase 33 again = " << (sl.erase(33) ? "success" : "fail") << "\n";
cout << "search 33 = " << (sl.search(33) ? "yes" : "no") << "\n";
sl.Print();
// 边界：删除不存在的、清空
cout << "erase 999 = " << (sl.erase(999) ? "success" : "fail") << "\n";
for (int v : a) sl.erase(v);
cout << "after clearing all, search 19 = "
<< (sl.search(19) ? "yes" : "no") << "\n";
sl.Print(); // head 应已缩到只剩一层甚至 0 层
sl.add(7); // 空表重插，验证 head 能被重新撑起来
sl.Print();
cout << "search 7 = " << (sl.search(7) ? "yes" : "no") << "\n";
return 0;
}这段代码编译运行后，你会看到一层层 L0/L1/L2/L3 的形态打印，以及删除、清空、再插入时 head 层数的"缩下去又撑起来"。这比死记代码更能建立对跳表的体感。
泛化与比较器：支持任意类型
上一版把 key 写死成 int，够教学但对真实工程不够。真实场景里 key 可能是字符串、结构体，甚至希望倒序存储。这就要把跳表泛化，并且把"比较大小"这件事抽象出来，交给一个比较器（comparator），而不是硬编码 <。
先给泛化版，默认用 std::less<T>（即依赖类型自己的 operator<）：
#include <iostream>
#include <vector>
#include <cstdlib> // rand / srand
#include <ctime> // time
#include <functional> // std::less / std::greater
using namespace std;
// 泛化跳表：T 为 key 类型，Cmp 为比较器（默认依赖 T 的 operator<）
template<class T, class Cmp = less<T>>
class Skiplist
{
struct Node
{
T _val; // 泛化后的值
vector<Node*> _nextV; // forward 数组
Node(const T& v, int level) : _val(v), _nextV(level, nullptr) {}
};
Node* _head;
Cmp _cmp; // 比较器实例
size_t _maxLevel = 32;
double _p = 0.25;
public:
Skiplist() : _head(new Node(T(), 1)) {}
~Skiplist() // 沿第 0 层全量链逐个释放（与 int 版相同）
{
Node* cur = _head;
while (cur)
{
Node* toDelete = cur;
cur = cur->_nextV[0];
delete toDelete;
}
}
int RandomLevel() // 随机摇层数，p=1/4，上限 maxLevel
{
size_t level = 1;
while ((double)rand() / RAND_MAX < _p && level < _maxLevel)
++level;
return (int)level;
}
// 关键点：把 int 版的 “a < b” / “a > b” 统统改写成 _cmp(a, b)
bool search(const T& target)
{
Node* cur = _head;
int level = (int)_head->_nextV.size() - 1;
while (level >= 0)
{
// next 满足 _cmp(next, target) 即 next < target：向右
if (cur->_nextV[level] && _cmp(cur->_nextV[level]->_val, target))
cur = cur->_nextV[level];
else if (cur->_nextV[level] == nullptr
|| _cmp(target, cur->_nextV[level]->_val)) // target < next 即 next > target
--level;
else
return true; // 三者皆否 ⇒ next 与 target 相等
}
return false;
}
// 返回每一层“小于 num 的最右前驱”集合
vector<Node*> FindPrevNode(const T& num)
{
Node* cur = _head;
int level = (int)_head->_nextV.size() - 1;
vector<Node*> prevV(level + 1, _head);
while (level >= 0)
{
if (cur->_nextV[level] && _cmp(cur->_nextV[level]->_val, num))
cur = cur->_nextV[level]; // next < num：向右
else if (cur->_nextV[level] == nullptr
|| !_cmp(cur->_nextV[level]->_val, num)) // !(next < num) ⇒ next ≥ num：向下停
{
prevV[level] = cur;
--level;
}
}
return prevV;
}
void add(const T& num) // 插入（允许重复）
{
vector<Node*> prevV = FindPrevNode(num);
int n = RandomLevel();
if (n > (int)_head->_nextV.size())
{
_head->_nextV.resize(n, nullptr);
prevV.resize(n, _head);
}
Node* newnode = new Node(num, n);
for (size_t i = 0; i < (size_t)n; ++i)
{
newnode->_nextV[i] = prevV[i]->_nextV[i];
prevV[i]->_nextV[i] = newnode;
}
}
bool erase(const T& num) // 删除一个 num
{
vector<Node*> prevV = FindPrevNode(num);
Node* cand = prevV[0]->_nextV[0];
// cand 为空，或 cand 与 num 不相等（用比较器判断：既不小于也不大于）
if (cand == nullptr
|| _cmp(cand->_val, num)
|| _cmp(num, cand->_val))
return false;
for (size_t i = 0; i < cand->_nextV.size(); ++i)
prevV[i]->_nextV[i] = cand->_nextV[i];
delete cand;
int i = (int)_head->_nextV.size() - 1; // 收缩 head 空顶
while (i >= 0 && _head->_nextV[i] == nullptr)
--i;
_head->_nextV.resize(i + 1);
return true;
}
void Print() // 逐层打印形态
{
int h = (int)_head->_nextV.size();
for (int level = h - 1; level >= 0; --level)
{
Node* cur = _head->_nextV[level];
cout << "L" << level << ": ";
while (cur)
{
cout << cur->_val << " -> ";
cur = cur->_nextV[level];
}
cout << "null\n";
}
}
};
int main()
{
// 传 greater 让“大”的排在前面，做一棵倒序跳表，验证比较器生效
Skiplist<int, greater<int>> sl;
sl.add(5); sl.add(1); sl.add(9); // 倒序后应排成 9 -> 5 -> 1
sl.Print();
cout << "search 1 = " << (sl.search(1) ? "yes" : "no") << "\n";
cout << "erase 5 = " << (sl.erase(5) ? "success" : "fail") << "\n";
sl.Print();
return 0;
}比较器带来两个必须交代清楚的坑：
- "严格小于"的语义必须贯穿一致：跳表要求 "能往右就走、不能往右就降" 的前提是底层严格有序。如果你传的比较器既不是
less也不是严格弱序的greater，而是给了一个不严格的（比如让比较总返回 true），跳表会乱套。所以传入的比较器必须满足反对称、传递，且能退化成"两个相等元素间既 a<b 为假、b<a 也为假"，这样才能对着任意元素判出"小于 / 大于 / 等于"三者其一。 - head 哨兵的值：泛化后 head 存储
T()（默认构造值）。它必须"小于所有真实 key"才能胜任哨兵。对int这类可用T()；对自定义类，要么保证它默认构造出来的值偏小，要么干脆在比较时对 head 节点特殊处理（不在本条展开，知道这个前提即可）。
边界与坑：写好跳表的清醒清单
写完跳表，我把最容易翻车的几个点集中列一遍——写对它们，你的跳表才算"稳"：
坑 1：随机层数不要用 rand() % r 之类带模偏差的方式。rand() 返回 [0, RAND_MAX] 的整数。用模运算切范围时，如果 r 不整除 RAND_MAX+1，落在某些区间的概率会比别的区间略大，造成模偏差（modulo bias）——虽然对跳表影响通常不致命，但"概率 p 精确可控"正是跳表正确性的基石，严谨起见应写成 (double)rand() / RAND_MAX < p（让 0~1 均匀浮点与 p 比大小），或用 C++11 的 <random>（质量更好）。上面正式代码已采用浮点方案。
坑 2：随机种子。多数实现称 srand 依赖 rand()，别忘了 srand(time(0)) 打底，否则每次运行层数完全一样（等于退化到一种固定但无规律的层数，虽不严谨但可运行）。工程上更推荐用 <random> 的 std::default_random_engine + uniform_real_distribution，继续做"有没有 > 1/4"的判定。
坑 3：head 的层数是动态的，务必用有符号变量。size() 返回无符号 size_t，直接 size() - 1 在 head 只有 0 层时会溢出成巨大的正数，然后 while 里把空指针当成真实节点解引用，直接崩。所有"层号变量"（level、i）都该用 int，并允许它们减到 -1 作为合法的“结束”信号。
坑 4：删顶层节点后的 head 收缩。详见过 delete 一节——顶层节点被删光时，head 顶层指针全空，应把 head 收缩到“仍有非空后继的最高层 + 1”，否则白白带着空顶，既浪费又易在后续操作里多走空层。
坑 5：空表 / 只有 head。构造出来的跳表只有 head，此时 search 任何值都返回 false，add 会把 head 重新撑高，erase 一个不存在的值要返回 false 而不崩。三处都要有“空表兜底”。
坑 6：比较器语义。泛化时比较器要满足严格弱序（见泛化一节），否则严格判断“小于/大于/等于”会失效。
坑 7：释放内存。树形结构都要手写析构；跳表沿第 0 层的全量链逐个 delete 即可一次释放干净，别忘了。
跳表与平衡搜索树、哈希表的对比
终于到了开头卖的关子：把它们摆到同一张桌上。
先 vs 平衡搜索树（AVL / 红黑树）：
- 相同点：都能做到遍历数据有序；增删查改的期望/最坏复杂度都在同一档次的 O(logN)（跳表是期望，平衡树是最坏）。
- 跳表的优势：
- 实现简单、逻辑直白、容易控制。平衡树要维护平衡因子/颜色、考虑单旋双旋、还得处理上提的祖先链，代码又长又易错；跳表就是"找前驱 + 随机层数 + 接线"三件套，肉眼就能调试。
- 额外空间消耗更低。平衡树每个节点三叉链（左/右/父）+ 平衡因子或颜色位，开销摆在那；跳表一个节点平均指针数 = 1/(1-p)，p=1/2 时平均 2 个指针、p=1/4 时平均仅 1.33 个指针，其余几乎不占空间。
- 遍历与区间查找（ZRANGEBYSCORE 类）在大规模下也很方便——因为有全量底层链，遍历和对“范围区间”的滑动都极其自然。
| 对比维度 | 跳表 | 平衡搜索树（AVL/红黑） | 哈希表 |
|---|---|---|---|
| 数据是否有序 | 有序 | 有序 | 无序 |
| 增删查平均复杂度 | O(logN)（期望） | O(logN)（最坏） | O(1)（平均/分摊） |
| 实现复杂度 | 低 | 高（旋转/变色） | 中（需重哈希、冲突处理） |
| 额外空间 | 平均 1.33~2 指针/节点 | 三叉链 + 平衡字段 | 表空间 + 冲突链/游标 |
| 扩容开销 | 无（节点就地变高） | 动态插入/旋转 | 有明显扩容 rebuild 损耗 |
| 最坏场景 | 期望值，随机差则单次慢 | 稳定最坏 O(logN) | 冲突极端时退化成链表/红黑树 |
再 vs 哈希表：
- 哈希表的优势：平均 O(1) 的查找比跳表快；但代价是：无序（不能有序遍历）、空间开销略大（表 + 冲突链或游标），以及扩容有性能损耗（需要 rehash 把所有元素重排，偶尔很贵）。
- 跳表的优势：遍历有序；空间略省（平均 1.33~2 指针 vs 哈希表“表 + 链”）；没有重哈希的阵痛（跳表扩“高度”是就地发生的）；面对极端冲突（如所有 key 撞进同一个桶）时，哈希表会退化成 O(N)（现代才用红黑树补底），而跳表因为只依赖随机层数、不依赖特定 key 的分布，不会有这种“被数据背刺”的最坏场景。
一句话总结三者的定位：哈希表要速度给不了顺序，平衡树最均衡但难写，跳表用“稍慢一点点的期望 O(logN)”换来了“极简实现 + 天然有序 + 低增量内存”，在部分场景里成了比平衡树更“香”的选择。
Redis ZSet 为什么爱跳表
光说理论不过瘾，举一个你天天用的真实例子：Redis 的有序集合（ZSet / sorted set）底层用的就是跳表（与哈希表配合：哈希负责 O(1) 定位 member→score，跳表负责把 member 按 score 有序地组织起来）。
为什么 Redis 的作者偏爱跳表而不是红黑树？官网 FAQ 曾解释过几个现实理由：
- 实现和维护成本低。跳表代码短、逻辑天然“纯指针拼接”，比红黑树的旋转/变色要简单得多，而正确性更容易保证——对一个运行了多年的通用组件来说，可维护性零差。
- 区间操作极其方便。Redis 大量命令要做按分数区间取元素（如
ZRANGEBYSCORE、ZRANK）。跳表持有底层全量有序链 + 多层索引，要“从某个分数开始扫一片”时，就沿链往下走到起点然后线性往后取即可；而红黑树做区间取用要维护一个额外的界或做较复杂的遍历。跳表在“升序/逆序区间遍历”上天然更顺手。 - 期望复杂度够用。Redis 对每一条命令都要求稳定可预期的低延迟，跳表最坏期望 O(logN) 足够满足；它那个“随机层数”引入的不确定性，通过固定 p=1/4、maxLevel=32 已经被约束得很稳。
所以当你看到 Redis 用跳表而 C++ 的 map/set 用红黑树时，不必惊讶：两者都在 O(logN) 支撑有序动态集合，差别在“好不好写、区间遍历顺不顺、内存省不省”这些工程权衡。理解了跳表，你不但看懂了 Redis 的源码里为啥竖着那一根根指针，也更懂得“选型”永远不是唯一解，而是权衡的艺术。
好，这一路我们把跳表从“why（为什么有序链表太慢）”、到“how（多层索引 + 随机层数）”、再到“code（search / FindPrevNode / add / erase / Print 一行行手写）”、最后链接到“工程现实（与红黑树、哈希表怎么选，Redis 为何爱它）”全部打通了。现在回看开篇那个问题——跳表是“敢在链表底盘上长出二分能力的随机化多级索引”：它用一层受控的概率分布（几何分布，期望高度恒为 1/(1-p)）换来了避开“严格比例”的全局维护灾难，用期望 O(logN) 的代价保住了增删的自由。你读完这一章，再把文末那段完整代码跑一遍、亲手打印出那几层透都是空的高层，对这棵“不用树却胜似树的表”，就再也不会只停留在背过概念的层面了。下一站无论是继续深挖跳表删除的细节，还是回头看红黑树、哈希表，脑海里有这张“概率平衡”的底子，都能让你把不同平衡方案连成一张更大的知识网。
还没有评论 — 第一条由你来留。