布隆过滤器原理
判断"这个 URL 是否已经爬过""这个用户 ID 是不是黑名单""这个商品是否存在"，如果每次都查数据库太慢，把全部数据放进内存 Set 又太占空间。布隆过滤器（Bloom Filter）用一个极小的位数组解决这类海量数据的存在性判断，代价是允许极低概率的误判。
它解决什么问题
假设要爬 1 亿个网页，每抓一个都要先判断是否重复：
| 方案 | 1 亿条数据占用 | 判断速度 | 结论 |
|---|---|---|---|
| 直接查数据库 | 不占应用内存 | 慢（每次一次 IO） | 扛不住高频判断 |
| 内存 HashSet | 数 GB | 快 | 内存吃紧 |
| 布隆过滤器 | 约 120 MB | 快 | 内存与速度兼得 |
布隆过滤器的核心特性是：说"不存在"，就一定不存在；说"存在"，可能不存在。这个单向的准确保证，恰好适合做前置过滤。
核心结构：位数组 + 多个哈希
两个组成部分：
- 长度为 m 的位数组，每个位置只存 0 或 1；
- k 个相互独立的哈希函数，各自把元素映射到
[0, m)。
位数组 m = 18，哈希函数 k = 3
插入 "a"：h1=1, h2=5, h3=11
下标 0 1 2 3 4 5 6 7 8 9 10 11 12 ...
bit 0 1 0 0 0 1 0 0 0 0 0 1 0
插入 "b"：h1=2, h2=5, h3=15（第 5 位已被 "a" 置位）
下标 0 1 2 3 4 5 6 7 8 9 10 11 12 ... 15
bit 0 1 1 0 0 1 0 0 0 0 0 1 0 ... 1
插入与查询的流程：
add(x): # 插入：把 k 个位置全部置 1
for i in 0..k-1: bits[h_i(x)] = 1
mightContain(x): # 查询：任何一位为 0 就说明不存在
for i in 0..k-1:
if bits[h_i(x)] == 0: return false
return true # 可能存在，有误判概率
用 Go 表达查询的核心逻辑（片段，需放入工程）：插入只需把判断改成置位 b.bits[o/64] |= 1 << (o % 64)。
// 需 import "hash/fnv"
type Bloom struct {
bits []uint64
m, k uint64 // m 位数组长度，k 哈希个数
}
// 双哈希 h(i) = (a + i*c) % m：用两个 64 位哈希组合出 k 个位置
func (b *Bloom) hashes(data []byte) []uint64 {
h1, h2 := fnv.New64a(), fnv.New64()
h1.Write(data)
h2.Write(data)
a, c := h1.Sum64(), h2.Sum64()
offs := make([]uint64, 0, b.k)
for i := uint64(0); i < b.k; i++ {
offs = append(offs, (a+i*c)%b.m)
}
return offs
}
func (b *Bloom) MightContain(data []byte) bool {
for _, o := range b.hashes(data) {
if b.bits[o/64]&(1<<(o%64)) == 0 {
return false // 该位为 0，必定不存在
}
}
return true // 全为 1，可能存在
}
元素越多，位数组越"满"，误判率越高。
误判率与容量估算
误判率由位数组长度 m、元素个数 n、哈希个数 k 共同决定，近似关系为：
最优哈希个数 k ≈ (m / n) × ln2 ≈ 0.693 × (m / n)
误判率 p ≈ (1 - e^(-kn/m))^k，取最优 k 时 p ≈ 0.6185^(m/n)
工程上只需记住：要达到某个误判率，每个元素需要多少 bit。
| 目标误判率 p | 每元素位数 m/n | 哈希个数 k | 1 亿元素占用 |
|---|---|---|---|
| 10% | 4.8 | 3 | 约 60 MB |
| 1% | 9.6 | 7 | 约 120 MB |
| 0.1% | 14.4 | 10 | 约 180 MB |
| 0.01% | 19.2 | 13 | 约 240 MB |
需求：1 亿个 URL 去重，可接受 1% 误判率
查表：m/n = 9.6 bit → 位数组 = 1e8 × 9.6 bit = 9.6e8 bit ≈ 120 MB
哈希个数 k = 0.693 × 9.6 ≈ 6.65，取 7
容量必须按预计最大元素数预留。按 100 万规划却装了 500 万，位数组接近饱和，误判率会从 1% 飙到 20% 以上，过滤器形同虚设。
为什么不支持删除
位数组的每一位被多个元素共享，删除时清零会误伤其他元素：
插入 "a" 置位 1、5、11
插入 "b" 置位 2、5、15
删除 "a" 清零 1、5、11 → 第 5 位本是 "b" 需要的，被误清零
再查 "b" 得到"不存在" → 产生假阴性，不可接受
因此标准布隆过滤器只支持"插入 + 查询"。需要删除能力时可选：计数布隆过滤器（每位用计数器替代 bit，内存放大数倍）、布谷鸟过滤器（本身支持删除）、时间分桶（过期后整体丢弃）。
典型应用
| 场景 | 用法 | 收益 |
|---|---|---|
| 缓存穿透防护 | 查缓存前先过布隆，判定不存在直接返回空 | 拦住打到数据库的无效请求 |
| URL / 内容去重 | 爬虫入库前判断是否已抓取 | 省下大量存储与比对开销 |
| 黑名单校验 | 用户 ID、IP、手机号前置判断 | 高频判断无需查库 |
| 用户名是否被占用 | 注册前快速提示"已存在" | 减少一次数据库查询 |
注意：缓存穿透场景里，布隆保存的是数据库中存在的全部 key。判定"存在"时仍要回查缓存与数据库，只有判定"不存在"才能直接拒绝。
常见误区
- 当精确存储用：布隆只能回答"可能存在"，写操作仍须落库校验；
- 容量规划不足：按当前数据量配置，业务增长后误判率失控；
- 以为能删元素：标准实现不支持，需换计数布隆或布谷鸟过滤器；
- 用于必须精确的场景：如扣库存前的存在性判断，误判会造成真实业务错误。
小结：布隆过滤器用"位数组 + k 个哈希"把海量数据的空间开销压到每元素几个 bit，代价是存在假阳性（说存在可能不存在）、绝无假阴性（说不存在一定不存在）。使用时按最大元素数规划容量与哈希个数，记住它不支持删除，只能做前置过滤，不能当精确数据源。