Hyperloglog

已发布 2017-12-12 23:24:12

Redis 里有 HyperLogLog 数据结构,一直看不懂是什么意思,其实原理很简单。

在理想状态下,将一堆数据hash至[0,1],如果是随机均匀分布的话,每两点距离相等,测算出这个距离,那么 1/间距 就是这堆数据的基数,也就是数据的个数。

然而这个数据需要修正,太小或太大都是通过一个log函数来得到新的估计值。

计算过程:

  1. hash成32位的值
  2. 初始化m个登记表
  3. 存储每组最大的 leading-zeros 个数
  4. 计算基数并做调整。

这里有一个模拟页面,动态模拟这个估算过程。

原始信息通过hash函数变小之后,在加上是存储到每个“桶”里,使得存储空间变得很小。

References

comments powered by Disqus