HyperLogLog

发表于 分类于 ， ，

UV访问量

UV:全称uniqueVisitor,也叫独立访客量,
是指通过互联访问、浏览这个页的自然人。1天内同个户多次访问该站,只记录1次。

PV:全称PageVieW,也叫页访问量或点击量,
用户每访问站的个页,记录1次PV,用户多次打开页,则记录多次PV。往往来衡量站的流量。

HyperLogLog 详解:为什么它能用 12KB 左右统计海量去重数

目录

  1. HyperLogLog 是什么,它到底解决了什么问题
  2. 它为什么能省内存:从 Set 的痛点说起
  3. 核心原理直觉:为什么“前导零”可以拿来估算基数
  4. Redis 里怎么用:命令、性能、实现细节
  5. 业务里怎么落地:典型场景、Key 设计、和 Set/Bitmap 的选择
  6. 面试怎么答:高频问法、易错点、你该掌握到什么深度

测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
@Test
void testHyperLogLog() {
    // 准备数组，装用户数据
    String[] users = new String[1000];
    // 数组角标
    int index = 0;
    for (int i = 1; i <= 1000000; i++) {
        // 赋值
        users[index++] = "user_" + i;
        // 每1000条发送一次
        if (i % 1000 == 0) {
            index = 0;
            stringRedisTemplate.opsForHyperLogLog().add("hl11", users);
        }
    }

    // 统计数量
    Long size = stringRedisTemplate.opsForHyperLogLog().size("hl11");
    System.out.println("size = " + size);
}

一图先看懂

1
2
3
4
5
输入（userId / IP / deviceId）
        ↓
hash → 分桶 → 记录“最长前导零”这类统计特征
        ↓
输出近似去重数（approximate distinct count）

HyperLogLog 是一种 probabilistic data structure,用来估算一个集合里 去重后的元素个数,也就是 cardinality。它不是拿来保存所有成员的,而是拿来保存“估算所需的统计状态”的。

你可以先记住一句话:

HyperLogLog 解决的是海量数据的去重计数问题,不是精确存储所有去重元素的问题。

1. HyperLogLog 是什么,它到底解决了什么问题

先抓住核心定义:

HyperLogLog 用来做 approximate distinct count,也就是近似去重计数。

典型场景:

  • 网站一天的 UV
  • 某活动期间的 独立设备数
  • 某接口的 独立 IP 数
  • 某搜索词池里的 独立 query 数

这些场景的共同点是:

  • 数据量很大
  • 重复值很多
  • 你只关心“有多少种不同元素”
  • 不关心把所有去重后的成员都取出来

它不是什么

很多人第一次会误会:

“它是不是 Set 的压缩版?”

不是。

  • Set:目标是 精确存成员
  • HyperLogLog:目标是 近似估个数

所以两者不是一个方向的工具。

一句话理解

HyperLogLog 不是“存了很多元素但是更省”,而是:

压根不存元素本身,只存估算这些元素数量所需的统计特征。

2. 它为什么能省内存:从 Set 的痛点说起

假设你想统计某天 UV。

最直觉的做法是用 Set:

1
2
3
SADD uv:2026-03-30 user:1001
SADD uv:2026-03-30 user:1002
SCARD uv:2026-03-30

这套方案的优点:

  • 结果 精确
  • 可以判断成员是否存在
  • 还能做交集、并集、差集等集合运算

但缺点也很明显:

  • 你必须真的把每个唯一元素都存进去
  • 去重元素越多,内存越大
  • 到了百万、千万量级时,成本会很可观

HyperLogLog 的 trade-off

HyperLogLog 的思路是:

  • 放弃绝对精确
  • 换取极低内存占用

你可以把它理解成下面这个对比:

方案 存什么 结果 内存增长方式
Set 真正的成员 精确 基本随成员数增长
HyperLogLog 统计状态 近似 近似常量级

这个 trade-off 的本质

Set 的逻辑是:

我把所有去重后的元素都记住,所以结果一定准。

HyperLogLog 的逻辑是:

