HyperLogLog

23rd January 2021 at 10:13pm
Algorithm: Statistical Data Structure

HyperLogLog 是一种概率数据结构(probabilistic data structure)和算法。用来统计大数据量下的去重元素个数,比如 UV(unique visitor)。

做了一个 幻灯片 来讲解:

电脑上如果 PDF 不展示或者展示不正常,使用 Chrome 并安装 PDF Viewer 插件。其他情况请下载文件查看:hyperloglog.pdf

Redis 的 HyperLogLog 最多占用 12kB 内存,是怎样计算出来的?

Redis 的 hash 值为 64 位,前 14 位作为桶(register),一共有 214 个桶。每个桶最多纪录 49 个 0,需要 6 位(26 为 64)来纪录。因此需要的存储空间为 214 × 6 / 8 = 12kB。