bloom filter浅析(基本概念,概率分析,源码分析)

Bloom filter是一种概率型数据结构，用于判断某个元素是否属于一个集合。它可以快速地检索元素，而不需要存储实际的元素本身，因此具有很小的存储空间。

基本概念：

1. 布隆过滤器使用一个位数组（bitmap）来表示集合，初始时所有位都被置为0。

2. 通过多个哈希函数将元素映射到位数组的不同位置上，将对应位置的位设置为1。

3. 当要查询一个元素时，将该元素通过相同的哈希函数映射到位数组的相应位置，如果所有对应位置的位都为1，则表示该元素可能存在于集合中，否则一定不存在。

概率分析：

由于布隆过滤器使用多个哈希函数进行映射，因此可能会存在哈希冲突的情况。假设布隆过滤器中有n个元素，位数组的长度为m，使用k个哈希函数，则每个元素映射到位数组的位置的概率为1/m，因此一个位为0的位置的概率为(1-1/m)^kn。当查询一个元素时，如果所有对应位置的位都为1，则表示该元素可能存在于集合中。但是有可能存在哈希冲突，导致其他元素也将对应位置的位置为1，因此存在一定的误判率。

源码分析：

以下是一个简单的布隆过滤器的示例代码：

from bitarray import bitarray import mmh3 class BloomFilter: def __init__(self, size, num_hashes): self.size = size self.num_hashes = num_hashes self.bit_array = bitarray(size) self.bit_array.setall(0) def add(self, item): for i in range(self.num_hashes): index = mmh3.hash(item, i) % self.size self.bit_array[index] = 1 def contains(self, item): for i in range(self.num_hashes): index = mmh3.hash(item, i) % self.size if self.bit_array[index] == 0: return False return True # 使用示例 bf = BloomFilter(1000000, 5) bf.add("apple") print(bf.contains("apple"))  # 输出True print(bf.contains("banana")) # 输出False 

这段代码使用了第三方库bitarray和mmh3来实现布隆过滤器。bitarray用于表示位数组，mmh3用于计算哈希值。在初始化布隆过滤器时，需要指定位数组的长度和哈希函数的个数。add方法用于将元素添加到布隆过滤器中，contains方法用于判断一个元素是否存在于布隆过滤器中。在查询元素时，需要使用相同的哈希函数进行计算，并检查对应位置的位是否为1。