布隆过滤器

算法简介

布隆过滤器（Bloom Filter）是布隆在 1970 年提出的算法，可以用于检测一个元素是否存在于集合当中，优点是空间效率和查询效率都远超一般算法，缺点是有一定的误判率并且难以删除已经存在的元素。布隆过滤器的本质是一个很长的二进制向量和一系列的随机 hash 函数。

实现思路

判断一个元素是否存在于集合当中，一般的思路是先保存集合当中所有的元素，然后通过比较确定结果。但是随着集合中元素的增加，这种算法所消耗的空间也会越来也大，同时查询元素的速度也会越来越慢。

在布隆过滤器算法中，当一个元素被添加到集合当中时，先通过 N 个不同 hash 函数生成 N 个不同的 hash 值，然后在很长的二进制向量当中把 N 个 hash 值对应的位设置为 1。判断元素是否存在的时候，再检查这些 N 个 hash 值对应的位：如果有任何一个为 0 则表示元素肯定不存在，如果全部都为 1 则表示元素很大可能存在。

hash1(value) -> 1
hash2(value) -> 4
hash3(value) -> 7


       value
    /    |    \
   /     |     \
 hash1 hash2 hash3
   |     |     |
   v     v     v
+-+-+-+-+-+-+-+-+-+-+
|0|1|0|0|1|0|0|1|0|0|
+-+-+-+-+-+-+-+-+-+-+
 0 1 2 3 4 5 6 7 8 9

优点/缺点

相比于其它算法，布隆过滤器在空间和时间方面都有巨大的优势。另外，由于 hash 函数之间没有互相关系，因此方便程序并行计算。布隆过滤器本身不会存储数据，因此也适用于数据安全敏感的场景。

但是，布隆过滤器存在误判的概率，当存储的元素越来越多，误判的概率就越来越大。并且，一般情况下，布隆过滤不能删除已经存在的元素。

参考资料

• 数学之美系列二十一 － 布隆过滤器（Bloom Filter）