本文参考：
陶加涛 https://www.infoq.cn/article/j3b2Eoz_V7Wzm27odwXX
算法简介
是一种近似去重算法，能够使用极少的存储空间给出一个数据流中不重复元素的个数
HLL 算法需要完整遍历所有元素一次，而非多次或采样；
该算法只能计算集合中有多少个不重复的元素，不能给出每个元素的出现次数或是判断一个元素是否之前出现过；
多个使用 HLL 统计出的基数值可以融合。
在牺牲一定准确性的前提下，存储空间可以被大量节省
| 算法 | 存储空间(10^6) | 误差 |
|---|---|---|
| Bitmap | 120KB | 0% |
| HLL(10) | 1KB | 9.75% |
| HLL(12) | 4KB | 4.88% |
| HLL(14) | 16KB | 2.44% |
| HLL(16) | 64KB | 1.22% |
空间复杂度：Bitmap（O(N)），HLL（O(log2log2N)）
HLL 算法有着非常优异的空间复杂度，可以看到它的空间占用随着基数值的增长并没有变化。
HLL 后面不同的数字代表着不同的精度，数字越大，精度越高，占用的空间也越大，可以认为 HLL 的空间占用只和精度成正相关。
算法的原理简介
举一个生活中的例子来帮助大家理解 HLL 算法的原理：
比如你在进行一个实验，内容是不停地抛硬币，出现正反面的概率都是1/2，记录你连续抛到正面的次数K，
这种抛硬币多次直到出现正面的过程记为一次伯努利过程，对于n次伯努利过程，我们会得到n个出现正面的投掷次数值K1,K2,K3…Kn，其中最大值记为Kmax，
那么可以得到下面结论：
- n次伯努利过程的投掷次数都不大于Kmax
- n次伯努利过程，至少有一次投掷次数等于Kmax
以上结论可以总结为：进行了n次进行抛硬币实验，每次分别记录下第一次抛到正面的抛掷次数K，那么可以用n次实验中最大的抛掷次数Kmax来预估实验组数量n：
n = 2^Kmax
如果你最多连抛正面记录是 3 次，那可以想象你并没有做这个实验太多次，如果你最长连抛正面记录是 20 次，那你可能进行了这个实验上千次。
一种理论上存在的情况是，你非常幸运，第一次进行这个实验就连抛了 20 次正面，我们也会认为你进行了很多次这个实验才得到了这个记录，这就会导致错误预估；
改进的方式是请 10 位同学进行这项实验，这样就可以观察到更多的样本数据，降低出现上述情况的概率。这就是 HLL 算法的核心思想。
算法具体实现
- 用一个哈希函数，对数据流中的每一个元素求出哈希值
如果使用long来存储哈希值，则该哈希函数需要把2^64个不同的值映射到 0 ~ 2^64 -1 上
对于每个哈希值，取最后p位来决定桶的序号
在剩下的(64 - p)位中找到第一个1出现的位置，如果大于桶中现有的值，则更新
所有元素处理完毕后，求所有桶中值的调和平均数
调和平均数是将所有的数值取倒数并求其算术平均数之后，再将次算术平均数取倒数而得
- 乘以m得到最后的结果E
HLL 会通过一个 hash 函数来求出集合中所有元素的 hash 值（二进制表示的 hash 值，就可以理解为一串抛硬币正反面结果的序列），得到一个 hash 值的集合，然后找出该 hash 值集合中，第一个 1 出现的最晚的位置。
例如有集合为 [010, 100, 001], 集合中元素的第一个 1 出现的位置分别为 2, 1, 3，可以得到里面最大值为 3，故该集合中第一个 1 出现的最晚的位置为 3。
因为每个位置上出现 1 的概率都是 1/2，所以我们可以做一个简单的推断，该集合中有 8 个不重复的元素。
可以看到这种简单推断计算出来集合的基数值是有较大的偏差的，那如何来减少偏差呢？
正如我上面的例子里说的一样，HLL 通过多次的进行试验来减少误差。那它是如何进行多次的实验的呢？
这里 HLL 使用了分桶的思想，上文中我们一直有提到一个精度的概念，比如说 HLL(10)，这个 10 代表的就是取该元素对应 Hash 值二进制的后 10 位，
计算出记录对应的桶，桶中会记录一个数字，代表对应到该桶的 hash 值的第一个 1 出现的最晚的位置。
例如哈希值：0000010010111010111100 0000001001
该 hash 值的后 10 位的 hash 值是 0000001001，转成 10 进制是 9，对应第 9 号桶，而该 hash 值第一个 1 出现的位置是第 6 位，如果比原先 9 号桶中的数字大，那么把 9 号桶中的数字更新为 6。
可以看到桶的个数越多，HLL 算法的精度就越高，HLL(10) 有 1024(2^10) 个桶，HLL(16) 有 65536(2^16) 个桶。
同样的，桶的个数越多，所占用的空间也会越大。
HLL 的误差分布服从正态分布，它的空间复杂度: O(m log2log2N), Ｎ 为基数, m 为桶个数。
这边给大家推导一下它的空间复杂度，我有 264 个的不重复元素 (Long. MAX_VALUE)，表达为二进制一个数是 64 位，这是第一重 log2, 那么第一个 1 最晚可能出现在第 64 位。
64 需要 6 个 bit (26=64) 就可以存储，这是第二重 log2。如果精度为 10，则会有 1024 个桶，所以最外面还要乘以桶的个数。
由于需要完整的遍历元素一遍，所以它的时间复杂度是一个线性的时间复杂度
Redis实现了HyperLogLog
