2. hyperLogLog
如果要实现这么一个功能：
统计 APP或网页 的一个页面，每天有多少用户点击进入的次数。同一个用户的反复点击进入记为 1 次。
聪明的你可能会马上想到，用 HashMap 这种数据结构就可以了，也满足了去重。的确，这是一种解决方法，除此之外还有其它的解决方案。
问题虽不难，但当参与问题中的变量达到一定数量级的时候，再简单的问题都会变成一个难题。假设 APP 中日活用户达到百万或千万以上级别的话，我们采用 HashMap 的做法，就会导致程序中占用大量的内存。
我们下面尝试估算下 HashMap 的在应对上述问题时候的内存占用。假设定义HashMap 中 Key 为 string 类型，value 为 bool。key 对应用户的Id,value是是否点击进入。明显地，当百万不同用户访问的时候。此HashMap 的内存占用空间为：100万 * (string + bool)。
可以说，在上述问题目前现有的解决方案中，HashMap 是内存占用量最多的一种。如果统计量不多，那么可以使用这种方法解决问题，实现起来也简单。
除此之外还有B+ 树，Bitmap 位图，以及该文章主要介绍的 HyperLogLog算法解决方案。
在一定条件允许下，如果允许统计在巨量数据面前的误差率在可接受的范围内，1000万浏览量允许最终统计出少了一两万这样子，那么就可以采用HyperLogLog算法来解决上面的计数类似问题。
HyperLogLog 只需要12K内存就能统计2^64个数据。虽然计数存在一定的误差，但是误差率整体较低。标准误差为 0.81% 。
2.1 相关命令
-
PFADD
PFADD key element [element ...]
将ele添加进hll的基数计算中。流程：
先对ele求hash（使用的是一种叫做MurMurHash的算法）
将hash的低14位(因为总共有2的14次方个桶)作为桶的编号，选桶，记桶中当前的值为count
从的hash的第15位开始数0，假设从第15位开始有n个连续的0（即前导0）
如果n大于count，则把选中的桶的值置为n，否则不变
-
PFCOUNT
PFCOUNT key [key ...]
当参数为一个key时,返回存储在HyperLogLog结构体的该变量的近似基数，如果该变量不存在,则返回0.
当参数为多个key时，返回这些HyperLogLog并集的近似基数，这个值是将所给定的所有key的HyperLoglog结构合并到一个临时的HyperLogLog结构中计算而得到的。
-
PFMERGE
PFMERGE destkey sourcekey [sourcekey ...]
将多个 HyperLogLog 合并（merge）为一个 HyperLogLog ，合并后的 HyperLogLog 的基数接近于所有输入 HyperLogLog 的可见集合（observed set）的并集。
合并得出的 HyperLogLog 会被储存在目标变量（第一个参数）里面，如果该键并不存在，那么命令在执行之前，会先为该键创建一个空的。
