# hyperloglog
# 介绍
一天内有多少用户访问了我的主页，类似这种要去重计数的功能是非常常见的需求，在redis中提供了HyperLogLog的数据结构来支持这类去重计数需求。
命令
pfadd key element 向key的计数中加入一个元素
pfcount key查看元素去重计数
优点: 空间少，单个计数key只使用12kB，O(1)时间复杂度 缺点：有一定0.81%的误差，不能判断是否在集合中。
操作时间复杂度，pfadd每个element O(1)，redis单机qps 11w左右，pipeline 100 batch 100w qps左右。
# 数据结构
对传入的key进行hash。用hash左边的14bit选择要用的bucket。 后边50bit统计从最右向左最多有多少个连续的0，如果比当前bucket中的数值大，记录到对应的bucket中，每个bucket只需要6bit（2的6次方>50)
统计总的次数时，通过各个桶中的数值通过公式得出结果。
所以hyperloglog每个key只需要 16384 * 6 / 8 = 12KB。
hyperloglog利用概率方式，通过连续0的bit数量，预估出计数的次数（重复element计数不会对最大连续0bit造成影响）。 不同元素的计数数量越多，连续为0的数量就越大。并且为了避免个别数据case的影响，使用了16384个分桶，来分别计数。
# 其他方案
- bitmap，可以用于记录long类型数据，比如用户id，一亿数据约100MB，可以通过区间分片等方式横向扩容。
- string，适用于更通用的数据去重计数，单独找一个去重缓存和计数缓存，内存使用量比较大，适用于数据量不大的场景。