随机化与近似结构

跳表

这一章讲什么

前面每一章的结构都是确定的：给定输入，形状唯一。这一章的四个不是 —— 它们各自放弃一点确定性，换来规模上的可行：

结构	放弃了什么	换来了什么
跳表	结构确定（层高随机）	免掉旋转，代码短一个数量级
布隆过滤器	答案精确（有误判）	空间降到几分之一
一致性哈希	分布绝对均匀	扩容时只迁移少量数据
限流器	计数精确	O(1) 空间做速率控制

⭐ 它们的共同点是代价可以量化：不是「差不多够用」，而是「误判率恰好是这个公式，实测对得上」。这一章每一篇都会把理论值和实测值并排放。

⚠️ 和随机算法那篇不是一回事：那篇讲怎么正确地产生随机（洗牌、水塘抽样），这一章讲怎么用随机性设计结构。

跳表：从有序链表开始

有序链表查找是 O(n)，因为只能一个个走。二分查找需要随机访问，链表给不了。

⭐ 跳表的想法：给一部分节点加一条「跳得更远」的指针。

第 3 层  1 -----------------------------> 9
第 2 层  1 --------> 5 ----------------> 9
第 1 层  1 -> 3 -> 5 -> 6 -> 7 -> 9

找 7：从最高层出发，1 → 9 太远（9 > 7）就下一层，1 → 5 可以走，再从 5 出发 5 → 9 太远又下一层，5 → 6 → 7。跳过了 3。

📌 每一层都是下一层的「快车道」，规则只有两条：往右走到下一个会超过目标为止，然后下一层。

🚨 关键设计：层高由抛硬币决定

如果每隔一个节点升一层（严格的 2 的幂结构），查找确实是 O(log n) —— 但插入一个节点就要重排后面所有节点的层数，退化成 O(n)。 这正是平衡树用旋转解决、而代码变复杂的那个问题。

⭐ 跳表的答案是：别维护，掷骰子。

const P = 0.25, MAX_LEVEL = 16;

function randomLevel() {
  let level = 1;
  while (Math.random() < P && level < MAX_LEVEL) level++;
  return level;
}

每个节点独立决定自己有几层，谁也不用管别人。插入不需要重排，删除也不需要。

⚠️ 听起来很不靠谱，但它的分布是可以精确算出来的：恰好 k 层的概率是 (1-p) · p^(k-1)。10 万个节点、p=0.25， 换 21 个随机种子各跑一次（取奇数个，中位数才没有歧义）：

       理论        21 个种子的中位数     最小 ~ 最大
1 层   75.00%          75.00%        74.76 ~ 75.33%
2 层   18.75%          18.73%        18.44 ~ 18.92%
3 层    4.69%           4.68%         4.54 ~  4.86%
4 层    1.17%           1.18%         1.13 ~  1.24%
5 层    0.29%           0.29%         0.26 ~  0.32%
6 层    0.07%           0.07%         0.06 ~  0.09%

⭐ 平均层高：理论 1/(1-p) = 1.333，21 个种子的中位数 1.334（1.328~1.338）。 也就是说每个节点平均只有 1.33 个 next 指针 —— 这是跳表省空间的来源，对照红黑树每个节点要存左右子、父指针和颜色。

🚨 为什么报区间而不报一个数：上面的 randomLevel 用的是 Math.random()， 它不能播种。也就是说这一篇里任何一个「实测值」，换台机器、换一次运行都不一样，读者永远复现不出你写的那个小数。想让实测可复现，量的时候把 Math.random 换成可播种的生成器（mulberry32 之类），生产代码再换回来。 📌 判据：报单个随机实测值等于报了个无法核对的数字。要么报区间，要么写出种子。

完整实现

class SkipList {
  constructor() {
    // 哨兵头节点，值取 -Infinity，省掉「插到最前面」的特判
    this.head = { v: -Infinity, next: new Array(MAX_LEVEL).fill(null) };
    this.level = 1;               // 当前实际用到的最高层
  }

  // ⭐ 所有操作的公共部分：记下每一层「最后一个小于 v 的节点」
  _find(v) {
    const update = new Array(MAX_LEVEL).fill(this.head);
    let cur = this.head;
    for (let i = this.level - 1; i >= 0; i--) {      // 🚨 从高层往低层
      while (cur.next[i] && cur.next[i].v < v) cur = cur.next[i];
      update[i] = cur;
    }
    return { update, node: cur.next[0] };            // node 是候选目标
  }

  search(v) {
    const { node } = this._find(v);
    return !!node && node.v === v;
  }

  add(v) {
    const { update } = this._find(v);
    const lv = randomLevel();
    // 新节点比当前最高层还高时，多出来的那几层从 head 开始
    if (lv > this.level) {
      for (let i = this.level; i < lv; i++) update[i] = this.head;
      this.level = lv;
    }
    const node = { v, next: new Array(lv).fill(null) };
    for (let i = 0; i < lv; i++) {
      node.next[i] = update[i].next[i];
      update[i].next[i] = node;
    }
  }

