Redis数据结构——HyperLogLog

HyperLogLog布局用于统计基数,因为基数是不重复的,所以一个大的数据集,其基数会小很多,占用很少的空间.

HyperLogLog的尺度错误是1.04 / sqrt(m),其中“m”是使用的寄存器数.

Redis使用16384个寄存器,因此尺度错误为0.81％.

由于Redis实现中使用的散列函数具有64位输出,并且我们使用14位的散列输出来寻址16k寄存器,所以剩下50位,所以我们可以遇到的最长的零运行将适合一个6位寄存器.这便是为什么Redis HyperLogLog值仅对16k寄存器使用12k字节的原因.

由于使用了64位输出功能,对付我们可以计算的集合的基数没有实际的限制.此外值得注意的是,非常小的基数的误差往往很小.

命令前缀为“PF”,以纪念Philippe Flajolet,后半部分则比拟容易记住：PFadd-增加,PFcount-统计,PFmerge-合并.

hyperloglog示例以下：