算法技术手册（原书第2 版）

搜索算法

｜

111

搜索算法

5.4 布隆过滤器

无论是使用链表还是开放定址技术，

散列搜索

都需要将集合

C

中的所有元素存储到散列

表

H

中，而且随着更多的元素加入散列表中，如果不增加存储空间，那么势必会需要花

费更多的时间来寻找元素。话虽如此，本章所有算法的性能也都和存储空间的大小息息

相关，我们希望能够寻找到一个平衡点——在从集合中查找元素时，既能够减少查找的

次数，也能够减少额外需要的空间。

布隆过滤器

提供了另外一种思路，它使用一个

位数组

B

，来确保只需要

常数时间

就能够

把集合

C

中的元素插入集合

B

中，或者检查一个元素是否没有被添加到

B

中。而且令人

惊讶的是，这个常数时间和

B

中已有的元素数量无关。当然，世事并非完美，

布隆过滤

器

在检查一个元素是否在集合

B

中时，会

误报

目标元素存在，然而实际并不存在。相反，

布隆过滤器

却可以很准确地汇报目标元素并不存在

B

中。

布隆过滤器算法小结

最好情况、平均情况和最坏情况：

O

(

k

)

create(m)

return bit array of m bits

❶

end

add (bits,value)

foreach hashFunction hf

❷

setbit = 1 << hf(value)

❸

bits |= setbit

❹

end

search (bits,value)

foreach hashFunction hf

checkbit = 1 << hf(value)

if checkbit | bits = 0 then

❺