  erase(v) {
    const { update, node } = this._find(v);
    if (!node || node.v !== v) return false;
    for (let i = 0; i < this.level; i++) {
      // 🚨 只断开真正指向它的那些层 —— 节点不一定有 this.level 那么高
      if (update[i].next[i] === node) update[i].next[i] = node.next[i];
    }
    while (this.level > 1 && !this.head.next[this.level - 1]) this.level--;
    return true;
  }

  // 走第 0 层，拿到全部值（范围查询就是从这里开始的）
  toArray() {
    const out = [];
    for (let cur = this.head.next[0]; cur; cur = cur.next[0]) out.push(cur.v);
    return out;
  }
}

⭐ 三个操作共用 _find，区别只在拿到 update 之后做什么。 这是跳表最舒服的地方：没有旋转、没有变色、没有分裂合并， add 和 erase 各自不到十行。

📌 与排序数组对拍 300 轮 × 300 次随机操作（插入/删除/查找按 5:3:2 混合，值域 0~59 故意让重复值和删不存在的值都出现），外加每轮结束后 全值域逐值扫一遍 —— 合计 9 万次操作，0 处不一致。

🚨 `erase` 里那个 `if` 不能省

for (let i = 0; i < this.level; i++) {
  if (update[i].next[i] === node) update[i].next[i] = node.next[i];
}

⚠️ 要删的节点可能只有 2 层，而 this.level 是 5 —— 第 3、4、5 层的 update[i].next[i] 指向的是别的节点。不加这个判断就会把无关节点从高层链上摘掉，表现是查找偶尔漏掉某些值，而链表底层（第 0 层）看起来完全正常。

实测（去掉那个 if，同一套 9 万次随机混合操作）：29 处答案错误。原版 0 处 —— 所以确实是这个 if 的功劳，不是对拍框架在误报。

🚨 但失败路径比「摘掉无关节点」长四环

「摘掉无关节点」本身还不会给出错误答案 —— 高层只是快车道，把它截短只会让查找变慢，不会变错。真正出错要走完这四步（下面的计数来自其中一条具体的操作序列）：

① 把高层指针写成 undefined（截掉无关节点）           61 次
② head 的最高层被截空，this.level 跟着缩小            10 次
   （原版跑完 this.level = 5，坏版只剩 2）
③ 于是出现「节点自身层数 > this.level」的删除          2 次
   erase 的循环只走到 this.level，高层根本没清理
④ 留下指向已删节点的悬垂指针                          2 个   ← 与 ③ 一一对应

⭐ 第 ④ 步才是致命的，而它有两种发作方式（300 轮里分别出现）：

模式 A：新节点根本没进第 0 层（29 / 300 轮，共丢 20 个值） add 也要先 _find。若 cur 落在悬垂节点上，update[0] 就是个已删节点，新节点被接到那条陈旧的链上 —— 第 0 层里根本找不到它。

模式 B：第 0 层完好，但查找走过头（3 / 300 轮）

第 0 层序列 = 3,4,5,5,5,6,…    （92 个值，与参考数组逐位相同）
第 1 层链   = 1, 4, 19, 21     其中两个是【已删除】的节点

search(5)  第1层 → 1 → 4        停在那个【已删除的 4】上
           这个 4 的 next[0] 还是它被删时的旧快照，指向 6
           → 落点 cur.next[0] = 6，三个真实的 5 被整段跳过 → 返回 false

🚨 所以「底层完全正常、只有高层查找出错」只是模式 B，而它是少数。 多数情况下第 0 层自己也已经丢了值 —— 也就是说 拿 toArray() 和参考数组对拍，反而是最容易抓到这个 bug 的检查 （29/300 轮直接报警），比逐个 search 更灵。 📌 判据：别假定「底层链表是唯一事实来源」 —— 一旦高层出现悬垂指针，写路径会顺着它把底层也污染掉。

⚠️ 它还挑测试。我第一版对拍用「顺序插入 0~199，再删掉所有偶数」，跑出来 0 处不一致 —— 顺序插入让每次 update[i] 恰好都真的指向目标节点， if 拦不拦都一样。换成随机交错的 add/erase 才炸出来。 👉 判据：测「漏删/多删」这类 bug，操作必须交错随机，不能先插一批再删一批。

📌 顺带一个能一眼看出结构烂掉的指标：跑完之后看 this.level。 n=2 万、删掉一半、11 个种子，原版 this.level 中位数是 8，坏版塌到 1 —— 已经退化成单链表（右移步数从 17.8 步涨到 5980 步）。 先看结构指标，再看答案对不对。

查找到底多快

n = 10 万，随机查 1000 次。🚨 先说清「一步」是什么 —— 两种数法差一半：

                                实测中位数(11 个种子)   同口径的理论值
只数右移（沿某一层往右挪一格）        22.3  (21.3~24.1)     (1/p−1)·log_{1/p}(n) = 24.9
右移 + 每次下层各算一步              32.0  (29.5~34.1)     (1/p)·log_{1/p}(n)   = 33.2

单链表                             50000（理论均值 n/2）
log₂(n)                            16.6

⭐ 两种口径下实测都比理论值略好（22.3 < 24.9，32.0 < 33.2），而且都和 log₂(n) = 16.6 是同一个量级。

⚠️ 别拿一个口径的实测去比另一个口径的理论。 (1/p)·log_{1/p}(n) = 33 这个常被引用的式子含下层开销，拿「只数右移」的 22.3 去比它，会得出「实测比理论好 33%」的错觉 —— 同口径下只好 10%。 📌 这个坑在下一节会直接改变结论。

⭐ p 该取多少：一张实测的权衡表

p 越大，节点层数越高、跳得越远，但指针也越多。n = 5 万，11 个种子取中位数：

p        指针/节点   只数右移   右移+下层   ← 两种口径，结论不同
                    实测/理论   实测/理论
0.5        2.00     14.8/15.6   29.9/31.2
0.25       1.33     20.5/23.4   29.6/31.2      ← Redis 的选择
0.125      1.14     30.8/36.4   36.0/41.6

🚨 看「右移+下层」那一列：p 从 0.5 降到 0.25，总步数几乎没变。 不是巧合，是个恒等式 —— 总代价 (1/p)·log_{1/p}(n) = ln(n) / (p·ln(1/p))，而：

0.5   × ln(2) = 0.346574
0.25  × ln(4) = 0.346574     ← 逐位相同
0.125 × ln(8) = 0.259930     ← 掉下来了
最大值在 p = 1/e ≈ 0.368

⭐ 所以逐档的边际交换是这样的（理论值）：

0.5   → 0.25     指针 -33%    总步数  ±0%     ← 纯赚，不花钱
0.25  → 0.125    指针 -14%    总步数 +33%     ← 从这里开始付账
0.125 → 0.0625   指针  -7%    总步数 +50%

⭐ 0.25 是最后一顿免费的午餐 —— 比 0.5 省三分之一指针，查找一步不多走。再往下才是真正的取舍。这才是 Redis 和多数实现选它的理由。

🚨 只数右移就得不出这个结论：那个口径下 0.5→0.25 看着「慢了 37%」，像是在拿时间换空间。因为它把「下层次数」漏掉了 —— 而那一项恰好随 p 减小而减少 （p=0.5 要下 15.6 层，p=0.25 只下 7.8 层），刚好补偿掉多出来的右移。 📌 判据：度量一个权衡时，先确认量具没有系统性漏掉其中一边的收益。

为什么 Redis 用跳表而不是红黑树

Redis 作者本人给过三条理由，每条都能对上上面的数据：

实现和调试简单得多。上面整个类 46 行代码（含注释与空行 56 行），没有旋转与变色。红黑树的删除要分多种情况、每种还有左右镜像，写对了也难改。
范围查询天然高效。找到起点后沿第 0 层顺着走就行（就是上面的 toArray()）—— 而红黑树要做中序遍历，代码和常数都更重。有序集合的 ZRANGE 正是范围查询。
内存可调。改一个 p 就能在空间与时间之间移动（见上表），平衡树没有这个旋钮。⭐ 而且 0.5→0.25 这一档是免费的。

⚠️ 反过来，跳表的最坏情况是 O(n) —— 如果所有节点都掷出 1 层。但那个概率是 0.75^n，n=100 时约 3×10⁻¹³。 📌 这是随机化结构的通性：不保证最坏情况，但坏情况的概率小到可以不考虑，而且与输入无关 —— 攻击者构造不出坏数据，因为随机来自你自己。

面试会怎么问

手写跳表（力扣 1206「设计跳表」，困难，非会员题）—— 会考，但真正卡人的是 erase 那个 if 和「层高不用维护」这个观念转变，不是代码量。
跳表 vs 红黑树 / B+ 树 —— 答上面那三条，再补一句「跳表最坏 O(n) 但概率可忽略，且不受输入构造影响」。
为什么 p = 0.25 —— 能说出「空间与时间的权衡，0.25 附近是拐点」就够。 ⭐ 想答得更好就说透一层：0.5→0.25 的总查找代价完全不变 （因为 0.5·ln2 = 0.25·ln4），指针却少三分之一，所以 0.25 是「白拿」的最后一档 —— 这句话背不出来，只有推过或量过才说得出。

下一步

跳表放弃的是结构确定性，答案仍然精确。下一篇的布隆过滤器更进一步 —— 它连答案本身都不保证准确，换来的是空间降到几分之一。

练习

勾选记录做过哪些，0 / 5 道。进度只存在这台设备的浏览器里；同一道题在别篇勾过，这里也会显示已做。

1206. 设计跳表困难⭐ 本篇主讲。真正卡人的是 erase 里那个 if，不是代码量
1670. 设计前中后队列中等多指针维护同一序列，和跳表「多层指针」是同一种思路
1472. 设计浏览器历史记录中等双向结构 + 位置指针；先想清楚状态再写
981. 基于时间的键值存储中等有序存储 + 二分查找，跳表在工程里正是干这个的
1146. 快照数组中等⚠️ 别真的复制数组：每个下标存「版本 → 值」再二分

⚖️ 这里只给题号、官方标题和链接，不复述题面 —— 平台的题面文字有版权。「这题考什么」写的是它对应本篇的哪个点，那部分是本站自己的内容。

跳表