紧凑的过滤器,不是精确集合
定义 6.1.1
(布隆过滤器、假阳性与假阴性)
布隆(Bloom)过滤器有 个初始为零的位,以及 个稳定哈希函数 ,把键值映到索引 。插入键值时把所有指定位置设为一;查询时只要有一个指定位置为零,就回答确定不存在,否则回答可能存在。哈希输出可以重复。过滤器不保存键值,不能枚举它们,也不能证实正面回答一定正确。假阳性是对未插入的键值回答“可能存在”;假阴性是对已插入的键值回答“确定不存在”。
定理 6.1.2
(已插入键值没有假阴性)
在哈希函数稳定、过滤器起初为空且位不被清除的情况下,每个已插入键值在其后的每次查询中都得到“可能存在”。
证明
(位只会被设为一)
设 已被插入。插入当刻, 个位 都成为一。其后的操作只有插入(只会把位设为一)和查询(不改变任何东西)。因为函数稳定,之后对 的查询读取同样的 个位置,发现它们全是一,所以绝不会回答“确定不存在”。
未插入键值仍可能发现所需位全被其他键值设为一,这就是假阳性。若需要精确成员判定,应在正面回答后查证精确的后端存储。
跟踪与不安全删除
例题 6.1.3
(两次插入、一个假阳性及一个确定不存在)
取 ,为四个不同键值指定如下哈希输出。这是例子的指定输出,不代表某个具体哈希实现。
| 键值 | ||
|---|---|---|
| a | 1 | 5 |
| b | 2 | 5 |
| c | 1 | 2 |
| d | 0 | 5 |
只插入 a 和 b,设为一的位是 。查询 c 回答可能存在,虽然 c 没被插入;查询 d 因位 为零而回答确定不存在。出现假阳性不要求 c 的哈希对与某个已插入键值完全相同。
反例模式
清除共用位会破坏保证
假设尝试删除 a,清除位 和 。键值 b 仍在目标集合中,却需要位 ,所以下次查询会错误地回答确定不存在。普通位数组没有记录哪些键值共用一个位。计数变体只有在其自身的计数器、溢出及合法删除规则下才能支持删除;本过滤器没有建立那些规则。
常见错误
(把正面回答当成成员的证明)
在上面的跟踪中,查询 c 回答可能存在,但 c 从未被插入:位 和 是 a 和 b 设的。只有“确定不存在”才是对已插入集合的确切陈述。正面回答须对照存储的键值作精确检查,才算确定。
概率计算的假设
确定的位位置列表本身没有内在概率。要建立概率模型,先固定已插入键值及一个未插入查询,并使它们独立于随机选取的哈希。假设这些不同键值所用的所有哈希输出都在 个索引上独立且均匀,包括不同函数的输出。这个理想化模型比只说每个哈希各自均匀更强。
定理 6.1.4
(均匀模型下的假阳性概率)
在此模型下,插入 个不同键值后,令 为值一位的随机数目。对未插入的查询键值,假阳性概率 满足
证明
(以已完成的位数组为条件)
给定已完成的位数组,未插入查询的 个输出独立且均匀,因为它们独立于决定该数组的 个插入输出。每个输出落在值一位的概率为 ,所以 个全部如此的概率为 。对数组取期望,便得第一个等式。
至于第二个等式:固定位保持为零,恰当全部 个插入输出都不等于其索引,概率为 。所以该位为一的概率是 ,对 个位求和并用期望线性性,得 。当 ,数组全为零,,。
证明透视
独立性用在哪里
查询输出与插入输出的独立性只用一次,就是把条件概率写成 时;没有它,查询可能与过滤器内容相关,因子 便不正确。 个查询输出之间的独立性再用一次,才能取 次方。 的期望在求零位的概率时用到插入输出的独立性,但对各位只用期望线性性,不需要不同位之间独立。两个等式回答不同的问题:第一个给出精确概率,第二个只给出平均占用率。
把平均值代入 次方得到常用近似,通常不等于次方的精确期望。模型及任何近似都须按实现与工作负载检查。
常见错误
(在次方内以平均占用数代替随机占用数)
令 、,插入一个固定键值。其两个独立均匀输出相同的概率为 ,得到 ;否则 。对独立的未插入查询,
这里 ,其平方却是 ,不是 。占用数是随机的,所以不能直接用平均值的次方代替次方的平均值。
例题 6.1.5
(m = 8、k = 2、n = 2 时,以平均值估计与精确值的比较)
共有 个插入输出。固定位为零的概率是 ,所以位为一的概率是 ,以平均值作的估计为 。要求精确值,设查询输出为 。若 (概率 ),两者都落在值一位的概率为 。若 (概率 ),两个位都为一的概率是 ,这由排除任一位保持为零的情况得出。因此
估计值 与精确值 不同,正如上面 的情形所示。对 同一公式给出 ,因为没有位被设为一。
习题与解答
快速检查
(重复插入。在哈希稳定时,把同一键值插入两次会怎样?)
第二次插入设定哪些位?
解答 · 答案
第二次再把相同位设为一,数组不变。
快速检查
(负面查询。在例子中,为何 d 确定不存在?)
d 需要哪个位,而它没有被设定?
解答 · 答案
它需要的位 是零,而任何已插入键值都会把所需位设为一。
快速检查
(小模型。在 的模型中, 是多少?)
两个插入输出何时不同?
解答 · 答案
,因为四个等可能有序输出对中有两个的两项不同。
快速检查
(精确存储。若不能接受错误的正面回答,布隆过滤器能单独代替集合吗?)
正面回答能保证什么?
解答 · 答案
不能。正面回答可能错误,需要精确查证或另一种结构。