概率型数据结构总览

我曾经把“概率型数据结构总览”学成了一组互不相干的名词和代码。具体表现是：我以前默认数据结构必须给出绝对正确的答案，第一次接触概率型结构时，很难接受“允许误判”也能成为工程优势。后来我尝试只保留一个问题：它到底在减少哪一种重复工作？顺着这个问题，整块知识才稳定下来。

有些系统不需要保存完整答案，只需要以极小空间快速排除大多数情况。概率型数据结构通过允许受控误差，换取数量级更低的内存或更高吞吐。

“可能”不是“不可靠”

关键在于误差是否单向、概率是否可计算、业务是否允许二次确认。以布隆过滤器为例：

• 返回“不存在”时，可以确定不存在。
• 返回“可能存在”时，仍需查询真实数据源。
• 允许假阳性，不允许假阴性（前提是没有不正确删除和实现缺陷）。

因此它适合挡住肯定不存在的请求，而不是代替数据库给出最终业务结论。

图：根据成员判断、频率估计、基数估计和删除需求选择概率结构

常见概率型结构

选择时先从问题出发：成员判断、频率估计还是去重计数？再根据数据规模、可接受误差和更新模型计算参数，而不是使用随手复制的默认值。

这些结构分别保留了什么信息

Bloom Filter 只保留若干哈希位，无法枚举元素。Count-Min Sketch 为多个哈希行维护计数，查询取各行最小值，因此碰撞只会让估计偏大。HyperLogLog 观察哈希值前导零长度，用概率分布估算不同元素数量。Cuckoo Filter 保存短指纹并允许在候选桶之间搬移，更适合需要删除的成员判断。

它们共同放弃了原始明细，因此不能从结构中恢复输入。如果业务以后可能需要审计、回放或精确列表，必须另存权威数据。

参数不是固定魔法值

任何概率结构都需要至少三个输入：预计数据量、目标误差和内存预算。数据量若超过设计值，误差会快速恶化；哈希质量差也会破坏理论分布。

参数评审应回答：

• 预计元素数是峰值、日增量还是存量？
• 错误会多查一次数据库，还是造成用户可见决策？
• 是否需要删除、过期和跨版本迁移？
• 是否要求跨语言产生完全一致的哈希结果？
• 结构丢失后能否从权威数据重建，耗时多久？

以成员判断为例，假设系统预计写入 n 个元素，允许假阳性率为 p，布隆过滤器所需位数和哈希函数数量可以近似计算为：

m = -n × ln(p) / (ln(2)²)
k = (m / n) × ln(2)

其中 m 是位数组长度，k 是哈希次数。公式不是为了考试，而是帮助工程决策：容量翻倍但内存不变时，误判率不会保持不变；把误判率从 1% 压到 0.01% 也一定要付出更多内存和计算。

Count-Min Sketch 同样需要参数设计。宽度主要影响误差上界，深度主要影响超过误差上界的概率。HyperLogLog 则通过寄存器数量平衡内存与标准误差。不同结构的参数含义不同，不能把一套“经验值”横向复制。

误差预算也是系统设计

假阳性率不是越低越好。更低误差意味着更多位和更多哈希计算。应该根据后端查询成本、请求量和允许浪费的比例确定。例如过滤器每天多放过几百次无效查询可能完全可接受，没必要为了理论极低误差消耗大量内存。

还要监控实际填充率和估计误差。数据规模超过设计容量后，假阳性率会显著上升；这时需要重建、分片或滚动版本，而不是继续相信初始参数。

生命周期与版本化

概率结构往往需要定期重建。可以给结构附带版本、容量、哈希算法、种子、创建时间和源数据水位。读取方只有在元数据匹配时才加载，避免升级后用新算法查询旧位图。

滚动重建可以采用双版本：新数据同时写入旧版和新版，后台从权威数据回填新版，追平水位后切换读取，再下线旧版。这样避免停机清空，也减少漏写导致的假阴性。

分布式场景要明确一致性。多个实例各自维护本地 Bloom 会得到不同答案；共享 Redis 位图便于统一，但引入网络和中心依赖；按分片键拆分可以降低单体容量，但路由规则必须稳定。

从业务问题到结构选择

可以使用四步法做选择：

1. 写清楚查询问题，例如“这个订单号是否肯定没出现过”。
2. 写清楚错误方向，假阳性和假阴性分别会造成什么后果。
3. 估算峰值规模、写入速率、保留周期和可接受误差。
4. 再决定结构、参数、权威数据源和降级路径。

例如接口防重若把一个真实新请求误判为重复，会直接拒绝合法业务，这类场景不能只靠普通 Bloom Filter 做最终判定；它最多作为第一层过滤，仍需精确幂等表确认。缓存穿透场景中的假阳性只会多查一次数据库，通常更容易接受。

哈希函数与序列化契约

概率结构依赖哈希分布。直接使用对象进程内的 hashCode() 可能在跨语言、跨版本或重启后不稳定。生产实现应固定：

• 输入字节编码，例如统一 UTF-8。
• 字段拼接规则和空值表示。
• 哈希算法、种子及从一个哈希派生多个位置的方法。
• 位序、字节序、序列化格式和版本号。

常见的“双重哈希”方法用两个基础哈希生成多个位置：index_i = (h1 + i × h2) mod m，避免真正计算 k 套昂贵哈希。取模前要处理负数与溢出，测试时还要验证不同语言实现对同一输入得到完全相同的位置。

常见失效方式

• 实际元素数远超预计容量，假阳性率失控。
• 删除普通 Bloom 中的位，误伤共享该位的其他元素，产生假阴性。
• 数据库先写成功、过滤器后写失败，却没有补偿或重建机制。
• 发布新版本时更换哈希算法，旧位图仍被继续读取。
• 把“可能存在”直接当作“确定存在”，省略权威数据确认。
• 只压测平均吞吐，不测热点键、批量重建和故障恢复。

这些问题说明概率结构不是一个孤立容器，而是一段带容量、版本、一致性和观测要求的数据链路。

适用边界

概率结构适合做前置筛选、分析估算和大规模流式统计，不适合资金、权限、库存等要求精确最终判断的核心状态。即使使用，也必须保留权威数据源和降级路径。

选择与验收清单

• 成员判断且不删除：Bloom Filter。
• 成员判断且需要删除：Counting Bloom 或 Cuckoo Filter。
• 高频项与近似频率：Count-Min Sketch。
• 超大规模 UV：HyperLogLog。
• 精确结果：普通集合、数据库或精确聚合。

验收时用独立数据集实测误差，不只相信公式；验证序列化后兼容、重建耗时、容量超限告警和权威数据源降级。

建议至少记录写入元素估计数、位图填充率、查询量、过滤量、回源量、实测假阳性量、重建耗时和当前版本。压测数据不能与建库数据完全相同，还应包含未见过的随机值与分布倾斜值，否则测不出真实误差。

最后可以用三个问题自测：为什么概率结构不能代替权威库？容量超限后为什么要重建而不是继续追加？业务不能接受假阴性时，更新顺序和故障补偿应该如何设计？