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

搜索算法

｜

113

搜索算法

self.bits = 0

self.size = size

if hashFunctions is None:

self.k = 1

self.hashFunctions = [lambda e, size: hash(e) % size]

else:

self.k = len(hashFunctions)

self.hashFunctions = hashFunctions

def add(self, value):

"""

将元素插入

布隆过滤器中

"""

for hf in self.hashFunctions:

self.bits |= 1 << hf(value, self.size)

def __contains__(self, value):

"""

决定一个元素是否存在。它可能会误报一个不存在的元素存在

但是

,

它绝对不错误报一个存在的元素不存在

"""

for hf in self.hashFunctions:

if self.bits & 1 << hf(value, self.size) == 0:

return False

#

可能存在

return True

上述实现假定已经有

k

个散列函数，其中每个散列函数都接受待插入的值和位数组的大

小作为参数。每加入一个值后，位数组中的

k