Bloom filter是一种概率型数据结构，用于判断某个元素是否属于一个集合。它可以快速地检索元素，而不需要存储实际的元素本身，因此具有很小的存储空间。
基本概念：
布隆过滤器使用一个位数组（bitmap）来表示集合，初始时所有位都被置为0。
通过多个哈希函数将元素映射到位数组的不同位置上，将对应位置的位设置为1。
当要查询一个元素时，将该元素通过相同的哈希函数映射到位数组的相应位置，如果所有对应位置的位都为1，则表示该元素可能存在于集合中，否则一定不存在。
概率分析：
由于布隆过滤器使用多个哈希函数进行映射，因此可能会存在哈希冲突的情况。假设布隆过滤器中有n个元素，位数组的长度为m，使用k个哈希函数，则每个元素映射到位数组的位置的概率为1/m，因此一个位为0的位置的概率为(1-1/m)^kn。当查询一个元素时，如果所有对应位置的位都为1，则表示该元素可能存在于集合中。但是有可能存在哈希冲突，导致其他元素也将对应位置的位置为1，因此存在一定的误判率。
源码分析：
以下是一个简单的布隆过滤器的示例代码：
from bitarray import bitarrayimport mmh3class BloomFilter:def __init__(self, size, num_hashes):self.size = sizeself.num_hashes = num_hashesself.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.sizeself.bit_array[index] = 1def contains(self, item):for i in range(self.num_hashes):index = mmh3.hash(item, i) % self.sizeif self.bit_array[index] == 0:return Falsereturn True# 使用示例bf = BloomFilter(1000000, 5)bf.add("apple")print(bf.contains("apple")) # 输出Trueprint(bf.contains("banana")) # 输出False这段代码使用了第三方库bitarray和mmh3来实现布隆过滤器。bitarray用于表示位数组，mmh3用于计算哈希值。在初始化布隆过滤器时，需要指定位数组的长度和哈希函数的个数。add方法用于将元素添加到布隆过滤器中，contains方法用于判断一个元素是否存在于布隆过滤器中。在查询元素时，需要使用相同的哈希函数进行计算，并检查对应位置的位是否为1。
