BLOOM FILTER · BF.ADD · BF.EXISTS · HYPERLOGLOG · PFADD · PFCOUNT · PFMERGE

容忍一点点误差，换回几百上千倍的内存

有些问题不需要绝对精确。“这个用户 ID 存不存在”允许偶尔答错一次“存在”；“今天有多少不同的人来过”差 1% 也没关系。布隆过滤器和 HyperLogLog 就是用这点误差，把几个 GB 的数据压成几 MB 甚至 12 KB。

布隆过滤器Bloom Filter

像门口的保安：说“没来过”就一定没来过；说“来过”，有小概率认错人。

回答：在不在？不能删不能列出成员

HyperLogLogPFADD / PFCOUNT

像数人头：不记谁来过，只记一个“最稀罕的现象”有多稀罕，由此估出大概多少人。

回答：有多少个不同的？误差约 0.81%固定 12 KB

同样是 1 亿个用户 ID，存法不同，内存差多少（对数刻度）

Set（精确）

约 6 GB

布隆过滤器 1%

约 120 MB

Bitmap（ID 是连续整数时）

12.5 MB

HyperLogLog

12 KB

刻度是对数的：左端 1 KB，右端 10 GB，每往右七分之一就大 10 倍。Set 的大小是粗略估算；Bitmap 只在 ID 是从 0 开始的连续整数时这么省，ID 是字符串就用不了。

位数组m 个 bit

布隆过滤器的全部家当，一开始全是 0。

越大，误判越少

哈希函数k 个

把一个元素映射到 k 个位置，同一个元素每次结果都一样。

太少太多都不好

抛硬币前导 0 的个数

哈希值像抛硬币，连续的 0 越长越罕见，罕见说明人多。

HyperLogLog 的核心

分桶16384 个寄存器

只看一次运气偏差太大，分成很多桶再取平均。

每桶 6 bit，共 12 KB

布隆过滤器：写进去、查一查

一个 m 位的位数组，加上 k 个哈希函数。下面用 16 位、3 个哈希函数举例（Redis 第 01 篇里它用来挡缓存穿透）。

写入 user:1 和 user:2

user:1→ 3 个哈希 → 位置 2、7、11

user:2→ 3 个哈希 → 位置 5、7、14

0010010100010010

把这几个位置设成 1。第 7 位被两个元素共用了，这就是为什么不能删除：把 user:1 的位清掉，user:2 也会“消失”。

查询 user:3 和 user:9

user:3→ 位置 2、9、14 → 第 9 位是 0 → 一定不存在

user:9→ 位置 5、11、14 → 全是 1 → 说“可能存在”，其实是误判

查 user:3（框出的是它的 3 个位置）

0010010100010010

查 user:9

0010010100010010

只要有一位是 0，就肯定没写过。全是 1 时，也可能是别的元素凑巧把这几位都点亮了。

误判率 ≈ (1 − e^−k·n/m)^k　　最好的 k ≈ (m / n) · ln 2　　需要的位数 m ≈ −n · ln p / (ln 2)²

n 是已经放进去的元素个数，p 是想要的误判率。直觉上：位数组越满（n/m 越大），误判越多；哈希函数太少，每个元素留下的“指纹”太短；太多又会把位数组点得太满。

误判率实验室

调位数组大小、哈希函数个数、放进去多少元素，看位数组被点亮了多少，以及拿 4000 个没放进去的元素去查，有多少被误判成“存在”。

位数组 m：

哈希个数 k：

已放入 n：20 个

生产上要开多大、怎么用

按公式算：元素越多、要求误判率越低，位数组越大，哈希次数也越多。

预计元素数	误判率 1%	误判率 0.1%	误判率 0.01%

RedisBloom 命令Redis 8 内置，之前要装模块

BF.RESERVE user:bf 0.01 100000000   # 误判率 1%，预计 1 亿个
BF.ADD user:bf u:1001                → 1（新加入）
BF.MADD user:bf u:1002 u:1003
BF.EXISTS user:bf u:9999             → 0 一定没有；1 可能有
BF.INFO user:bf                      # 容量、已放入个数、占多少内存

