1.基数计数cardinality counting
基数计数通常用来统计一个集合中不重复的元素个数。要实现基数计数，最简单的做法是记录集合中所有不重复的元素集合S，当新来一个元素x，若S中不包含元素x，则将x加入S，否则不加入，计数值就是S的元素数量。但这种做法存在两个问题：
- 当统计的数据量变大时，相应的存储内存也会线性增长
- 当集合S变大，判断其是否包含新加入元素x的成本变大
你一定想到了HashMap，完美适用这个问题。但是大数据场景下，基数计数的性能与内存消耗是一个值得关注的事情，HashMap的内存占用太多了。另外，有时候的计数还需要一些整合，例如统计了某三天的访问量，还需要知道这三天的总共访问量为多少。
2.几种常见的方法
1.B-Tree
B树最大的优势是插入和查找效率很高，如果用B树存储要统计的数据，可以快速判断新来的数据是否已经存在，并快速将元素插入B树。要计算基数值，只需要计算B树的节点个数。 将B树结构维护到内存中，可以快速统计和计算，但依然存在问题，B树结构只是加快了查找和插入效率，并没有节省存储内存。
2.BitMap
通过一个bit数组来存储特定数据的一种数据结构，每一个bit位独立包含信息，bit是数据的最小存储单位，因此能大量节省空间。新加入一个元素，只需要将已有的bit数组和新加入的数字做按位或 (or)(or)计算。bitmap中1的数量就是集合的基数值。
一个很明显的优势是可以轻松合并多个统计结果，只需要对多个结果求异或就可以。bitmap对于内存的节约量是显而易见的，但还是不够。如果用32bit的int代表每个统计数据，保存1亿数据大约需要内存32*100000000/8/1024/1024 ≈ 381M。
3.概率算法
在大数据场景下，如果对数据的精确度要求没有那么高，可以考虑采用此方法。概率算法不直接存储数据集合本身，通过一定的概率统计方法预估基数值，这种方法可以大大节省内存，同时保证误差控制在一定范围内。
目前用于基数计数的概率算法包括:
- Linear Counting(LC)：早期的基数估计算法，LC在空间复杂度方面并不算优秀，实际上LC的空间复杂度与上文中简单bitmap方法是一样的（但是有个常数项级别的降低），都是O(N_max)；
- LogLog Counting(LLC)：LogLog Counting相比于LC更加节省内存，空间复杂度只有O(log2(log2(N_max)))
- HyperLogLog Counting(HLL)：HyperLogLog Counting是基于LLC的优化和改进，在同样空间复杂度情况下，能够比LLC的基数估计误差更小。
3.HyperLogLog算法详解
redis中实现的HyperLogLog，只需要12K内存，在标准误差0.81%的前提下，能够统计2^64个数据。下面我们重点解释一下这绝妙的算法。
1.伯努利试验
解释HLL算法之前，我们来认识一下伯努利试验，其起源就是“抛硬币”。
众所周知，抛硬币次数足够多时，获得正面与反面的概率都是50%。假设一直抛硬币，直到它出现正面为止，我们记录为一次完整的试验。可能抛了一次就出现了正面，也可能抛了4次才出现正面。无论抛了多少次，只要出现了正面，就记录为一次试验。这就是伯努利试验。
假设进行了n次伯努利试验，每次伯努利试验所经历了的抛掷次数为k。第一次伯努利试验，次数设为k1，以此类推，第n次对应的是kn。
其中，对于这n次伯努利试验中，必然会有一个最大的抛掷次数，例如最多抛了12次才出现正面，那么称这个为k_max，代表抛了最多的次数。
伯努利试验容易得出有以下结论：
- n 次伯努利过程的投掷次数都不大于 k_max。
- n 次伯努利过程，至少有一次投掷次数等于 k_max
最终结合极大似然估算的方法，发现在n和k_max中存在估算关联：n = 2^k_max 。显然，在试验次数不够多时，这个等式是不成立的。
2.估算的优化
虽然提升实验次数，能够降低该估算的误差率，但是这显然不够，所以我们引入了多轮试验的概念。
假设进行了m轮试验，取其k_max的平均数，即sum(k_max)/m。则可以得出以下公式，这也是LogLog算法的公式：
上面公式的DVLL对应的就是n，constant是修正因子，它的具体值是不定的，可以根据实际情况而设置。m代表的是试验的轮数。头上有一横的R就是平均数：(k_max_1 + ... + k_max_m)/m。
而HyperLogLog与LogLog算法的区别就是，将算数平均数换成了调和平均数。调和平均数的有点是不容易受极大值的影响。可以得到以下公式：
3.与计数问题的关联
伯努利实验的等式表明，在已知k_max的情况下可以估算出试验次数n。
基数计数的本质也是，通过记录一些信息从而估算出总量。那么关键就是，如何抽象出k_max的含义与记录它。
假设我们现在需要计数的问题是，统计一个web页面的访问次数。
1.二进制表示
将数字转换成二进制表示。其中0 代表了反面，1 代表了正面。
如果一个数据最终被转化成了 10010000，这就是一次抛硬币过程的实验结果，那么从右往左，从低位往高位看，我们可以认为，首次出现 1 的时候，就是伯努利实验结束的位置。
2.对应
假设每个用户有一个唯一id，我们可以取其的hash值转换为二进制。我们可以统计其首次1出现的位置，假设出现在第三位，则此轮试验的k就是3，我们将3存下来作为当前的k_max。此后每次有用户访问都可以更新此值，在足够多的用户访问后，我们就可以根据k_max来预估访问量。
但是这样的过程，手上只维护了一个k_max，也就是说对应着一轮伯努利试验。如果将其拆成多轮伯努利试验，从而能够降低误差率呢？
3.改进与分桶
很简单，只需要将ID拆成两部分，一部分表示轮次，一部分表示试验即可。分轮也就是分桶，回忆一下bucket sort，这里桶是类似的含义。
假设我们有一个用户ID转成二进制后为1001011000011。我们约定二进制的低两位用来计算桶，则此用户处于第3个桶，即象征伯努利的第3轮试验。计算出桶号后，剩下的比特串是：10010110000，第一次出现1在第五位，所以第三轮试验的k_max为5，记录至第三个桶中。
按照上面的流程，多个不同的用户 id，就被分散到不同的桶中去了，且每个桶有其 k_max。估算时将每个桶中的k_max取出来带入公式，即可实现HLL算法。
4.Redis中的应用
Redis中实现了HLL作为计数算法，最主要的命令为pfadd与pfcount。
Redis中设有 16384 (2^14)个桶，每个桶有6bit。每个数会被hash成 64 位，前14位用来分桶，正好分散到所有桶中。后50位中，即使第一次1出现在最高位，即50，6bit最大能表示63，也可以容纳下。
具体实现规则和上述描述一致，所以一共有2^64个数，只需要16384*6/8/1024K的空间就可以计数了。
误差说明：官方描述基数估计的结果是一个带有 0.81% 标准错误（standard error）的近似值。是可接受的范围
不过Redis具体实现的时候有一些优化：
1.pfadd命令并不会一次性分配12k内存，而是随着基数的增加而逐渐增加内存分配；而pfmerge操作则会将sourcekey合并后存储在12k大小的key中，这由hyperloglog合并操作的原理（两个hyperloglog合并时需要单独比较每个桶的值）可以很容易理解。
2.Redis 对 HyperLogLog 的存储进行了优化，在计数比较小时，它的存储空间采用稀疏矩阵存储，空间占用很小，仅仅在计数慢慢变大，稀疏矩阵占用空间渐渐超过了阈值时才会一次性转变成稠密矩阵，会占用12k的空间。
具体的源码分析可以参考此博客：走近源码：神奇的HyperLogLog
5.偏差修正
之前的描述中一直忽略了公式中那个constant。他不是一个常量，会随着情况改变。通过数分可以修成无偏估计。具体数学分析参见此论文：Loglog Counting of Large Cardinalities。
结论如下：
假设m为分桶数，p是m的以2为底的对数。
switch (p) {
case 4: constant = 0.673 * m * m;
case 5: constant = 0.697 * m * m;
case 6: constant = 0.709 * m * m;
default: constant = (0.7213 / (1 + 1.079 / m)) * m * m;
}
