布隆过滤器：说没有就真没有，说有只是可能有

缓存穿透那阵子，恶意请求用不存在的ID狂刷接口，每次都回源打数据库。加了个布隆过滤器做前置判断，不存在的key直接拦下，数据库QPS立刻回落。这个结构的误判特性值得每个做缓存的人理解一遍。

结构与原理

一个m位的位数组加k个哈希函数。插入元素时，k个哈希各算出一个位置，置1。查询时同样算k个位置，全为1才「可能存在」，任一为0就「一定不存在」：

import hashlib

class BloomFilter:
    def __init__(self, m_bits, k):
        self.m = m_bits
        self.k = k
        self.bits = bytearray((m_bits + 7) // 8)

    def _positions(self, item):
        out = []
        seed = hashlib.sha256(str(item).encode()).digest()
        for i in range(self.k):
            h = int.from_bytes(seed[i*2:i*2+2], 'big')
            out.append(h % self.m)
        return out

    def add(self, item):
        for p in self._positions(item):
            self.bits[p // 8] |= 1 << (p % 8)

    def might_contain(self, item):
        return all(self.bits[p // 8] & (1 << (p % 8))
                   for p in self._positions(item))

bf = BloomFilter(m_bits=10000, k=4)
for i in range(1000):
    bf.add(f'user:{i}')
print(bf.might_contain('user:500'))   # True
print(bf.might_contain('user:99999')) # False 或 False阳性

误判来自哈希碰撞：不同元素可能把同一批位置置了1。误判率近似(1-e^(-kn/m))^k，n为已插入元素数。经验公式：每个元素约10比特、k=7时，误判率约1%。1亿元级ID也就120MB左右，比全量HashSet便宜两个数量级。

不能删，怎么更新

标准布隆不能删除（一个位可能被多个元素共享，清0会误伤别人）。计数布隆把位换成计数器支持删但空间翻几倍； cuckoo filter支持删除且空间效率相当；业务上更常见的做法是定期全量重建：离线用最新ID集合生成新过滤器，原子替换。

使用纪律

• 「可能存在」的结果只能走二次确认（查缓存、查库），绝不能当权威
• 容量要按预估规模留余量，塞超了误判率飙升
• 参数用现成计算器定m和k，不要拍脑袋

落地后我们的链路变成：布隆判无直接返回，判有再走缓存和库。穿透流量被挡在第一层，误判的那一小部分多一次查询也无伤大雅。Redis的BF模块、Guava的BloomFilter都是成熟轮子，理解原理再用，参数调优心里有底。