1. 什么是基数计算
基数计算（cardinality counting）指的是统计一批数据中的不重复元素的个数，常见于计算独立用户数（UV）、维度的独立取值数等等。实现基数统计最直接的方法，就是采用集合（Set）这种数据结构，当一个元素从未出现过时，便在集合中增加一个元素；如果出现过，那么集合仍保持不变。
在大数据的场景中，实现基数统计往往去面临以下的两个问题：
如果有效的存储原始数据，以避免数据占用空间过多，这里就涉及到存储空间压缩的问题
如果能够跨不同的维度、不同的时间段实现基数计算，比如在计算日度UV的情况下，如果计算出周度、或者月度的UV
本文旨在介绍目前比较成熟的基数计算的方式，并通过实例对比他们在解决以上两个问题上的效果，最后引出本文的重点，HyperLogLog算法的实现和应用。
2. Bitmap 2.1 基本原理Bitmap进行基数计算的方法，是先定义一个bit数组，数组中的每一位对应数据的一种取值。由于bit是计算机中的最小单位，使用bit可以大量的减少存储空间。例如一个数组[1,3,4,5]，那么对应的bitmap即为[0,0,0,1,1,1,0,1]，后续每新增加一个元素，就和现有的bitmap进行OR操作，通过计算bitmap中1的个数，即可以得到基数计算的结果。
正是因为bitmap之间对OR也是良好支持的，两个bitmap在进行OR操作之后，便是这两个条件组合下的基数计算结果，因此使用bitmap是可以实现任意条件下的基数计算。
2.2 空间使用按照上面介绍的原理，进行bitmap的构建。假如统计1亿数据的基数值，大约需要内存100000000/8/1024/1024 ~= 12M，如果有100个这样的对象，就需要1.2G的内存空间，可见占用内存还是很大的，在实际业务中基本很少使用。
3. Linear Counting 3.1 基本原理Linear Counting是采用概率的方式进行基数估计的最简单的方法。下面通过一个实例描述Linear Counting的计算过程：
数据哈希：假设原始数据的基数为n，使用一组哈希空间为m的哈希函数H，将原始数据转换为满足均匀分组的一组哈希数组。
分桶数据统计：构建一个长度为m的bitmap，其中每一个bit对应哈希空间的一个值。生成哈希数组的值如果存在，则把相应的bit设置为1。当所有值设置完成后，统计bitmap中为0的bit数为u。
可以通过下述的公式计算基数估计的结果：
注意这里的log指的是自然对数。
其中最重要的是要清楚，在经过n次数据的哈希后，bitmap中的某个bit值为0，是一个伯努利事件。记住这一点再理解公式推导就容易多了。
3.2 空间使用Linear Counting的空间使用，和bitmap相比，空间复杂度是一致的，仅有线性下降。因此如果对于1亿的原始数据，仍然需要MB级别的内存空间存储。Linear Counting在实际应用中也很少被使用。
4. LogLog Counting 4.1 伯努利过程在介绍LogLog Counting之前，我们先来回顾一下伯努利过程的概念。
伯努利过程是一个由有限个或无限个的独立随机变量 X1, X2, X3 ,..., 所组成的离散时间随机过程，其中 X1, X2, X3 ,..., 满足如下条件：
对每个 i, Xi 等于 0 或 1; 对每个 i, Xi = 1 的概率等于 p. 换言之，伯努利过程是一列独立同分布的伯努利试验。每个Xi 的2个结果也被称为“成功”或“失败”。所以当用数字 0 或 1 来表示的时候，这个数字被称为第i个试验的成功次数。
举一个常见的例子：每次抛硬币之后，出现正面和反面的概率分别为1/2，如果不停地抛硬币，直至出现正面为止，这就是一个伯努利过程。
这样，我们假设一共进行了n次伯努利过程，出现正面的次数分别为k1, k2, ... kmax，那么有以下两个结论：
n次伯努利过程的投掷次数都不大于kmax
n次伯努利过程，至少有一次的投掷次数等于kmax
已知投掷k次才出现正面的概率为：1/2^k，那么：
第一种情况的概率为：
第二种情况的概率为：
如果n >> 2^k，则P(x >= kmax)为0；如果n << 2^k，则P(x <= kmax)为0。因此我们可以用2^k来作为n的近似估计结果。
4.2 伯努利过程与LogLog Counting