HyperLogLog (HLL)

引言：“独立访客”问题

你是一家社交媒体网站的 CTO。你想统计今天有多少 独立 (Unique) 用户访问了某个特定页面（即基数估计）。

• 集合法： 将每个用户 ID 存入 Hash Set。1 亿个 ID $imes$ 8 字节 $\approx$ 800MB。如果有 10,000 个页面，你需要 8TB 内存。这根本不现实。
• HyperLogLog： 仅使用 1.5 KB 内存即可统计这 1 亿个用户，误差约为 2%。

HyperLogLog 是一种解决 去重计数 (Count-Distinct) 问题的概率算法。它是 Redis、BigQuery 和 AWS Redshift 处理海量数据的核心工具。

算法要解决什么问题？

• 输入： 元素流。
• 输出： 已见过的 唯一 元素数量的估算值。
• 承诺： 内存占用极小且固定，无论你统计的数据量是 1 万还是 10 亿。

核心思想 (直觉版)

想象 抛硬币。

• 如果我告诉你：“我抛硬币，开头连续出了 3 个反面 (TTT…)”，你会猜我大概抛了 8 次左右。
• 如果我告诉你：“我开头连续出了 20 个反面 (TTTT…TT)”，你会猜我大概抛了上百万次。

HyperLogLog 将这种逻辑应用到了数据上：

1. 将元素哈希为二进制字符串。
2. 观察哈希值中 前导零的数量。
3. 看到的前导零越多，说明集合中存在的唯一元素可能就越多。
4. 为了避免偶然性，它将数据分到多个“桶”中并取平均值。

为什么要用它？

• ✅ 极致省钱： 它是空间的绝对王者。它能在比一条推文还小的空间里统计数十亿项数据。
• ✅ 可合并性： 你可以分别计算“周一”和“周二”的 HLL，然后直接合并它们，得到“整周”的去重计数，结果非常准确。

典型业务场景

• ✅ DAU/MAU 统计： 实时估算日活/月活用户数。

• ✅ 广告技术： 在数十亿次广告展示中，统计有多少个独立用户看过了广告。

• ✅ 网络安全： 统计连接到服务器的唯一 IP 数量，以检测 DDoS 攻击。

• ❌ 需要精确值： 如果出于计费或法律原因需要精确到个位数的数值，HLL 不适合你。它的标准误差约为 2%。

性能与复杂度总结

• 时间： 添加和查询均为 $O(1)$。
• 空间： $O(\log \log N)$（在实践中几乎是常数，如 1.5KB）。

小结：一句话记住它

“HyperLogLog 是‘估算的奇迹’。它将統計數十億數據的任務轉化為一個關於‘數零’的統計遊戲。當‘足夠接近’能換取一萬倍的內存節省時，請使用它。”