Redis源码中hyperloglog结构的实现原理是啥( 八 )
参考文献：Count-distinct Problem 的维基百科：https://en.wikipedia.org/wiki/Count-distinct_problemHeule, Stefan, Marc Nunkesser, and Alexander Hall. "HyperLogLog in practice: algorithmic engineering of a state of the art cardinality estimation algorithm." Proceedings of the 16th International Conference on Extending Database Technology. 2013.Flajolet, Philippe, et al. "Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm." 2007.HyperLogLog 的 demo 网站：http://content.research.neustar.biz
■网友
具体可以看一下这篇文章
用户日活月活怎么统计 - Redis HyperLogLog 详解基本原理
HyperLogLog 是一种概率数据结构，它使用概率算法来统计集合的近似基数。而它算法的最本源则是伯努利过程。
伯努利过程就是一个抛硬币实验的过程。抛一枚正常硬币，落地可能是正面，也可能是反面，二者的概率都是 1/2 。伯努利过程就是一直抛硬币，直到落地时出现正面位置，并记录下抛掷次数k。比如说，抛一次硬币就出现正面了，此时 k 为 1; 第一次抛硬币是反面，则继续抛，直到第三次才出现正面，此时 k 为 3。
对于 n 次伯努利过程，我们会得到 n 个出现正面的投掷次数值 $ k1, k2 ... kn $, 其中这里的最大值是kmax。
根据一顿数学推导，我们可以得出一个结论： $2^{k_ max}$ 来作为n的估计值。也就是说你可以根据最大投掷次数近似的推算出进行了几次伯努利过程。
下面，我们就来讲解一下 HyperLogLog 是如何模拟伯努利过程，并最终统计集合基数的。
HyperLogLog 在添加元素时，会通过Hash函数，将元素转为64位比特串，例如输入5，便转为101(省略前面的0，下同)。这些比特串就类似于一次抛硬币的伯努利过程。比特串中，0 代表了抛硬币落地是反面，1 代表抛硬币落地是正面，如果一个数据最终被转化了 10010000，那么从低位往高位看，我们可以认为，这串比特串可以代表一次伯努利过程，首次出现 1 的位数为5，就是抛了5次才出现正面。
所以 HyperLogLog 的基本思想是利用集合中数字的比特串第一个 1 出现位置的最大值来预估整体基数，但是这种预估方法存在较大误差，为了改善误差情况，HyperLogLog中引入分桶平均的概念，计算 m 个桶的调和平均值。
Redis 中 HyperLogLog 一共分了 2^14 个桶，也就是 16384 个桶。每个桶中是一个 6 bit 的数组，如下图所示。
HyperLogLog 将上文所说的 64 位比特串的低 14 位单独拿出，它的值就对应桶的序号，然后将剩下 50 位中第一次出现 1 的位置值设置到桶中。50位中出现1的位置值最大为50，所以每个桶中的 6 位数组正好可以表示该值。
在设置前，要设置进桶的值是否大于桶中的旧值，如果大于才进行设置，否则不进行设置。示例如下图所示。 
此时为了性能考虑，是不会去统计当前的基数的，而是将 HyperLogLog 头的 card 属性中的标志位置为 1，表示下次进行 pfcount 操作的时候，当前的缓存值已经失效了，需要重新统计缓存值。在后面 pfcount 流程的时候，发现这个标记为失效，就会去重新统计新的基数，放入基数缓存。
推荐阅读
- microsoft redistributable为啥不做成一个带可选项的程序
- 网站完整源码能有途径获取吗
- cygwin下源码编译openssl出错
- redis中的hset怎样快速地找到最大key或最大value，有办法快速地知道一个hset中key的个数 或 value的个数吗
- 怎样借助 redis 进行内容的排序，并将关注的 feed 流推送进来，聚合在一起，显示出来
- 有关JDK源码中一些元素类型在方法实现方面的效率问题请大牛们指点迷津一下，谢谢！?
- wordpress首页文章摘要字数设置具体源码在文中！求大神！
- 开发一个网站的价格，做一个网站要多少钱，需要源码的呢
- 写一个类，让toString()输出这个类的源码
- 如果让一个程序随机的修改自己源码无限制的编译且复制自身，是否有一日会出现一个完善的人工智能