我不记住元素是谁,我只记录它们留下的统计特征,所以极省空间,但不是 100% 精确。

这就是它值钱的地方。

3. 核心原理直觉:为什么“前导零”可以拿来估算基数

这一部分你不用先背公式,先吃掉 intuition。

3.1 先把元素做 hash

比如一个 userId 经过哈希后,可能得到这样的二进制模式:

1
2
3
001011...
000001...
101101...

一个关键前提是:

好的 hash 输出,在统计意义上应该接近随机。

也就是说,每个元素经过 hash 后,看起来像一个随机比特串。

3.2 为什么前导零长度有价值

如果一个随机比特串前面有很多个 0,那它是比较“稀有”的。

比如:

  • 1xxxx... 很常见
  • 01xxxx... 少一点
  • 001xxxx... 更少
  • 000001xxxx... 就更稀有

所以随着样本越来越多,你更可能看到“更罕见的模式”。

于是就有了一个直觉:

如果我看到非常长的前导零,说明我已经观察过相当多的样本了。

这就是 HyperLogLog 能估算基数的核心感觉。

3.3 为什么要分桶

如果你只看“全局最长前导零”,波动会非常大,不稳定。

所以 HyperLogLog 会把数据拆到很多 bucket / register 里:

  1. 先用哈希值的一部分来决定落到哪个桶
  2. 再用剩下的部分去统计前导零长度
  3. 每个桶分别记录一个局部统计特征
  4. 最后把所有桶的信息汇总,得到更稳定的估计值

你可以把它理解成:

一个桶的观察值不可靠,那就用很多桶一起投票。

3.4 你面试时怎么说原理

不用推公式,讲到这一步就已经很够用了:

HyperLogLog 会先对元素做 hash,再把 hash 值拆成“分桶信息 + 统计信息”。每个桶记录一个稀有度特征,常见解释就是前导零长度,最后再把多个桶的结果综合起来,估算整体去重数量。它保存的是统计状态,不是元素本身。

这个回答对实习面试已经很 solid。
误差小于0.81%

4. Redis 里怎么用:命令、性能、实现细节

这一部分最实战。

4.1 三个核心命令

Redis 里 HyperLogLog 最核心就 3 个命令:

  • PFADD:加入元素
  • PFCOUNT:查看近似去重数
  • PFMERGE:合并多个 HLL

最小例子

1
2
3
4
5
6
PFADD uv:2026-03-30 u1 u2 u3
PFCOUNT uv:2026-03-30

PFADD uv:2026-03-31 u2 u4
PFMERGE uv:2days uv:2026-03-30 uv:2026-03-31
PFCOUNT uv:2days

这段表达的是:

  • 每来一个用户,就 PFADD
  • 想知道当天 UV,就 PFCOUNT
  • 想知道两天总去重,就 PFMERGE 后再 PFCOUNT

4.2 命令理解

PFADD

1
PFADD uv:day:2026-03-30 user:1001 user:1002

作用:把元素加入 HyperLogLog。

理解重点:

  • 不是把成员原样存在里面
  • 而是用这些成员去更新内部统计状态

PFCOUNT

1
PFCOUNT uv:day:2026-03-30

作用:返回这个 HLL 当前估算出的去重数。

注意:

  • 是 近似值
  • 不是绝对精确值

PFMERGE

1
PFMERGE uv:week:2026-W14 uv:day:2026-03-30 uv:day:2026-03-31

作用:把多个 HLL 合并成一个新的 HLL。

这个非常适合:

  • 日 UV 合并成周 UV
  • 多渠道 UV 合并成总 UV
  • 多节点统计结果归并

4.3 性能理解

实践里你可以这样记:

  • PFADD:很轻量,适合高频写入
  • PFCOUNT:单 key 查询通常很快
  • PFMERGE:适合做周期性统计归并

一个经验点:

如果你经常需要查多个窗口的 union,最好提前 merge 出结果 key,而不是每次临时现算。

4.4 Redis 实现层面的几个记忆点

你现在记住这几个点就够了:

1 它在 Redis 里本质上编码成 String

