用python代码实现布隆过滤器

布隆过滤器是一种空间效率很高的概率型数据结构，用于判断一个元素是否在一个集合中。它利用了位数组和哈希函数的特性，通过计算元素的一些哈希值并将其对应的位设置为1，来表示该元素可能存在。由于它是概率型的，可能会存在误判（将不在集合中的元素误认为在），但不会漏掉。

以下是Python中简单实现布隆过滤器的示例：

import mmh3  # 使用mmh3库来进行哈希计算，可以替换为其他哈希函数

class BloomFilter:
    def __init__(self, size, hash_functions=4):
        self.size = size
        self.hash_functions = hash_functions
        self.bits = bytearray(size)
        self.misses = 0

    def add(self, item):
        for seed in range(self.hash_functions):
            index = mmh3.hash(item, seed) % self.size
            self.bits[index] = True
        self.misses += 1

    def contains(self, item):
        all_bits_set = True
        for seed in range(self.hash_functions):
            index = mmh3.hash(item, seed) % self.size
            if not self.bits[index]:
                all_bits_set = False
                break
        return all_bits_set and self.misses < self.size * 0.5  # 设置阈值，当误判率超过50%时，认为不存在

# 使用示例
filter = BloomFilter(100_000, hash_functions=8)
filter.add("apple")
print(filter.contains("apple"))  # 输出：True (可能是真阳性)
print(filter.contains("banana"))  # 输出：False (可能是阴性，也可能是假阴性)