布隆过滤器

算法简介

布隆过滤器(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 函数之间没有互相关系,因此方便程序并行计算。布隆过滤器本身不会存储数据,因此也适用于数据安全敏感的场景。

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

参考资料

最后更新于