这点比较 cool,说明它不是一个“能遍历成员的集合型结构”,而是一个特殊编码的数据块。

2 它会根据规模采用不同表示方式

元素较少时会更节省;规模起来后进入更稳定的 dense 表示。

3 常见口径:大约 12KB

大家经常说:

“HyperLogLog 只要 12KB 左右。”

你可以把这个记成 Redis 实现层面的一个代表性特征。

5. 业务里怎么落地:典型场景、Key 设计、和 Set/Bitmap 的选择

5.1 典型业务场景

最常见就是按时间窗口做 UV 统计。

Key 设计示例

1
2
3
4
uv:day:2026-03-30
uv:day:2026-03-31
uv:week:2026-W14
uv:month:2026-03

每来一个用户就写入

1
PFADD uv:day:2026-03-30 user:1001

查当天 UV

1
PFCOUNT uv:day:2026-03-30

合并多天

1
2
PFMERGE uv:tmp:2026-03-30_2026-03-31 uv:day:2026-03-30 uv:day:2026-03-31
PFCOUNT uv:tmp:2026-03-30_2026-03-31

这种设计的优点:

  • 统计口径清晰
  • 方便按天、周、月聚合
  • 不会把所有历史都堆进一个 key

5.2 HyperLogLog vs Set vs Bitmap

这是面试很爱问的对比。

方案 适用场景 优点 缺点
Set 要精确去重,还要成员能力 结果精确,可判断成员 内存随成员数增长
HyperLogLog 只关心去重数 极省内存,可合并 有误差,不能取成员
Bitmap 用户 ID/状态可映射为位偏移 一位表示一个状态,适合布尔型统计 依赖可映射 offset,不适合任意字符串成员

三者怎么选

选 Set

当你:

  • 必须精确
  • 还要判断成员是否存在
  • 可能要做交集 / 并集 / 差集

选 HyperLogLog

当你:

  • 只关心去重数
  • 数据量很大
  • 可以接受小误差
  • 想把内存压到很低

选 Bitmap

当你:

  • 成员天然能映射为整数位偏移
  • 你关心的是“出现过 / 没出现过”这种布尔状态
  • 例如签到、活跃、打标等场景

6.2 面试官可能追问什么

Q1:为什么它能这么省内存?

答:因为它不存成员本身,只存统计特征,所以内存占用非常低。

Q2:为什么会有误差?

答:因为它本质是概率估计,不是 exact counting。

Q3:能不能判断某个元素在不在里面?

答:不能。它只能估算 distinct count,不能做 membership query。

Q4:多个时间窗口怎么统计总去重?

答:可以通过 PFMERGE 合并多个 HLL,再 PFCOUNT 统计。

Q5:和 Set 最大区别是什么?

答:Set 存的是成员,所以精确但更占内存;HLL 存的是统计状态,所以省内存但有误差。

6.3 面试中的易错点

易错点 3:不知道它为什么适合 UV

要答出:

  • 重复很多
  • 只关心去重数
  • 数据量大
  • 对小误差可接受

易错点 4:原理讲太深把自己讲乱

你现在阶段,没必要背公式推导。

讲清楚:

  • hash
  • 分桶
  • 前导零直觉
  • 多桶综合估计

结尾总结

你把 HyperLogLog 记成这句话,基本就稳了:

它不是拿来“存去重成员”的,而是拿来“估去重数量”的。

所以它最擅长的是:

  • 数据量大
  • 重复很多
  • 只关心去重数
  • 能接受少量误差

而它不擅长的是:

  • 要精确
  • 要成员列表
  • 要判断某元素是否出现过
  • 要审计 / 计费级准确性

附:面试速背版

1
2
3
4
5
HyperLogLog 是一种概率型数据结构，用于近似统计集合基数，也就是去重后的数量。
它适合做 UV、独立 IP、独立设备数这类场景。
它不保存原始成员，只保存统计状态，所以极省内存。
Redis 里常用命令是 PFADD、PFCOUNT、PFMERGE。
如果业务要求精确去重，我会选 Set；如果只关心去重数且数据量很大，我会选 HyperLogLog。