# 不先 RESERVE 就 BF.ADD，会按默认容量 100、误判率 1% 自动建一个，
# 很快就要叠很多层

# 放满后默认自动再叠一层更大的子过滤器（EXPANSION 2），
# 新层的误判率更低，总误判率仍控制在目标附近；NONSCALING 则不扩
# 代价是每次查询要把每一层都查一遍

Java：Redisson / Guava不用装模块

// Redisson：底下用 Redis 的 Bitmap，多个实例共享
RBloomFilter<String> bf = redisson.getBloomFilter("user:bf");
bf.tryInit(100_000_000L, 0.01);     // 只在第一次生效
bf.add("u:1001");
boolean maybe = bf.contains("u:9999");

// Guava：放在本机内存里，每个实例各一份
BloomFilter<String> local = BloomFilter.create(
        Funnels.stringFunnel(StandardCharsets.UTF_8), 1_000_000, 0.01);

要能删除？普通布隆过滤器删不了。要删除用布谷鸟过滤器（Cuckoo Filter）：它存的是每个元素的一小段“指纹”，可以 CF.DEL，内存和布隆是同一个量级。代价是只能删确实加过的元素，删一个没加过的，可能把别人的指纹删掉。命令是 CF.RESERVE、CF.ADD、CF.EXISTS、CF.DEL。

HyperLogLog：从抛硬币里估人数

一直抛硬币，记下“最长连着出了几次反面”。连着 5 次反面的概率是 1/32，你见到了，说明大概抛了 32 次左右。HyperLogLog 把每个元素哈希成一串 0 和 1，就像一次抛硬币。

Redis 怎么拆一个 64 位的哈希值

10110010100110 0001011…

14 位：选 16384 个桶中的哪一个后 50 位：开头连着几个 0第一个 1 在第 4 位，这个桶记 4（只保留最大值）

为了好看画成从左往右数；Redis 实际用低 14 位选桶、从低位往高位数，道理一样。

为什么要分桶

只看一个“最长纪录”，运气成分太大：第一个人就碰上 20 个 0，估出来就是一百万。分成 16384 个桶，每个桶各记各的，最后取调和平均，误差降到约 1.04 / √16384 ≈ 0.81%。

为什么是 12 KB

每个桶记的是“最多连着几个 0”，最大也就 50 多，用 6 位就够。16384 × 6 位 = 12288 字节。元素少的时候还会用更省的稀疏格式，超过 3000 字节（hll-sparse-max-bytes）才转成这 12 KB。

为什么重复不影响

同一个元素哈希值永远一样，落在同一个桶、同一个数字，取最大值时什么都不会变。所以它天然就是“去重计数”。

估数实验台

往里加不重复的用户，看两个 HyperLogLog 的估算：一个只有 64 个桶（下面画出来的），一个和 Redis 一样有 16384 个桶。再加一批已经来过的老用户，看看数字会不会变。

HyperLogLog 命令和典型用法

最常见的用途是统计 UV：每天一个 key，用户来了就 PFADD；要看一周的 UV，把七天合并起来再数。

redis-cliRedis 2.8.9 起就有

PFADD uv:2026-11-05 user:1 user:2 user:3   → 1（有桶被更新了）
PFADD uv:2026-11-05 user:1                 → 0（来过了，没有桶变化）
PFCOUNT uv:2026-11-05                      → 3
PFMERGE uv:week45 uv:2026-11-02 … uv:2026-11-08   # 合并一周
PFCOUNT uv:week45
PFCOUNT uv:2026-11-05 uv:2026-11-06        # 多个 key 临时合并再数，比较慢

Spring Data RedisHyperLogLogOperations

HyperLogLogOperations<String, String> hll = redis.opsForHyperLogLog();
hll.add("uv:" + today, userId);
Long uv = hll.size("uv:" + today);
hll.union("uv:week45", days.toArray(new String[0]));   // 就是 PFMERGE

它本质是一个 String，能 GET 出来、能跟着 RDB 一起持久化。单个 key 的 PFCOUNT 会把结果缓存在头部，没有新写入时直接返回；Redis 的估算公式在原论文基础上改进过，小基数和大基数都比较准。

