如何将基数计算，等价地认为是一个伯努利过程，是LogLog Counting的关键所在。这里我们可以把原始数据进行哈希，哈希后的数组是满足均匀分布的。把每个元素看做一个投掷硬币的过程，将元素转换为2进制之后，每个bit出现0和1的概率是相等的。从高位开始查，第一次出现1的位置记为k，即等同于投掷硬币时出现第一个正面，将所有元素出现1的位置的最大值，记为kmax，那么2^kmax就是基数计算的结果。
4.3 LogLog Counting计算过程数据哈希：这个和Linear Counting是类似的，都需要保证哈希后的数据是满足均匀分布的。
转换为2进制：将哈希后的每个元素，都转换为2进制，由于数据在哈希后满足均匀分布的，2进制数据每一个bit的0和1出现的概率都是1/2，这里设2进制数据的位数为L。
统计第一个1出现的位置：分别计算每个2进制数据，第一次出现1的次数。所有次数中的最大值为kmax，那么2^kmax就是最终结果。
下图中给出一个针对一个元素进行k值计算的过程。
上面的计算过程，由于是单一估计量，可能会出现一定的偶然性导致误差。因此这里引入数据分桶的方法。取哈希空间分成m个桶，用哈希值的前几个bit的值来决定数据属于哪一个桶，再对桶内的数据取k值，最终计算出kmax。再将所有桶的kmax取平均数，这样就通过多次估计取平均的方式，消除了单一估计可能存在的偶然性误差。计算公式如下：
4.5 误差修正和分析
以上的过程仍然是存在误差的，并不是无偏估计。将上述过程修正为无偏估计的过程由于过于复杂，这里就不再介绍了。需要了解的是，最终结果的误差公式为：
4.6 空间使用
到这里，我们就可以理解LogLog Counting中两个log了，它们的含义分别如下：
第一次log，和Linear Counting很类似，由于使用哈希，压缩了数据空间。
第二次log，由于在存储哈希值的第一次1出现的次数时，只需要存储结果k，而不需要存储原始的哈希值，进一步节省了空间。
加入哈希之后的值有32bit，那么每个桶需要5bit保存kmax的值，m个桶就是m5/8 B。
如果基数是1亿个（227），当分桶数为1024时，每个桶的基数上限为227 / 2^10 = 217，log(log(217))=4.09，那么每个桶需要5bit保存kmax，总共需要的空间为51024/8，等于640B，可见是非常小的。
通过概率计算可知，LogLog Counting由于使用了几何平均值，可能出现在基数较小的情况，有些桶是为空的。空桶对于最后平均值的计算干扰较大。
Adapative Counting的思想是将Linear Counting和LogLog Counting进行结合。Linear Counting和LogLog Counting的存储结构是类似的，仅仅是Linear Couting关心桶是否为空，而LogLog Counting需要桶中的kmax。
最终分析得到的结论是：在空桶率大于0.051时，使用Linear Counting的偏差率更小；在空桶率小于0.051时，使用LogLog Counting的偏差率更小。
6. HyperLogLog CountingHyperLogLog Counting，是在LogLog Counting的基础上，将桶之间计算采用的几何平均，修改为调和平均，可以有效的减少空桶对于平均值的影响。
调和平均的计算公式如下：
使用调和平均后的偏差公式为：
可见偏差期望和LogLog Counting相比要更小。
Linux公社的RSS地址：https://www.linuxidc.com/rssFeed.aspx