在 Redis 的面试中，HyperLogLog 是一个高频考点。它常被用来解决“海量数据的基数统计”问题，比如统计每天访问网站的独立 IP 数、搜索关键词的独立用户数等。相比使用 Set 或 Hash 存储每一个元素，HyperLogLog 最大的优势在于：用极小的内存（12KB）就能统计接近 2^64 个元素的基数，标准误差仅 0.81%。但它的代价是只能给出近似值，且无法获取原始元素。下面我们从底层原理到误差分析，彻底搞懂它。
一、为什么需要 HyperLogLog？
假设你要统计 1 亿个用户的 UV。如果用 Set 存储用户 ID，每个 ID 假设 8 字节，加上 Redis 的哈希表开销，内存可能达到 GB 级别。而 HyperLogLog 只需要 12KB，相差近十万倍。它不存储元素本身，而是通过概率算法估算集合的基数。因此它非常适合对精度要求不是 100% 严格、但内存敏感的场景。
二、HyperLogLog 的核心思想：伯努利实验与调和平均数
HyperLogLog 基于一个简单的概率观察：抛硬币直到出现正面，记录抛掷次数。如果一次实验中出现了连续 k 次反面然后正面，那么 k 的概率服从几何分布。对于一组随机数，我们可以用每个数的二进制表示中“第一个 1 出现的位置”来模拟这个实验。
具体来说，对于每个元素，HyperLogLog 会：
- 用一个哈希函数将它映射成一个 64 位的二进制串。
- 取低 14 位作为桶的编号（Redis 中桶的数量 m = 2^14 = 16384）。
- 剩余 50 位中，从低位开始数，统计第一个 1 出现的位置（即前导零个数 + 1），记为 k。
- 每个桶记录该桶中出现过的最大 k 值。
最后，根据所有桶的最大 k 值，用调和平均数估算基数。直观理解：如果桶中最大的 k 很大，说明有很多元素，因为出现大 k 的概率很低，只有元素数量足够多时才会出现。
三、Redis 的实现细节
Redis 的 HyperLogLog 结构体 hllhdr 如下（简化）：
struct hllhdr {
char magic[4]; // "HYLL"
uint8_t encoding; // 0 表示稀疏，1 表示稠密
uint8_t notused[3];
uint8_t card[8]; // 缓存的基数估计值
uint8_t registers[]; // 桶数组
};
- 桶数量：固定为 16384（2^14），每个桶用 6 bit 存储，因此稠密模式占用 16384 * 6 / 8 = 12288 字节，加上头部共 12KB 多一点。
- 稀疏编码：当基数较小时，为了节省内存，Redis 使用稀疏表示（ZERO、XZERO、VAL 三种操作码），此时内存可能只有几十字节到几百字节。当稀疏表示超过一定阈值（默认 3000 字节）时，会自动转换为稠密表示。
- 基数缓存：
card[8]缓存上一次计算的基数，如果自上次计算后没有修改，则直接返回缓存值。注意最高位是无效位标志。
四、误差来源与理论分析
HyperLogLog 的误差主要来自两个方面：
- 哈希碰撞：不同元素可能映射到相同的桶和相同的 k 值，导致低估。但 64 位哈希的碰撞概率极低，可以忽略。
- 随机波动：由于每个桶的 k 值是随机的，最终估计值是一个随机变量。根据论文，标准误差（相对误差）约为：
[
\frac{1.04}{\sqrt{m}}
]
其中 m 是桶的数量。对于 m = 16384，标准误差 = 1.04 / 128 ≈ 0.81%。这意味着在 95% 的情况下，误差不超过 1.62%（2 倍标准误差）。
Redis 官方文档也明确说明：HyperLogLog 的标准误差是 0.81%。
五、偏差修正
原始的 HyperLogLog 在小基数和大基数时会有偏差。Redis 采用了以下修正：
- 小基数修正：当估计值小于 2.5 * m 时，使用线性计数（Linear Counting）方法，公式为
m * log(m / V)，其中 V 是空桶的数量。这能显著降低小基数时的误差。 - 大基数修正：当估计值接近 2^64 时，使用一个修正公式避免溢出。但实际中几乎不会遇到。
Redis 源码中的 hllCount 函数实现了这些修正。
六、面试常见问题
Q1：HyperLogLog 为什么用 16384 个桶？
A：这是精度和内存的权衡。16384 个桶对应 12KB 内存，误差 0.81%。如果桶数减半，误差会增大到约 1.15%，但内存只省 6KB。Redis 选择了这个平衡点。
Q2：HyperLogLog 能获取元素吗？能删除元素吗？
A：不能。它只存储哈希后的概率信息，不存储原始元素。删除元素会破坏概率分布，因此标准 HyperLogLog 不支持删除。Redis 提供了 PFADD、PFCOUNT、PFMERGE，但没有 PFDEL。
Q3：PFADD 和 PFCOUNT 的时间复杂度？
A：PFADD 是 O(1)，因为只需要计算哈希并更新一个桶。PFCOUNT 在稠密模式下是 O(m)，即 16384 次操作，但实际非常快；如果使用缓存，则 O(1)。PFMERGE 是 O(m)。
Q4：HyperLogLog 和 Bitmap 的区别？
A：Bitmap 精确统计，但需要知道最大 ID，内存与最大 ID 成正比。HyperLogLog 近似统计，内存固定 12KB，与元素数量无关。
七、总结
HyperLogLog 是一个精巧的概率数据结构，通过哈希、分桶、调和平均数，以 0.81% 的误差换取了极低的内存占用。Redis 在其基础上增加了稀疏编码、基数缓存和小基数修正，使其在工程上更加实用。面试中除了记住 12KB、16384、0.81% 这几个数字，更要理解其背后的伯努利实验和调和平均思想，以及为什么它不能获取元素、不能删除元素。掌握这些，你就能从容应对相关面试题。
未经允许不得转载：任鹏个人博客 » Redis 的 HyperLogLog 底层原理和误差分析
