项目在统计UV/PV时用到了Druid的Hyper hyperunique算法，书上介绍这种算法求出的UV/PV存在一定误差，因此需要了解下误差来自哪里。
实现去重功能，最简单的就是使用set记录集合本身，缺点与前面Bloom Filter差不多，显而易见，需要大量内存空间。HyperLogLog为解决这个问题而生。
另外redis也实现了HyperLogLog的结构，所以可以从redis源码上分析下其实现。
1。基数计数
基数是指一个集合中不同元素的个数。假设有一组数据{1， 2， 3， 3， 4， 5}，除去重复的数字之后，该组数据中不同的数有5个，则该组数据的基数为5。
那什么是基数统计呢？基数统计是指在误差允许的情况下估算出一组数据的基数。
2。伯努利过程
投掷一次硬币出现正、反两面的概率均为1/2。如果我们不断的投掷硬币，直到出现一次正面，在这样的一个过程中，投掷一次得到正面的概率为1/2，投掷两次才得到正面的概率为1/2^2….依次类推，投掷k次才得到一次正面的概率为1/2^k。这个过程在统计学上称为伯努利问题。
思考下面两个问题：
进行n次伯努利过程，所有投掷次数都小于k的概率
进行n次伯努利过程，所有投掷次数都大于k的概率
针对第一个问题，在一次伯努利过程中，投掷次数大于k的概率为1/2^k，也就是投了k次反面的概率。因此，在一次过程中投掷次数不大于k的概率为1-1/2^k。因此n次伯努利过程所有投掷次数都不大于k的概率为
很显然，第二个问题，n次伯努利过程，所有投掷次数都不小于k的概率为
从上述公式中可得出结论：当n远小于2^k时，P(x>=k)几乎为0，即所有投掷次数都小于k；当n远大于2^k时，P(x <= k)几乎为0，即所有投掷次数都大于k。因此，当x=k的情况下，我们可以把2^k当成n的一个粗糙估计。
3。基数统计和HyperLogLog算法
将上述伯努利过程转换到比特位串上，假设我们有8位比特位串，每一位上出现0或者1的概率均为1/2，投掷k次才得到一次正面的过程可以理解为第k位上出现第一个1的过程。
那么针对一个数据集来说，我们用某种变换将其转换成一个比特子串，就可以根据上述理论来估算出该数据集的技术。例如数据集转换成00001111，第一次出现1的位置为4，那么该数据集的基数为16。
于是现在的问题就是如何将数据集转换成一个比特位串？很明显，哈希变换可以帮助我们解决这个问题。
选取一个哈希函数，该函数满足一下条件：
具有很好的均匀性，无论原始数据集分布如何，其哈希值几乎服从均匀分布。这就保证了伯努利过程中的概率均为1/2
碰撞几乎忽略不计，也就是说，对于不同的原始值，其哈希结果相同的概率几乎为0
哈希得出的结果比特位数是固定的。
有了以上这些条件，就可以保证“伯努利过程”的随机性和均匀分布了。
接下来，对于某个数据集，其基数为n，将其中的每一个元素都进行上述的哈希变换，这样就得到了一组固定长度的比特位串，设f(i)为第i个元素比特位上第一次出现”1“的位置，简单的取其最大值f_max为f(i)的最大值，这样，我们就可以得出以下结论：
当n远小于2^f_max时，f_max为当前值的概率为0
当n远大于2^f_max时，f_max为当前值的概率为0
这样一来，我们就可以将f_max作为n的一个粗糙估计。当然，在实际应用中，由于数据存在偶然性，会导致估计量误差较大，这时候需要采用分组估计来消除误差，并且进行偏差修正。
所谓分组估计就是，每一个数据进行hash之后存放在不同的桶中，然后计算每一个桶的f_max，最后对这些值求一个平均f_avg，即可得到基数的粗糙估计2^f_avg。
实际实现中，分组估计也不能很好的解决误差问题，还需要额外的偏差修正工作。
http://algo.inria.fr/flajolet/Publications/DuFl03-LNCS.pdf
4。Redis实现
对于输入，计算64位hash
hash最右14bit来进行分桶，桶的个数是2 ^14=16384个
统计hash左侧50bit，第一次1出现的位置（用bit存储需要6bit：2^6 = 64 > 50）
与对应桶的6bit值比较，若大于原来值，则更新之
redis HyperLogLog内存占用：6（存储第一次出现位置） * 16384（桶个数） / 8 （1byte = 8bit）/ 1024(bytes) = 12K
因此redis使用12K固定大小内存即可完成对一个Key的Unique统计，空间效率极高。