一个被低估的数据结构
后端开发中经常遇到这类需求：判断一个元素是否在集合中存在。当数据量小的时候，一个 map 或 Set 就够了。但当数据量到亿级——比如邮箱是否已注册、URL 是否已爬取、手机号是否在黑名单——内存就吃不消了。
10 亿个 64 字符的字符串直接放内存，大约需要 60 GB。布隆过滤器用不到 2 GB 就能覆盖同样的数据量，代价只是极低的误判率。
厃普西隆：布隆过滤器的核心原理
布隆过滤器由 Burton Bloom 在 1970 年提出，核心思路是：用一个位数组加多个哈希函数，用空间换准确性。
它有两个关键特征：
- 可能误判（假阳性）：说存在，可能不存在
- 绝不漏判（假阴性）：说不存在，一定不存在
这个不对称性非常重要——它适合「宁可错杀，不可放过」的场景。
工作流程
初始化一个 m 位的位数组，全置 0。插入元素时，用 k 个哈希函数算出 k 个位置，全部置 1。查询时，同样算出 k 个位置，只要有一个位是 0，则元素一定不在；如果全是 1，则元素「可能」在。
1
2
3
|
位数组: [0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1]
↑ ↑ ↑ ↑
hash1(x) hash2(x) hash3(x) hash4(x)
|
不同元素的哈希位置会重叠，这就是误判的来源。但只要位数组够大、哈希函数够多，误判率可以控制在 1% 以下。
Go 原生实现
下面是一个最小可用的布隆过滤器实现，核心逻辑不到 60 行：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
|
package bloom
import (
"hash/fnv"
"math"
)
// BloomFilter 布隆过滤器
type BloomFilter struct {
bitmap []uint64 // 位数组，用 uint64 切片模拟
k int // 哈希函数数量
bits uint // 位数组总位数
}
// New 根据预期元素数 n 和目标误判率 p 计算最优参数
func New(n int, p float64) *BloomFilter {
// 最优位数组大小: m = -(n * ln(p)) / (ln(2)^2)
m := uint(math.Ceil(-1 * float64(n) * math.Log(p) / (math.Ln2 * math.Ln2)))
// 最优哈希函数数: k = (m/n) * ln(2)
k := int(math.Ceil(float64(m) / float64(n) * math.Ln2))
return &BloomFilter{
bitmap: make([]uint64, (m+63)/64),
k: k,
bits: m,
}
}
func (bf *BloomFilter) hash(data []byte, seed uint32) uint {
h := fnv.New32a()
h.Write([]byte{byte(seed), byte(seed >> 8), byte(seed >> 16)})
h.Write(data)
return uint(h.Sum32()) % bf.bits
}
func (bf *BloomFilter) setBit(pos uint) {
idx, offset := pos/64, pos%64
bf.bitmap[idx] |= 1 << offset
}
func (bf *BloomFilter) getBit(pos uint) bool {
idx, offset := pos/64, pos%64
return bf.bitmap[idx]&(1<<offset) != 0
}
// Add 添加元素
func (bf *BloomFilter) Add(data []byte) {
for i := 0; i < bf.k; i++ {
bf.setBit(bf.hash(data, uint32(i)))
}
}
// Contains 判断元素是否存在（可能有假阳性）
func (bf *BloomFilter) Contains(data []byte) bool {
for i := 0; i < bf.k; i++ {
if !bf.getBit(bf.hash(data, uint32(i))) {
return false // 任一位为 0，必定不存在
}
}
return true // 全为 1，可能存在
}
|
实际生产中不要自己造轮子——用 github.com/bits-and-blooms/bloom/v3 库，API 更完善，支持序列化和并发安全：
1
2
3
4
5
6
7
8
9
10
11
12
|
import "github.com/bits-and-blooms/bloom/v3"
// 容量 1000 万，误判率 0.1%
filter := bloom.NewWithEstimates(10000000, 0.001)
filter.Add([]byte("[email protected]"))
if filter.Test([]byte("[email protected]")) {
// 可能存在，查数据库确认
}
if !filter.Test([]byte("[email protected]")) {
// 一定不存在，直接返回
}
|
Redis 集成：跨进程共享布隆过滤器
单机布隆过滤器重启就丢失，多实例之间也无法共享。Redis 4.0+ 通过 RedisBloom 模块提供了原生的布隆过滤器支持：
Go 客户端用 github.com/redis/go-redis/v9 配合 RedisBloom：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
package main
import (
"context"
"fmt"
redisbloom "github.com/RedisBloom/redisbloom-go"
)
func main() {
client := redisbloom.NewClient("localhost:6379", "", nil)
ctx := context.Background()
_ = ctx
// 创建过滤器（已存在则忽略错误）
client.Reserve("url_seen", 0.01, 1000000)
// 爬虫去重场景
url := "https://example.com/page-123"
exists, _ := client.Exists("url_seen", url)
if exists {
fmt.Println("已爬取过，跳过")
return
}
// 抓取页面...
client.Add("url_seen", url)
fmt.Println("新增到爬取队列")
}
|
三个经典工程场景
场景一：缓存穿透防护
恶意请求大量不存在的 key，绕过缓存直击数据库。布隆过滤器挡在最前面：
1
|
请求 → 布隆过滤器拦截 → 命中？查缓存/DB → 未命中？直接返回空
|
启动时把数据库所有 ID 灌入布隆过滤器，请求先过布隆这一关。假阳性偶尔漏几个请求到数据库，不影响大局。
场景二：爬虫 URL 去重
10 亿 URL 全放内存要 60+ GB，布隆过滤器只需 1.7 GB（误判率 1%）。偶尔重复抓取几个页面，远比 60 GB 内存划算。
场景三：邮箱/手机号注册拦截
用户输入邮箱时，前端先查布隆过滤器。如果返回「不存在」，100% 可以放行注册；如果返回「可能存在」，再查数据库确认。大部分新邮箱直接通过，数据库压力大幅降低。
参数调优：误判率与内存的权衡
布隆过滤器没有银弹，核心是三个变量的关系：元素数 n、误判率 p、位数组大小 m、哈希函数数 k。
| 元素数 n |
误判率 p |
内存占用 |
哈希函数 k |
| 100 万 |
1% |
1.2 MB |
7 |
| 100 万 |
0.1% |
1.8 MB |
10 |
| 1 亿 |
1% |
114 MB |
7 |
| 1 亿 |
0.01% |
229 MB |
16 |
经验法则：先定 n（容量），再定 p（误判率），m 和 k 由公式自动算出。p 调小一档，内存翻倍但误判大幅下降。
一个容易踩的坑：布隆过滤器不支持删除。如果业务需要移除元素，用 Counting Bloom Filter（每个位用计数器代替 0/1），或改用 Cuckoo Filter。
总结
布隆过滤器解决的不是「存什么」，而是「肯定不存在」这个判断。它的不对称性——假阴性为零，假阳性可控——让它在缓存防护、去重、黑名单等场景无可替代。
实践建议：
- 优先用 RedisBloom，跨进程共享且支持持久化
- 误判率起步设 1%，够用再降
- 容量预估宁大勿小，满了误判率会指数上升
- 需要删除时换 Cuckoo Filter，别硬删
掌握布隆过滤器，你就在工具箱里多了一把专门解决「海量数据存在性判断」的利器。