精确集合保留每个键，精确计数器保留每个键的频率。只能单遍处理输入、又不愿为所有键保存完整记录时，可以接受受条件约束的误差，但必须先说明查询什么，以及哪一种错误不会发生。

Bloom Filter回答某个键是否可能出现过；Count-Min Sketch估计某个键累计出现的次数。前者不是精确集合，后者不是直接列举高频键的完整方案。本篇沿04篇的哈希碰撞模型与32篇的失败概率分析，分别核对它们的保证。

Bloom的确定性保证从哪里来

维护m个位和k个固定哈希函数。插入键x时，把h_1(x)到h_k(x)对应的位全部置1；查询时若有任一位为0，就回答不存在，否则回答可能存在。

只要插入与查询使用同一组哈希函数、位数组没有丢失或被清零，每个已插入键查询到的位置就都为1。因此无假阴性是操作不变量，不依赖哈希分布足够随机。对一个未插入键，这些位置可能已经被其他键置1，产生假阳性。

普通精确哈希表并不因为哈希冲突就返回假阳性：它还会比较完整键，冲突影响查找成本。Bloom没有保存足够的完整键来消除这种歧义，不能把两种数据结构的结果保证混用。

标准Bloom不能通过清除某个键对应的位来删除它，因为其他键可能共享这些位。若两个键映射到同一组位置，删除其中一个时清零会让另一个出现假阴性。计数型变体另有计数器溢出和合法删除前提，不属于这里的位数组实现。

常见误报公式为什么不总是等式

先采用一个明确的理想模型：对每个不同插入键及固定未插入查询键，各k个哈希位置彼此独立、均匀落在m个位中，允许位置重复。n表示不同插入键的数量，重复插入同一个键不会增加新的独立投球。

记插入后置1位数为随机变量S。条件于完整位数组，查询的k个独立位置全部命中1的概率是(S/m)^k，所以精确假阳性概率为

p=E[(S/m)k].p=\mathbb E[(S/m)^k].

虽然E[S]/m=1−(1−1/m)^{kn}，一般也不能把k次幂移到期望外面。对k≥1，幂函数的凸性反而说明

p≥[1−(1−1/m)kn]k.p\ge\left[1-(1-1/m)^{kn}\right]^k.

例如m=2、n=1、k=2。两个插入位置相同的概率为1/2，此时S=1；不同的概率为1/2，此时S=2。因此精确p=(1/2)(1/2)²+(1/2)·1=5/8，常见替代式却得到9/16。

规划参数时常用(1−e^{-kn/m})^k近似，并由此得到k约为(m/n)ln2。它是理想模型下的近似设计关系，还要选择整数k；不能把它当作任意哈希实现、任意输入和自适应查询的精确保证。

Count-Min保存多个碰撞计数

维护d行、每行w个非负计数器，每行有一个哈希函数h_i。收到更新(x,Δ)时，要求Δ为非负整数，把每行第h_i(x)个计数器增加Δ。查询x时取d个对应计数器的最小值。

设真实频率为f_x，总质量N=Σ_x f_x。每行对应桶都包含x自身的f_x，其他键只增加非负碰撞噪声，所以估计值始终不小于f_x。这个不低估保证也来自确定性结构，不是概率事件。

初始化需要O(dw)个计数器；每次更新和查询需要O(d)次哈希及计数操作。若每个计数器需要存到N，理论计数器空间是O(dw log(N+2))位，而Python列表中的整数对象还有解释器开销，不能直接把对象数当成实际占用位数。

教学接口仅接受非负增量。某些允许负更新、但所有最终频率仍非负的模型可以继续证明查询界；不能笼统说任何删除都必然错误。若允许一般有符号频率，则碰撞键可能贡献负噪声，例如同桶的f_x=1、f_y=−2会得到−1，已经低估x。

用一行的期望，再用多行放大

固定一个与哈希选择无关的非负频率向量f，以及固定查询键x。第i行噪声为Z_i=Σ_{y≠x}f_y·[h_i(y)=h_i(x)]。若不同键每行碰撞概率至多1/w，则E[Z_i]≤N/w；这里用期望线性性，不要求同一行所有碰撞事件完全独立。

