Bloom Filter（布隆过滤器）

Bloom Filter（布隆过滤器）

是由 Bloom 再1970年提出的一种多哈希函数映射的快速查找算法。是一种空间效率很高的随机数据结构，可以看作是对 bit-map 的扩展。

原理是：

当一个元素被加入集合时，通过 K 个 Hash 函数将这个元素映射为一个位阵列（Bit Array） 中的 K 个点，把他们置为 1**。检索时，我们只要看看这些点是不是都是1就大概知道集合中有没有它了：

• 如果这些点有任何一个0，则被检索元素一定不在；
• 如果都是1，则被检索元素很可能在。

通常应用在一些需要快速判断某个元素是否属于集合，但是并不严格要求100%正确的场合。通过极少的错误换取了存储空间的极大节省。

算法如下：

创建一个 m 位BitSet，现将所有位初始化为0，然后选择 K 各不同的哈希函数。第 i 个哈希函数对字符串 str 哈希的结果记为 h(i, str)，且 h(i, str) 的范围是0到 m-1。

优点：

空间和时间都有巨大的优势。存储、插入和查询时间都是常数。

缺点：

• 误算率；
• 不能从布隆过滤器中删除元素，因为查找都不准确，因此删除也就是问题。

Bloom filter