1. 背景
基数（cardinality）统计，即求一个集合中，不重复的元素个数。例如集合{1,1,2,3,4}的基数是4。
在互联网中，典型的应用场景就是uv统计，下面就用uv统计作为例子去阐述。
对于uv统计，最简单的做法，是对被统计项，维护一个set去重，但这样做会有两个问题：
- 如果uv统计上限很高，那么这个set的空间开销就很大
- 如果被统计项有很多个，例如对于每一样商品，都要统计uv，那么空间开销巨大
针对这种情况，我们可以用允许一点误差，用概率统计的方法，将空间消耗极大降低
这里的set也能用BloomFilter去做，有误差但开销也比一般的用要小很多。
2. 思路和原理
2.1 去重
首先，这里的关键问题尽量降低代价的去重。显然，可以用哈希，hash(user_id)就把string变成整数，每个user_id都能唯一确定一个整数（看你有冲突），这样就去重来。然后再看看怎么统计。
2.2 统计
既然是基于概率的统计方法。
我们想想抛硬币，反面记0，正面记1，正反面的概率都是1/2。第一次出现正面的位置记为ρ(x)，那么ρ(0001)=3，0001出现的概率是1/23=1/16。换句话讲，就是进行16次实验，很可能出现一次或以上0001。再换句话讲，进行n轮实验，最大ρ(x)为y，那么可以估算进行出n=2y。
然后，我们只要把要去重的key，转换成一串01字符串，就能套用上面的统计方法了。
记hash函数的最大值为2L，把hash(key)看成长度为L的01串，换句话说，hash(key)就是进行L次抛硬币，并且每次只要key相同，抛硬币的结果就相同（去重了），然后从左到右找第一个1的位置就ok了。例如：
有三个key，相当于进行三次试验
hash(key1) = 01010110，ρ(01010110) = 2
hash(key2) = 01110010，ρ(01110010) = 2
hash(key3) = 00100110，ρ(00100110) = 3
最大值是3，所以根据概率看，有23=8次。可以看到，在数据量小时，误差会比较大，而且根据这个算法，统计出来的数字只会是2的次幂，虽然这样，但是基本思想已经掌握，接下来的就是优化了。
2.3 优化
2.3.1 分桶(log counting算法)
直接用最大的ρ(x)，受随机事件的影响很大，例如如果前几次就来一个0000000000000001。有一个方法，可以降低这种影响，就是分桶取平均数，例如分4个桶，取前两位作为桶的标志，
hash(key1) = 01010110，ρ(01010110) = 2，bucket 01
hash(key2) = 01110010，ρ(01110010) = 0，bucket 01
hash(key3) = 00000011，ρ(00000011) = 5，bucket 00
| bucket | max ρ |
|---|---|
| bucket 00 | 5 |
| bucket 01 | 2 |
| bucket 10 | 0 |
| bucket 11 | 0 |
| bucket avg | (5+2)/4,向上取整得2 |
所以估算值为22=4，这样影响就比较小了
2.3.2 调和平均数
但是如果遇到更极端的随机事件，例如hash函数最大是232，去到最后一位，对分桶取算数平均数的影响还是很大的，怎么办呢？数学上有个叫调和平均数的东西，我们用调和平均数取代算数平均数即可。
2.4 合并
多个HLL取并集，很简单，就是对比相同位置上的bucket，只保留最大的bucket。
2.5 最终公式与误差
const常数的选择
// 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;
}
在刚开始样本比较少的时候，用上面的算法还是容易偏大，这时可以用下面的方法估算：
（DV代表估计的基数值，m代表桶的数量，V代表结果为0的桶的数目，log表示自然对数）
if DV < (5 / 2) * m:
DV = m * log(m/V)