取w=⌈e/ε⌉，0<ε<1，便有E[Z_i]≤εN/e。N>0时由Markov不等式，一行噪声超过εN的概率至多1/e。N=0时所有计数器都为0，结论直接成立，不需要除以0。

若各行哈希独立选择，d=⌈ln(1/δ)⌉，0<δ<1，则所有行同时超出误差阈值的概率至多e^{-d}≤δ。查询取最小值，于是

fx≤f^x≤fx+εNf_x\le\widehat f_x\le f_x+\varepsilon N

中的左侧确定成立，右侧至少以1−δ概率成立。δ是对内部随机哈希选择而言的失败概率，不是运行一次后输出值附带的可信度标签，也不是相对误差εf_x。

若要同时回答Q个预先固定的查询，可用联合界把失败概率控制在Qδ。观察摘要结果后再自适应选择查询或更新，不在这条固定输入证明的范围内；不能继续原封不动地声称每次都有原来的δ保证。

教学哈希与理想模型分开

教学实现复用04篇的仿射哈希约定，固定素数p=65537，键必须是0≤x<p的整数。每行选择非零a及任意b，计算h(x)=((ax+b) mod p) mod w，要求1≤w≤p。这里复用的是同一个哈希族及其输入域，不能先把任意字符串压缩到域里，再忽略预先发生的碰撞。

若a、b在规定范围内理想均匀抽取，两个不同键在域中得到均匀的不同输出。固定第一个输出后，与它模w同桶的其他输出至多⌊(p−1)/w⌋个，所以碰撞概率至多1/w；各行独立选择参数就满足上面的Count-Min证明需求。模w后的输出不必严格成对独立，证明实际用的是碰撞上界。

这不足以推出Bloom所有键与查询位置完全独立。因此代码中的Bloom只核对无假阴性与这些种子的误报观测，不把5/8示例或常见规划公式当成这个仿射实现的精确误报率。random.Random也只是可复跑伪随机配置，数学保证针对理想参数抽取。

stream_sketch.py提供Bloom.insert/contains与CountMin.add/query，共享AffineHashes，均不提供删除。Bloom用bytearray为每个逻辑位保存一个字节，实际数组是m字节而非m位；另有k组参数。Count-Min保存dw个Python整数和d组参数。Bloom每次操作O(k)，初始化O(m+k)，计数摘要初始化O(dw+d)；键和参数限制在固定域内。

1
python3 examples/advanced-algorithms/check_stream_sketch.py

本轮以精确Counter同时提供成员集合与频率参照，输入51个不同键、总质量155。种子0–4下，Bloom参数m=128、k=3，对各100个未插入查询观察到假阳性42、45、47、39、20个；Count-Min参数w=16、d=4，最大高估依次为11、10、15、10、10。所有已插入键均未漏报，全部查询未低估。

另一个独立的理想位置枚举遍历m=2、n=1、k=2的16种等可能配置，其中10种误报，精确得到5/8；它不调用仿射哈希。空流、重复插入、域边界、零更新及12个非法输入拒绝也已检查。清位删除和有符号碰撞反例用独立小模型展示。结果保存于writing-plans/advanced-algorithms/evidence/stream-sketch-results.json；观测误报与高估不构成概率上界的实验性证明。

频率点查询不会自动枚举可能的高频键。Count-Min只保存桶计数，不保留所有键的身份；若要输出重频项列表，还需要候选维护或另外的摘要算法。把“可以估计已知键的频率”写成“可以恢复全部高频键”，扩大了接口承诺。

练习

  1. 在m=2、n=1、k=2的理想模型里枚举插入与查询位置，独立算出5/8。说明重复插入同一个键为什么不能把n改成2。
  2. 一个键真实频率为1，流总质量N=100000，ε=0.01。Count-Min保证允许多大的加性误差？说明为什么这不能当作该键的1%相对误差保证。

参考资料