HyperLogLog

“HyperLogLog”

HyperLogLog

HyperLogLog，下面简称为HLL，它是 LogLog 算法的升级版，作用是能够提供不精确的去重计数。

127.0.0.1:6379> PFADD  language  "PHP" "Python" "Perl" "Ruby"
(integer) 1

127.0.0.1:6379> PFCOUNT  language
(integer) 4

127.0.0.1:6379> PFADD  language  "PHP"    # Redis 已经存在，不必对估计数量进行更新
(integer) 0

127.0.0.1:6379> PFCOUNT  language    # 元素估计数量没有变化
(integer) 4

127.0.0.1:6379> PFADD  language "JAVA"    # 添加一个不存在的元素
(integer) 1

127.0.0.1:6379> PFCOUNT  language    # 估计数量增一
5

https://juejin.cn/post/6844903785744056333
https://www.cnblogs.com/wmyskxz/p/12396393.html http://content.research.neustar.biz/blog/hll.html

存在以下的特点:

代码实现较难。能够使用极少的内存来统计巨量的数据，在 Redis 中实现的 HyperLogLog，只需要12K内存就能统计2^64个数据。计数存在一定的误差，误差率整体较低。标准误差为 0.81% 。误差可以被设置辅助计算因子进行降低。

稍微对编程中的基础数据类型内存占用有了解的同学，应该会对其只需要12K内存就能统计2^64个数据而感到惊讶。为什么这样说呢，下面我们举下例子: 取 Java 语言来说，一般long占用8字节，而一字节有8位，即: 1 byte = 8 bit，即long数据类型最大可以表示的数是: 2^63-1。对应上面的2^64个数，假设此时有2^63-1这么多个数，从 0 ~ 2^63-1，按照long以及1k = 1024字节的规则来计算内存总数，就是: ((2^63-1) * 8/1024)K，这是很庞大的一个数，存储空间远远超过12K。而 HyperLogLog 却可以用 12K 就能统计完。伯努利试验在认识为什么HyperLogLog能够使用极少的内存来统计巨量的数据之前，要先认识下伯努利试验。

伯努利试验是数学概率论中的一部分内容，它的典故来源于抛硬币。

硬币拥有正反两面，一次的上抛至落下，最终出现正反面的概率都是50%。假设一直抛硬币，直到它出现正面为止，我们记录为一次完整的试验，间中可能抛了一次就出现了正面，也可能抛了4次才出现正面。无论抛了多少次，只要出现了正面，就记录为一次试验。这个试验就是伯努利试验。那么对于多次的伯努利试验，假设这个多次为n次。就意味着出现了n次的正面。假设每次伯努利试验所经历了的抛掷次数为k。第一次伯努利试验，次数设为k1，以此类推，第n次对应的是kn。其中，对于这n次伯努利试验中，必然会有一个最大的抛掷次数k，例如抛了12次才出现正面，那么称这个为k_max，代表抛了最多的次数。伯努利试验容易得出有以下结论:

n 次伯努利过程的投掷次数都不大于 k_max。 n 次伯努利过程，至少有一次投掷次数等于 k_max

最终结合极大似然估算的方法，发现在n和k_max中存在估算关联: n = 2^(k_max) 。这种通过局部信息预估整体数据流特性的方法似乎有些超出我们的基本认知，需要用概率和统计的方法才能推导和验证这种关联关系。例如下面的样子: 第一次试验: 抛了3次才出现正面，此时 k=3，n=1 第二次试验: 抛了2次才出现正面，此时 k=2，n=2 第三次试验: 抛了6次才出现正面，此时 k=6，n=3 第n 次试验: 抛了12次才出现正面，此时我们估算， n = 2^12 复制代码假设上面例子中实验组数共3组，那么 k_max = 6，最终 n=3，我们放进估算公式中去，明显: 3 ≠ 2^6 。也即是说，当试验次数很小的时候，这种估算方法的误差是很大的。

作者: 林冠宏_指尖下的幽灵链接: https://juejin.cn/post/6844903785744056333 来源: 掘金著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Contents

“HyperLogLog”

HyperLogLog

存在以下的特点: