illegalCreed

中文

English

中文

English

Appearance

跳表与布隆过滤器：概率数据结构 ​

基于通用算法套路 · 核于 2026-07

速查 ​

  • 跳表（Skip List）：在有序链表之上叠加多层概率索引，把单层 O(n) 查找压到期望 O(log n)——平衡树的概率替代。
  • 跳表的概率层级：每个节点以概率 p（通常 1/2）「晋升」到上一层，期望一半在第 1 层、四分之一在第 2 层……总层级高度期望 O(log n)。
  • 跳表查找：从最高层起，向右走（值更小就走）、走不动就下一层——像走楼梯下探，每层期望跳过一半节点，共 O(log n) 层。
  • 跳表插入/删除：先查找定位，再在每一层做链表节点增删——期望 O(log n)；无旋转、无颜色翻转，实现远比红黑树简单。
  • 跳表 vs 红黑树：复杂度同为 O(log n)，但跳表实现简单、并发友好（局部锁）、天然支持范围查询；代价是空间约 1.33 倍指针开销 + 概率保证（非确定）。
  • 跳表的工程地位：Redis ZSET（zskiplist）、LevelDB/RocksDB MemTable、Redisson 分布式锁——选它而非红黑树，主要因「简单 + 并发 + 范围查询」。
  • 布隆过滤器（Bloom Filter）：m 位位数组 + k 个哈希函数；插入置 k 位为 1，查询检查 k 位是否全 1——全 1「可能在」，有 0「一定不在」。
  • 布隆的核心性质：可能误判（false positive），绝不漏判（no false negative）——「判不在」必准，「判在」可能错；误判率随填充率上升而升高。
  • 布隆不支持删除：多位共享 bit，删一个会误删别的——要删除用 Counting Bloom Filter（每位改成计数器，删除时减 1）。
  • 布隆的典型应用：缓存穿透防护（数据库前挡一层）、爬虫 URL 去重、垃圾/恶意 URL 黑名单、HBase/LevelDB 读放大优化（读前过滤避免无谓磁盘 IO）。
  • 布隆参数选择：给定元素数 n 和误判率 p，最优位数组 m ≈ -n·ln p / (ln2)²，最优哈希个数 k = (m/n)·ln2——典型「每元素 ~9.6 bit + 7 哈希」达 1% 误判率。
  • 共同思想：用概率换工程收益——跳表用概率层级避开平衡树旋转，布隆用概率判重省 1~2 个数量级空间。

一、跳表：多层索引链表 ​

有序链表的致命短板是查找 O(n)——即使有序也不能二分（不能随机访问）。跳表的思路是给有序链表加「快车道」：在底层（Level 0，完整有序链表）之上叠加多层稀疏索引，越往上节点越少。查找时从最高层起，一路向右、走不动就下一层，像在多层高架桥上开车下匝道，快速逼近目标。

Level 2:  HEAD ──────────────► 30 ───────────────────────► NIL
Level 1:  HEAD ──────► 10 ────► 30 ──────► 50 ───────────► NIL
Level 0:  HEAD ► 5 ► 10 ► 20 ► 30 ► 40 ► 50 ► 60 ► 70 ► 80 ► NIL

查找 40：从 Level 2 的 HEAD 向右到 30（30<40），再向右遇到 NIL 下到 Level 1；Level 1 从 30 向右到 50（50>40 走不动），下到 Level 0；Level 0 从 30 向右到 40 命中。每层期望跳过约一半节点，总层数期望 O(log n)，所以查找 O(log n)。

二、概率层级：为什么期望 O(log n) ​

跳表的「多层索引」不是手动维护平衡（否则就和红黑树一样复杂了），而是用概率决定每个节点的层高：

  • 新节点插入时，抛硬币决定晋升：以概率 p（通常 1/2）晋升到上一层，直到「失败」或达到最大层。
  • 期望：第 0 层有 n 个节点，第 1 层约 n/2，第 2 层约 n/4……总层级数期望 log₂ n。
  • 每个节点平均层数 = 1/(1-p)，p=1/2 时为 2——即每个节点平均占 2 层的指针空间，加上跨层指针约 1.33 倍链表开销。

这是跳表相对红黑树的核心优势：用随机性代替了复杂的平衡操作。红黑树插入要旋转、变色、处理叔叔节点；跳表插入只是「查找到位置 + 每层插链表节点 + 随机层高」，实现代码量是红黑树的三分之一。代价是期望 O(log n) 而非最坏 O(log n)（极低概率层级退化），但工程上这个概率小到可以忽略。

三、跳表的操作：查找 / 插入 / 删除 ​

js
// 跳表骨架（p=0.5）
const MAXL = 16, P = 0.5;
class SkipNode { constructor(k, v, lv) { this.k = k; this.v = v;
  this.next = new Array(lv).fill(null); } }

