Python Bloom过滤器实现

Bloom过滤器概率集合。可能误判但不会错判不存在。位数组+k个哈希函数。不可删除(Counting Bloom可删除)。mmap位数组支持持久化。空间效率高。应用:缓存穿透、URL去重、垃圾邮件过滤。

import mmap, hashlib, math

class BloomFilter:
def __init__(self, n, fpr=0.01):
self.n = n
self.p = fpr
self.m = int(-n * math.log(fpr) / (math.log(2) ** 2))
self.k = int(self.m / n * math.log(2))
self.bit_array = bytearray(self.m)

def _hashes(self, item):
result = []
for i in range(self.k):
h = hashlib.md5(f"{i}:{item}".encode()).hexdigest()
result.append(int(h, 16) % self.m)
return result

def add(self, item):
for pos in self._hashes(item):
byte_idx = pos // 8
bit_idx = pos % 8
self.bit_array[byte_idx] |= (1 << bit_idx)

def __contains__(self, item):
for pos in self._hashes(item):
byte_idx = pos // 8
bit_idx = pos % 8
if not (self.bit_array[byte_idx] & (1 << bit_idx)):
return False
return True

bf = BloomFilter(10000)
bf.add("test")
print("test" in bf) # True
print("other" in bf) # 可能True(误判)或False