布隆过滤器（Bloom Filter）
一句话说明
布隆过滤器不是拿来“精确存数据”的，而是拿来用很小空间快速回答“它一定不存在，还是可能存在”。
先理解它到底解决什么问题
如果你只是想判断一个元素是否出现过，最直接的方法当然是哈希表。
但当数据量非常大时，哈希表会很吃内存。
布隆过滤器的思路是：
- 不保存元素本身
- 只保存若干个哈希位置是否被打过标记
所以它能大幅省空间，但换来的代价是：
- 说“不存在”时一定正确
- 说“存在”时只是可能存在
这是它最重要的结论
返回 false => 一定不存在
返回 true => 可能存在这句话比公式更重要。
很多业务正是因为“先快速排除绝大多数不存在请求”才会使用布隆过滤器。
核心结构
一个标准布隆过滤器只需要两样东西：
- 位数组
bitset - 多个哈希函数
插入元素时：
- 用
k个哈希函数算出k个位置 - 把这些位置都置为
1
查询元素时：
- 还是算出这
k个位置 - 只要有一个位置是
0，它就一定没出现过
为什么会有误判
因为不同元素可能把同一批位置都打成 1。
于是某个没加入过的元素，在查询时也可能碰巧命中全 1。
但它不会漏判，原因也很简单：
- 一个元素插入时打过的位，不会凭空变回
0 - 所以真插入过的元素，再查时至少不会出现“少了一位”
参数怎么理解
n：预期插入元素数量m：位数组长度k：哈希函数个数p：误判率
直觉上：
m越大，冲突越少，误判率越低k太少，信息不够；k太多，位数组又会过快填满
常见近似公式：
m = -(n * ln p) / (ln 2)^2
k = (m / n) * ln 2做题时知道量纲关系就够了，不必死背推导。
Go 代码：基础布隆过滤器
下面这个版本演示核心思路：
- 用
[]uint64作为位数组 - 用双哈希生成多个位置
- 支持
Add和Contains
type BloomFilter struct {
m uint64
k uint64
bits []uint64
}
func NewBloomFilter(expected int, falsePositiveRate float64) *BloomFilter {
m := optimalBitSize(expected, falsePositiveRate)
k := optimalHashCount(expected, m)
words := (m + 63) / 64
return &BloomFilter{
m: uint64(m),
k: uint64(k),
bits: make([]uint64, words),
}
}
func (bf *BloomFilter) Add(s string) {
h1, h2 := hashPair(s)
for i := uint64(0); i < bf.k; i++ {
pos := (h1 + i*h2) % bf.m
bf.setBit(pos)
}
}
func (bf *BloomFilter) Contains(s string) bool {
h1, h2 := hashPair(s)
for i := uint64(0); i < bf.k; i++ {
pos := (h1 + i*h2) % bf.m
if !bf.getBit(pos) {
return false
}
}
return true
}
func (bf *BloomFilter) setBit(pos uint64) {
word := pos / 64
bit := pos % 64
bf.bits[word] |= 1 << bit
}
func (bf *BloomFilter) getBit(pos uint64) bool {
word := pos / 64
bit := pos % 64
return (bf.bits[word] & (1 << bit)) != 0
}Go 代码：哈希和参数计算
func optimalBitSize(n int, p float64) int {
return int(math.Ceil(-float64(n) * math.Log(p) / (math.Ln2 * math.Ln2)))
}
func optimalHashCount(n, m int) int {
return int(math.Ceil(float64(m) / float64(n) * math.Ln2))
}
func hashPair(s string) (uint64, uint64) {
h1 := fnv.New64a()
_, _ = h1.Write([]byte(s))
h2 := fnv.New64()
_, _ = h2.Write([]byte("salt:"))
_, _ = h2.Write([]byte(s))
a := h1.Sum64()
b := h2.Sum64()
if b == 0 {
b = 1
}
return a, b
}业务里最常见的用法
缓存穿透防护
先查布隆过滤器：
- 如果判定不存在，就不访问数据库
- 如果判定可能存在，再继续查缓存或数据库
这样能挡掉大量根本不存在的 key。
大规模去重
例如：
- 爬虫 URL 去重
- 消息消费幂等校验
- 推荐流曝光去重
很多时候，少量误判是可以接受的，但内存节省非常划算。
为什么标准布隆过滤器不支持删除
因为一个位置上的 1 可能同时来自多个元素。
A 命中了位置 3、7、11
B 也命中了位置 7、12、20如果你把 A 删除并把位置 7 直接清零，就会把 B 也误伤掉。
所以标准版本通常只有：
AddContains
没有安全的 Remove。
如果一定要删除怎么办
可以用计数布隆过滤器：
- 不再用单个 bit
- 而是用计数器数组
- 插入时加一，删除时减一
但这样空间会明显上涨。
所以删不删得掉，不只是功能问题，也是空间权衡问题。
复杂度
如果用了 k 个哈希函数：
| 操作 | 时间复杂度 |
|---|---|
| 插入 | O(k) |
| 查询 | O(k) |
| 空间 | O(m) |
在业务里 k 一般是常数，所以可以看作常数时间。
什么时候该想到布隆过滤器
- 数据规模很大
- 只关心“是否可能存在”
- 能接受极低误判率
- 更想节省空间，而不是获得精确集合内容
如果题目要求下面这些能力，就别用标准布隆过滤器：
- 精确枚举所有元素
- 精确统计元素个数
- 可靠删除元素
- 完全无误判
易错点
布隆过滤器最容易误解的点
- 它没有假阴性，但有假阳性。
Contains == true不代表一定存在。- 标准版本不支持删除。
- 误判率不是固定不变的，插入越多，位数组越满，误判率会升高。
经典题目 / 思考题
- 手写一个支持
Add/Contains的 Bloom Filter - 推导
m和k的近似最优公式 - 比较布隆过滤器、计数布隆过滤器、布谷鸟过滤器的取舍
- 设计一个用于缓存穿透防护的布隆过滤器方案