class SkipList {
  constructor() { this.head = new SkipNode(-Infinity, null, MAXL);
    this.level = 1; }
  randLevel() { let lv = 1;           // 概率晋升
    while (Math.random() < P && lv < MAXL) lv++; return lv; }
  find(k) { let cur = this.head;
    for (let i = this.level - 1; i >= 0; i--) { // 从高层下探
      while (cur.next[i] && cur.next[i].k < k) cur = cur.next[i]; }
    cur = cur.next[0]; return cur && cur.k === k ? cur.v : null; }
  insert(k, v) {
    const update = new Array(MAXL); let cur = this.head;
    for (let i = this.level - 1; i >= 0; i--) {
      while (cur.next[i] && cur.next[i].k < k) cur = cur.next[i];
      update[i] = cur; }                              // 记录每层前驱
    const lv = this.randLevel();
    if (lv > this.level) { for (let i = this.level; i < lv; i++)
      update[i] = this.head; this.level = lv; }
    const node = new SkipNode(k, v, lv);
    for (let i = 0; i < lv; i++) {                    // 每层插节点
      node.next[i] = update[i].next[i]; update[i].next[i] = node; } }
}
  • 查找：从最高层起向右走到 cur.next[i].k >= k 前停下，下到下一层；底层（Level 0）即为精确定位，O(log n)。
  • 插入：查找时记录每层的前驱 update[i]，随机生成层高 lv，在每层做链表插入，O(log n)。
  • 删除：同理记录每层前驱，摘除目标节点并更新 update[i].next，O(log n)。

四、跳表的工程地位：为什么 Redis 选跳表而不是红黑树 ​

Redis 作者 antirez 明确解释过 ZSET 选用跳表而非红黑树（或 B+ 树）的原因：

  1. 内存占用可调：通过改 p 参数可压低平均层数（p=1/4 时平均 1.33 层），比平衡树指针更省。
  2. 范围查询友好：底层是有序链表，ZRANGE/ZRANGEBYSCORE 定位起点后沿链表顺序扫即可，O(log n + m)；红黑树范围扫要中序遍历，缓存差。
  3. 实现简单、易调试：无旋转、无颜色翻转，插入删除就是链表操作，代码可读性高，bug 少。
  4. 并发友好：链表是局部结构，并发时只需锁相邻节点（细粒度），不像树旋转要锁大块。

Redis ZSET 实际是跳表 + 哈希表的组合：哈希表（dict）按 member 查 score（O(1)），跳表（zskiplist）按 score 排序做范围查询（O(log n)）——和 LRU「哈希 + 链表」是同一种「拼装」思想。LevelDB/RocksDB 的 MemTable、Redisson 的分布式锁也用跳表。

五、布隆过滤器：位数组 + 多哈希 ​

海量数据精确判重（哈希表）太费空间。布隆过滤器用 m 位位数组 + k 个哈希函数把每个元素压到约 10 bit，是空间最省的概率判重结构。

工作机制：

  • 插入：对元素 x 算 h₁(x), h₂(x), ..., h_k(x) 共 k 个哈希，把位数组对应位置全置 1。
  • 查询：算 k 个哈希，检查对应位——全为 1「可能在」，有任何一位为 0「一定不在」。

为什么「可能误判但不漏判」：

  • 不漏判：x 真在集合里时，插入时它的 k 位必全置 1，查询时绝不会看到 0，故必判「在」（真阳性）。
  • 可能误判：x 不在集合里时，它的 k 位可能恰好被其他元素的哈希都置成 1（位重叠），于是被误判「在」（假阳性）；但只要有一位是 0，就铁定不在。
  • 误判率随填充率上升：位数组越满（1 越多），随机查一位是 1 的概率越高，误判率越高。

六、布隆不支持删除与 Counting Bloom Filter ​

标准布隆过滤器不支持删除：因为多个元素共享同一位（A 和 B 的某个哈希位都是第 5 位），删 A 把第 5 位置 0 会误伤 B（B 明明还在，却因第 5 位变 0 被判「不在」——这违反了「不漏判」）。

要支持删除，用 Counting Bloom Filter：把位数组每一位从 1 bit 扩展成几 bit 的计数器。插入时对应位置 +1，删除时 -1，查询时判 >0。这样删 A（第 5 位 5→4）不会误伤 B。代价是空间变大（计数器比 1 位大几倍）。

七、布隆过滤器的应用与参数选择 ​

典型应用（共性：海量数据 + 容忍误判 + 要省空间）：

  • 缓存穿透防护：恶意请求大量不存在的 key，每次都穿透到数据库。在数据库前挡一层布隆——布隆判「不在」直接返回，判「在」再查库（偶发误判查不到也无害，等于多查一次空库）。
  • 爬虫 URL 去重：百亿 URL 精确去重哈希表扛不住，布隆每个 URL 约 10 bit 即可。
  • 黑名单/垃圾过滤：恶意邮箱、恶意 URL 黑名单——误判（把好人当坏人）可接受「二次确认」。
  • HBase/LevelDB 读放大优化：读 SSTable 前先用布隆过滤判断 key 是否在这个文件，避免无谓磁盘 IO。

参数选择（给定元素数 n、目标误判率 p）：

  • 最优位数组大小：m = -n · ln p / (ln 2)²（bit）。
  • 最优哈希函数个数：k = (m / n) · ln 2。
  • 典型配置：n=1 亿、p=1% → m ≈ 114 MB（每元素约 9.6 bit）、k≈7。

交互演示 ​

下一步 ​

至此三种工程实用结构讲完——LRU（哈希+链表）、跳表（多层索引+概率）、布隆（多哈希+位数组+接受误判）都是「用一个结构补另一个短板」的工程拼装。完整 API、复杂度表、代码模板、易错点见参考。