有趣的算法 - 布隆过滤器
引言
现在假设一个需求：设计一个 url 黑名单系统，需求是 1 亿个 url 黑名单，每个 url 平均长度 30 字节，判断当前的 url 是否在黑名单中。
我们最先想到的可能时 HashSet，如果少量的 url，HashSet 有着 O(1) 的查询效率是首选的方案。但是面对 1 亿个 url，单单存储 value 就需要 2861MB 内存，显然不可取。而如果放到硬盘上进行数据库查询，面对近 3GB 的数据库，每次匹配都要查询的话，IO 操作本身就是瓶颈。
所以这时候引入了布隆过滤器。
原理
初始化
首先初始化一个长度为 m 的 bit 数组，每一位初始化为 0。
插入
确定 k 个独立的 hash 函数，每个 hash 可以将输入的 url 生成并映射为 1 个 [0,m-1] 的值，每个值作为数组下标，将该位置的值置为 1。
查询
同插入部分，将输入的 url 用插入时确定的 k 个 hash 函数生成 k 个数组下标，逐个检测每个下标对应的位置的值，如果有一个不为 1 则确定不在集合中，如果全部为 1，则有可能在集合中。
误判
误判来自两方面：
- 由于 hash 函数是有碰撞几率的，虽然多个 hash 会大大降低这种几率，但是仍然有几率两个完全不同的 url 通过 hash 后得到的 k 个值完全相同。
- 多次插入以后不同的插入组合可能与某个未插入值经过 hash 后的值相同，我们极端化思考：当数组被 1 填充满后，任何输入都会被判断为存在。
所以布隆过滤器判断不存在的一定不存在，判断存在的可能有误判率。根据误判我们可以做一些提高准确性的工作：当判断存在时进行一次数据库查询，对误判建立白名单系统。当然，如果本身可接受极低的误判率，那通过尽可能降低误判率后忽略误判。
公式
设过滤器数组的长度为 m，插入的值的个数为 n，hash 函数的个数为 k，误报率为ε。
给定插入个数和误报率可得过滤器的长度为：$m=-{\frac {n\ln \varepsilon }{(\ln 2)^{2}}}$
给定 m 和 n 时最优 hash 函数个数为：$k={\frac {m}{n}}\ln 2$，给定误报率时 hash 函数个数为：$k=-\log _{2}\varepsilon $
给定 m 和 n 时误报率为：$\varepsilon \leq \left(1-e^{-{\frac {k(n+0.5)}{m-1}}}\right)^{k}$，当 m 比较大时，可以近似为：$\varepsilon \approx \left(1-e^{-{\frac {kn}{m}}}\right)^{k}$
图示示例
- 设置一个 [0,14] 长度为 15 的数组，使用两个 hash 函数：
Fnv和Murmur：
- 插入 1，fnv(1)=7，murmur(1)=2：
- 插入 3，fnv(3)=9，murmur(3)=14：
- 查询 2，fnv(2)=8，murmur(2)=9，
Murmur命中但Fnv未命中，所以肯定不存在 2：
- 查询 14，fnv(14)=2，murmur(14)=14，两个 hash 函数均命中，所以可能存在 14：
注：此处使用两个 hash 函数得出 hash 值后取余映射回了 [0,14] 区间，并非直接所得 hash 值。
进阶
注： 仅供扩展了解，本人并未真正去推导
根据原理可知，该算法的时间复杂度为 O(k)，也就是性能瓶颈为 k 个独立的 hash 函数。当误报率小于 0.01%时，需要 13 个 hash 函数，这在频繁查询中也是一个很大的性能压力。 《Bloom Filters in Probabilistic Verification》 这篇论文很好的解决了这个问题，将 k 个不同的 hash 函数转换成了 2 个 hash 函数的简单运算，其公式为：$g_{i}(x)=h_{1}(x)+ih_{2}(x)+i^{2}\bmod m,i\in \left(0,k \right)$
根据公式我们可以得到第 i 个 hash 函数的值而不需要真的准备 k 个 hash 函数去计算。这样只需要 2 个 hash 函数即可完成布隆过滤器。另一篇哈佛的论文： 《Less Hashing, Same Performance: Building a Better Bloom Filter》 对该方法有效性进行了证明。
应用
我们只需要利用布隆过滤器真阴性性质就已经可以在 IO 查询前加入一层过滤系统来大大降低 IO 操作，如果可以容忍或者通过其他方式避免低概率的假阳性，那么可以用到更加广泛的方面。
业界常用的案例是垃圾邮件的过滤系统，爬虫的 url 去重系统。
实际上各种 k-v 储存都可以并且已经应用布隆过滤器来减少 IO 操作，比如 Leveldb，Hbase。