布隆过滤器：用 1% 的内存做 99% 的事

亲手玩一个布隆过滤器

一个 64 位的迷你布隆过滤器，3 个哈希函数。插入元素看位数组亮起来，查询不存在的元素看它怎么判定。多插几个试试能不能碰到误判。

试试：

已插入 0 个元素

填充率 0%

误判挑战：你能让它说谎吗

一个 1024 位的布隆过滤器，7 个哈希函数。每插入一个词，系统自动用 100 个随机串检测误判。看你插到第几个词时它会第一次骗你。

快速填充：

已插入

0

填充率

0%

累计误判

0

首次误判于第
—
个元素

参数调优实验室

调节三个参数，实时观察布隆过滤器的填充率和误判率变化。理解为什么 k=7 时误判率最低。

元素数量 (n) 1,000

位数组大小 (m) 10,000 bits

哈希函数数量 (k) 7

理论误判率

—

P = (1 - e^-kn/m)^k

位数组填充率

—

最优 k 值

—

k_opt = (m/n) × ln2

内存占用
—

位数组状态（前 512 位）

内存对决：布隆过滤器 vs HashSet

存 N 个元素，两种方案各需要多少内存？随着 N 增大，差距指数级拉开。

元素数量： 10,000,000

HashSet / HashMap

—

每个元素 ~40 bytes（对象头 + 哈希 + 指针 + 字符串）

布隆过滤器（0.1% 误判）

—

每个元素 ~14.4 bits（由误判率决定）

关键洞察

存 10 亿个元素：HashSet 需要 ~40 GB，布隆过滤器只需要 ~1.7 GB。节省 95.7% 内存，代价仅 0.1% 误判率。

布隆过滤器的核心直觉

01

一个比特值千金

HashSet 存完整元素（字符串、对象），一个元素 40+ bytes。布隆过滤器只在位数组上翻几个 bit，一个元素 ~14 bits。代价是放弃了"存原始数据"的能力。

02

多个哈希函数 = 交叉验证

一个哈希函数容易碰撞，k 个哈希函数同时命中才判定"存在"。碰撞概率从 1/m 降到 (1/m)^k。k 越大越准——但填得也越快。

03

单向安全

说"不在"就一定不在（零漏报），说"在"可能误判。这正好适合安全场景：宁可多查一次数据库，不能放过一个危险密码。

04

现实中的布隆过滤器

Chrome 恶意网址检测（本地快速过滤）、Medium 文章去重推荐、Cassandra/HBase 读优化、爬虫 URL 去重——都在用它省内存。