HyperLogLog：不保存所有访客 ID，怎样估算独立访客数？

网站想统计一个月有多少独立访客，最直接的办法是保存每个访客标识，再去重计数。但数据量可能很大，保存和排序所有 ID 既占空间，也增加处理成本。HyperLogLog 是一种概率型基数估计算法：它不保留每个元素，而是用少量寄存器摘要估算集合里有多少个不同元素。

算法先把每个输入映射为近似均匀的哈希值。哈希值的二进制开头往往会出现一段零；观察这段连续零的长度，偶尔出现很长零串，通常意味着已经看过了相当多样本。HyperLogLog 把哈希空间分成多个桶，每个桶记录自己遇到的最长零串特征，再综合这些统计量估计总基数。

单个桶的估计会有较大波动，多个桶的统计聚合能降低误差。寄存器数量增加时，通常可用更多内存换取更小的相对误差。它的空间使用不会随着访客人数线性增长，因此即便集合达到数亿级，仍可能只需要相对精简的摘要结构。具体误差会受寄存器配置、哈希质量和实现细节影响，不应把估算值当作精确计数。

HyperLogLog 还有一个很实用的性质：相同配置、兼容哈希规则的两个摘要可以合并，得到两个集合并集的估计。这让分布式系统可以先在各机器上统计，再把小型摘要汇总，而无需把全部用户 ID 拉到中心服务器。但摘要只能回答“有多少不同元素”这类问题，不能告诉你访客具体是谁，也不能还原元素名单。

它适合做趋势指标和容量估算，例如统计搜索词种类、独立访问量或去重设备数。若应用要求财务结算、抽奖资格或精准审计，概率误差可能不可接受，仍应采用精确集合或数据库去重。另一个隐私提醒是：摘要不保存原始名单，并不自动等于完整匿名或免除数据治理责任，输入哈希和系统日志仍需按实际风险管理。

可以把它想成不记下每位来客姓名，而是把来客映射到很多小格子，只记录每格里出现过的“罕见程度”，再估算总人数。HyperLogLog 用很小的记忆换取可控的统计误差，特别适合大规模流式去重。看懂这一点，就能分清它与精确位图、布隆过滤器等结构各自回答的是什么问题。

来源：Flajolet 等：HyperLogLog，2007