python 写一个简单的布隆过滤器,并计算误判率
时间: 2024-10-14 22:18:00 浏览: 10
布隆过滤器是一种空间效率很高的概率型数据结构,用于判断一个元素是否在一个集合中。它通过多个哈希函数将元素映射到位数组的不同位置,如果所有哈希结果对应的位都是1,则认为该元素可能在集合中,但是存在误判的可能性。
下面是一个简单的Python布隆过滤器实现:
```python
import bitarray
class BloomFilter:
def __init__(self, size=1000000, hash_count=5):
self.size = size
self.hash_functions = [hashlib.sha256, hashlib.md5, lambda x: int(x.encode('hex'), 16) % size]
self.bit_array = bitarray.bitarray(size, 'uint8')
self.bit_array.setall(0)
def add(self, element):
for hash_function in self.hash_functions:
index = hash_function(element) % self.size
self.bit_array[index] = 1
def contains(self, element):
result = all(self.bit_array[hash_function(element) % self.size] == 1 for hash_function in self.hash_functions)
return result and not (self.is_full() or self.has_false_positive())
def is_full(self):
return self.bit_array.all()
def has_false_positive(self):
# 假设每个哈希函数独立导致误判,所以误判率为 p^(k), 其中 k 是哈希函数的数量,p 是位错误的概率,默认为1/size
expected_false_positives = self.size * len(self.hash_functions) / (2**self.size)
if expected_false_positives > 1:
return True # 如果预期误判超过1次,说明可能有误判
else:
return False
# 使用示例
filter = BloomFilter()
filter.add("hello")
print(filter.contains("hello")) # 输出可能会是True,因为可能存在误判
阅读全文