在昂贵查询之前
假设搜索大型数据库需要昂贵的磁盘读取。我们希望先用小型内存结构回答:“这个键有可能存在吗?”布隆(Bloom)过滤器的否定回答可以精确,肯定回答却可能误报。因此它只能作为初步检查;若需要精确判断,回答“可能存在”后仍须查询权威数据库。
定义 16.1.1
(布隆过滤器)
取整数 、。布隆过滤器是初始全为零的 位比特数组,配合值域为 的哈希函数 。插入键 时,把 指向的比特都设为一;查询 时,若全部被指向的比特均为一,回答“可能存在”,否则回答“不存在”。对从未插入的键回答“可能存在”,称为误报。
容许碰撞,也容许同一键的多个位置相同。若哈希函数固定,重复插入同一键不会再改变比特。
命题 16.1.2
(单侧正确性)
若一个键已插入,而且之后没有比特被清除,查询绝不会把它判为不存在。这是确定性结论,不需要随机哈希假设。
证明
(比特只会被设为一)
插入时,该键指向的每个比特均设为一。其后的插入只会把比特设为一,所以查询时这些比特仍全为一,回答必为“可能存在”。碰撞及重复插入也包含在论证内。这里要求插入及查询使用相同函数和数组,更新没有遗失;结论并不保证肯定回答正确。
反方向,即“肯定回答证明了存在”,并不成立。
反例模式
肯定回答不等于真正存在
令 、,插入满足 的键 。若另一个从未插入的键 亦满足 ,查询 仍会回答“可能存在”。仅凭该比特无法区分两种历史。
明确的随机模型
定义 16.1.3
(固定查询的理想哈希模型)
在选取哈希函数之前,先固定 个互异的已插入键,以及一个不在该集合内的查询键。理想哈希模型假设这 个键的 个哈希值相互独立,各自在 个位置上均匀分布。
此理想模型比“每个哈希值各自均匀”强;具体实现能否适切近似它,须按哈希方式和工作负载另行验证。此结果不自动适用于观察过滤器后自适应选择的查询。
设插入后共有 个值为一的比特。
命题 16.1.4
(占用量与误报概率)
在理想哈希模型下,
其中 是固定查询键被回答“可能存在”的概率。
证明
(占用量用线性性,查询用条件化)
共有 次独立插入位置抽取;一个指定位置从未被抽中的概率为 。把 个位置“被抽中”的示性变量相加,再用期望的线性性,即得 。给定已完成的过滤器后,不存在的查询键的 个位置仍是独立均匀抽取,因为它们与插入位置独立。每个位置以条件概率 落在值为一的比特上,所以条件误报概率为 ;对过滤器取平均便得 。公式也涵盖 :因 ,此时 ,误报概率为零。
证明透视
两个强弱不同的独立性
证明用了两次独立性,两者不可混为一谈。第一,查询位置与插入位置独立;这正是查询键必须预先固定、且与所有已插入键不同的原因。观察过滤器后才选的查询,或再次查询已插入的键,都会破坏这一点。第二,给定过滤器时, 个查询位置相互独立,于是得到乘积 。它们并非无条件独立: 大时每一个都更容易成功,所以这些事件共用随机的占用量。因此要先取 次方,再取平均。确定性的无漏报命题两者都不需要。
随机模型用于概率结论,并非上述确定性正确性所需。
精确有限公式与可靠上界
对 ,先选出恰好被占用的 个位置,再计算其中每个位置至少出现一次的插入位置序列。
命题 16.1.5
(占用量的精确有限分布)
在理想哈希模型下,设 ,并约定 。对 ,
证明
(对遗漏位置作容斥)
所有 个位置序列等概率。固定一组 个位置,先数在这组内取值的 个序列;减去漏掉某指定位置的序列,加回漏掉两个位置的序列,如此交替,便是内层容斥和。再乘 ,因每个序列的占用集合唯一。最后对 作条件化并求和。当 ,约定使 的概率为一。公式虽精确,交替项在浮点计算中可能不稳定。
概念视角组合
用满射计数占用量
长度为 、恰好占用一组指定的 个位置的地址序列,就是从 个地址到这 个位置的满射。这样的满射相当于先把 个地址分成 个非空块,再把各块分配给各位置,所以容斥和等于 ,其中 是第二类 Stirling 数。因此 。当 、 时得到 和 ,与下文的计算一致。
不必计算整个分布,也可由 和 得到可能较松的上界:
第一式用 时 ;第二式对每个实现的过滤器都成立。两者均不假设对插入随机性取平均后,查询比特事件仍独立。常见的 把随机占用量换成其平均值;在这个有限模型中它只是近似,通常不是精确概率。
例题 16.1.6
(小型过滤器的修正)
取 、,插入一键。两次位置相同的概率为 ,此时 ;否则 。因此不存在的查询键误报概率为
平均占用比例为 ,但其平方是 ,并非 。上述两个可靠上界分别为 和 ,故此处前者较好。
例题 16.1.7
(计算容斥公式)
取 、,插入一键,故 。公式给出
以及 ;这是必然的,两个位置不可能占用三格。各概率之和为一。直接计算也一样:两个位置相同的概率是 。因此
作为比较,,用平均占用量计算的近似给出 ,低于精确的 。两个可靠上界为 和 ,都高于精确值。
例题 16.1.8
(两个不同键与重复插入同一键)
令 、,插入两个固定的不同键。其位置以 概率相同,此时 ;以 概率不同,此时 。因此固定的不存在查询键有
相反,插入同一键两次会把相同位置设为一两次:,误报概率为 。模型中的 是互异插入键数,不是插入调用次数。把重复调用当作独立新哈希抽取会改变算法,得出错误计算。
常见错误
(把平均占用比例的 k 次方当作精确值)
先把随机占用量换成平均值,再取次方。由于 在 上是凸函数,Jensen 不等式给出 :在有限模型中,这个近似只会低估精确概率, 时取等号。上面的例子显示了差距: 对 , 对 。
合并、删除与实际意义
若两个过滤器使用相同的 、 和哈希函数,可逐位作 OR 合并。输出比特为一当且仅当任一输入比特为一,故结果恰好等于插入两个集合之并集所得的数组。即使集合重叠,此等式仍确定成立。不过并集的概率计算仍需检查其互异键和查询键是否符合哈希假设;不同哈希函数的过滤器不能这样解释。
常见错误
(用清除比特的方式删除键)
直接清除被删键指向的比特并不安全:其他已插入键可能共用该比特。例如 时两键都使用唯一比特,清除它会使另一键被错判为不存在。单侧正确性命题假设没有比特被清除,而删除恰好违反这个假设。
计数变体可存储重数,但安全删除需要正确的插入记录、一致的计数更新及没有溢出或更新遗失;普通比特数组本身无法重建重数。
过滤器能否节省输入输出,取决于内存、 次哈希及误报查询的成本是否适合工作负载。占用率高时大多数查询都会呈阳性。如果输入或查询者能针对所选哈希作对抗,固定查询的随机保证并不是安全保证。应分开记录哈希族、种子政策、插入数与实测负载,不把理想模型当成实测。
练习与解答
快速检查
(令 、,插入一键。在理想模型下,固定的不在集合中的查询键误报概率是多少?)
先数值为一的比特个数。
解答 · 答案
恰有一个比特为一,查询命中它的概率为 。也可用确定的 得 。
快速检查
(令 、,插入一键并查询固定的不在集合中的另一键。四个哈希位置全相同的概率是多少?它是否涵盖所有误报?)
分开 与 两种情形。
解答 · 答案
第一个位置任意,其余三个各以概率 相同,故概率为 。这只涵盖 的情形;若插入占满两个位置,任何查询都为阳性,另贡献 ,总计 。
快速检查
(两个参数和哈希均相同的过滤器分别含集合 、。说明即使 ,其 OR 仍是 的过滤器。)
说明 OR 后某位置何时为一。
解答 · 答案
OR 后某位置为一,当且仅当任一集合中有键指向它,这正是并集的插入规则。重复插入不会改变已为一的比特。
快速检查
(工程师清除离开的键所指的全部比特。举出一个漏报,并说明计数方法需要什么额外状态。)
用最小的过滤器。
解答 · 答案
时插入两个不同键,两者把同一比特设为一。为第一个键清除后,第二个键被判为不存在。计数器须保留现存贡献的数量并正确更新,包括处理重复键及溢出;普通比特没有此信息。
以上计算只涉及有限理想模型中的固定查询,并非对实际哈希实现、自适应查询或任意删除的普遍保证。