概率数据结构

1. 首页
2. 概率数据结构

在精确集合成员判定（HashSet / 红黑树 / 哈希表）的成本随数据规模线性膨胀之后，工程界早已接受一个现实：**大多数"是否存在"的查询，并不需要 100% 精确**。当你可以容忍一个极小且可量化的假阳性（false positive）概率，却坚决不允许假阴性（false negative）时，有一类被称为"概率数据结构"的工具能把内存占用从 O(n·w) 压到 O(n·c)（c 为常数比特…

系统拆解 HyperLogLog 的第一性原理：从 Flajolet-Martin 草图、LogLog 分桶到 HLL 用调和均值替代算术均值抑制离群桶，把标准误差压到 1.04/√m；推导哈希分桶、ρ(rank) 寄存器、原始估计量 E=α·m²/Σ2^{-M[j]} 与 α_m 校正常数、误差表；解析小基数 Linear Counting 混合与 HLL++ 的 empirical bias correction、稀疏表示（varint 编码）与 64 位修正；论证逐桶 max 的可合并性如何支撑分布式/流式基数聚合；给出与 Bloom/Count-Min 的分工对照表、可合并的生产级 Python 实现（dense/sparse 切换、序列化、merge）与 12 项生产陷阱清单（哈希一致性、p 不可变、合并前不可先平均、误差带展示等）。与本站《布隆过滤器》(16214)、《Count-Min Sketch》(16270) 共同构成概率数据结构工程三部曲。

在流式系统与大规模遥测场景中，"精确计数"往往意味着不可接受的内存与维保成本：一个高基数的网络五元组流、一个全天候的搜索词流、一个全球分布的用户行为流，精确维护每个键的计数器需要 O(基数) 的内存，而基数本身随业务线性膨胀。当内存成为硬约束时，我们必须接受"以可控的估计误差换取次线性空间"的 trade-off——这就是**计数概要（counting sketch）**家族登场的地方。其中 **…

系统拆解布谷鸟哈希的第一性原理：每个键只有两个候选桶（双哈希），查询最坏 O(1) 且与负载率无关；推导插入时"踢走占用者（evict/kick）"的驱逐重定位算法、其终止性与失败概率，以及临界负载率 α*≈0.49（k=2）的由来；解析 Stash 旁路数组把溢出概率压到 O(1/√N) 的工程技巧、rehash 扩容换种子打破置换环的方法。展开 d-left hashing、分桶布谷鸟（b=4 推到负载率 0.99+）、计数布谷鸟、并发布谷鸟（多核锁粒度/tombstone 退化）等变体，并给出 Cuckoo Filter——可删、比 Bloom 省 1.5~2 倍空间的近似成员查询替身。附带可插拔双哈希、带 Stash 与自动扩容的生产级 Python 实现（插入/查询/删除/重建），与链地址/线性探测/布隆的分工对照表，以及 12 项生产陷阱清单（哈希相关性、MAX_LOOP、Stash 增长、扩容换种子、并发 tombstone、分桶 b 过大等）。与本站《布隆过滤器》(16214)、《Count-Min Sketch》(16270)、《HyperLogLog》(16312) 共同构成"概率与高性能数据结构工程"系列，补齐确定性 O(1) 查询 + 可删除 + 高负载率维度。

跳表（Skip List）是 1989 年 William Pugh 在论文《Skip Lists: A Probabilistic Alternative to Balanced Trees》里提出的一种**概率性平衡的有序数据结构**。它要解决的，是平衡二叉搜索树（AVL、红黑树、B 树）在工程里一个长期被忽视的痛点：**为了维持"平衡"，它们不得不在每次插入删除时做复杂的旋转（rotatio…

近似成员查询（Approximate Membership Query，AMQ）结构是后端系统的"第一道闸门"：缓存击穿防护、磁盘/SSD 索引跳查、流式去重、爬虫 URL 判重、垃圾邮件指纹、向量检索前置过滤，几乎都离不开它。提到 AMQ，绝大多数工程师第一反应是 **Bloom 过滤器**——它把 n 个元素的成员信息压缩进 m 个比特的位数组，用 k 个独立哈希定位。Bloom 足够好，但它…