该用哪一个

先问清楚要回答的是哪个问题：“在不在”、“有多少个”，还是“都有谁”。

	Set	Bitmap	布隆过滤器	布谷鸟过滤器	HyperLogLog
精确吗	精确	精确	“不在”精确，“在”有误判	同布隆	误差约 0.81%
判断某个在不在	能	能	能	能	不能
数有多少个	SCARD	BITCOUNT	只能估	只能估	PFCOUNT
列出都有谁	能	能（遍历位）	不能	不能	不能
删除	能	能	不能	能	不能
1 亿个时的内存	约 6 GB	12.5 MB（ID 连续时）	约 120 MB（1%）	和布隆同一量级	12 KB
典型用途	好友列表、标签	签到、在线状态	防缓存穿透、爬虫去重	需要删除的黑名单	UV、搜索词去重计数

Redis 版本，以及 JDK 8 和 JDK 17

HyperLogLog 很早就是内置类型；布隆过滤器长期是模块，Redis 8 才内置。Java 这边两种都有现成的库。

Redis 7 及以前 · Boot 2

JDK 8+

HyperLogLog 2.8.9 起内置
BF.* 和 CF.* 要装 RedisBloom 模块，或用 Redis Stack；云厂商的托管版不一定有
没模块时用 Redisson 的 RBloomFilter（基于 Bitmap），或 Guava 的本地 BloomFilter

Redis 8 · Boot 3

JDK 17+

布隆、布谷鸟，以及 Count-Min Sketch、Top-K、t-digest 这些概率结构都内置了
Spring Data Redis 有 opsForHyperLogLog()，但没有 BF 命令的 API；可以用 Jedis 的 bfAdd / bfExists，或者 Redisson
Redisson、Guava 在 JDK 8 和 17 上用法一样

没变的：布隆“说没有就一定没有”布隆不能删HLL 固定 12 KBHLL 误差约 0.81%

常踩的坑

概率结构的坑，基本都是没想清楚它能回答什么、不能回答什么。

上线半年后，布隆过滤器的误判率从 1% 涨到 44%

按 100 万、1% 建的，实际塞了 300 万。Redisson 和 Guava 的过滤器不会扩容，误判率一路上涨；RedisBloom 默认会叠新层，误判率稳得住，但查询要多查几层。建的时候按增长预留容量，或者定期重建。

新注册的用户被当成“不存在”拦掉了

写数据库时忘了同时写过滤器，它就一定说“没有”。新增数据的地方都要同步 BF.ADD，启动时全量加载一次。

删掉的商品，过滤器还说“可能有”

布隆删不掉，只是多查一次库，不算错。删得多了误判会升高，定期重建，或改用布谷鸟过滤器。

Java 写入的过滤器，Go 服务查不到

各家库的哈希算法和位置计算都不一样，Guava、Redisson、RedisBloom 互不兼容。所有服务用同一种实现，最省事的是都调 BF.* 命令。

误判率设成 0.0001%，内存和 CPU 都涨了

1% 时每个元素约 9.6 位、7 次哈希；0.0001% 要 28.8 位、20 次哈希。误判率每降 10 倍，每个元素多花约 4.8 位。一般 1% 配合“说有时再查一次库”就够了。

一个布隆过滤器几百 MB，成了大 key

迁移、持久化都卡（Redis 第 08 篇）。按 ID 取模拆成几个过滤器，分到不同节点。

想用 HyperLogLog 判断“这个用户今天来过没”

它只能数个数，不能查成员。要判断某人来没来过，用 Bitmap（ID 是整数时）或 Set。

用 HyperLogLog 的数字做结算，对不上账

它有约 1% 的误差。报表、看趋势没问题；要和钱、合同挂钩的计数，用精确的 Set 或数据库。

报表里 PFCOUNT 30 个 key，接口很慢

多个 key 时要临时合并，不走缓存。提前用 PFMERGE 合并好周、月的 key，查询时只数一个。

用 Set 统计每天的 UV，几周后内存告急

每天几千万个 ID，每个 Set 几个 GB。只要数字就换 HyperLogLog，一天一个 key 只要 12 KB。