问题的背景是在大数据冲击下，很多数据指标（尤其是涉及到去重的）的计算无法在合理的空间和时间内完成，比如uv的计算，数学原型问题等价于持续的向一个集合中写数，重复的不记，要求最终给出集合中不重复的元素的个数（集合的势）。而比较暴力的做法是随着数字增多不断的扩展集合的大小，让它放下所有的数，最终数出这个个数就OK。显然这样的空间复杂度在单机下是做不到的，所以多数做法是利用分布式原理将uv数据隔离到不同的计算节点，每个计算节点自行维护一个类似这样的集合（wdm实时里的布隆过滤器），然后分而治之，最后merge为一份结果数据。
基数估计的初衷就是为了解决在大数据的前提下，如何以低成本的空间复杂度去计算超大集合的势的问题，换句话说，通过基数估计，单机做到计算亿级别uv，误差在4%以内。解决思路主要是概率估计，具体原理和做法参看 blog和论文原文。
出于实验的目的，我简单实现了暴力做法bruteforce-bf，布隆过滤器-bbf，loglog-llc和hyperloglog-hllc四个算法，比较一下基数估计这个计算去重指标的逻辑是否可行（llc非常离谱，可能是我分桶数没有调整好，就不贴出结果了）。
预处理方法：1-N生成随机uid，模拟N次（均匀分布），jvm启动-Xmx1024m。
实验结果：
附加说明一下，期望值如何计算：其实这个实验的数学原型就是一个长度为k的均匀分布的（1-N)的随机数列，求不重复的元素个数的期望。我实验里k=n，这是一种极端情况（实验设计纯为方便计算，如果k较大会导致计算超慢，uv5000w时根本无法计算出来，增大k理论上会提高精度，我实验过的一组数据是100w uv 500wpv时 hllc的值是991234，误差<1%），理论上k相当于pv，在递推公式中k趋于无穷时期望等于n。
这个递推的计算可以通过组合分析推导，推导方法不详说了（当然我有可能推导错了~~数学功底 实在 不行了），通项公式见matlab代码。
syms e n;
e = n-(1/n)*((1-2*n+n*n)*((n-1)/n)^(n-2)+(1-n)*n+n*(n-1));
vpa(subs(e,'n',1000000),10)
另外，我个人认为分布式布隆过滤器的方案是非常好的，因为空间和时间都比较均衡，且精确度高，基数估计的方法本质上空间复杂度O(1)，时间复杂度代码高效一点也可以非常快，但是缺点是精确度稍微欠缺，且不易分布式计算（因为它天生适合单进程，llc分桶均衡也是单进程做比较好，分布式完全是牛刀杀鸡）。
ref blog: http://blog.codinglabs.org/articles/cardinality-estimate-exper.html#ref4
算法实现的java代码可见github： https://github.com/changedi/card-estimate