HyperLogLog算法初探

业务有一次用了 redis 的 HyperLogLog 接口计算个数，后来发现踩坑了，这个接口的结果是一个估算值！看了下，这个算法还是很牛逼的，只用12K的存储空间就可以估算几亿量级的数据，很适合大数据领域。最常用的场景应该就是“统计一段时间的UV”。
假设有1亿个不重复的 IP，每个IP用一个 bit 表示，那么准确存储的话，大概需要 10**8/8/1000/1000 = 12M 的空间，而使用上面的估算模型，只需要千分之一的空间！（误差大概有 3%）

基本原理大概有两个核心点：

• 概率模型
• 分桶平均

以 redis 估算一亿个 IP 为例：

• 取一个 IP
• redis 生成一个 14 bit的统计数组 m，大小为 2**14=16384
• 对 IP 进行 hash，生成 64 bit 数组 a
• a 的前 14 bit 会映射到 m 的一个位置，剩下 50 bit 记录第一个1出现的位置，最大位置为50，需要 log_2{50}=6 bit
• 重复以上步骤

通过概率模型进行局部估算，以及分桶平均可以取得较好的效果。实际需要的存储空间为：
6*16384/8/1000=12K

具体算法细节就不探讨了，比较深奥~~
这里有一个动画模型可以参考