要想了解HyperLogLog ，必须先要了解伯努利实验
- 作用：能够使用极少的内存，大数据量亿级数据去重复统计uv
- 伯努利实验
一次伯努利实验，抛硬币不管进行抛掷次数多少次，只要出现一个正面，就称之为为一次伯努利实验
对于这n次伯努利试验中，必然会有一个最大的抛掷次数k
k_max表示在所有次伯努利实验中，它是抛掷次数最高的
最终结合极大似然估算的方法，发现在n和k_max中存在估算关联：n = 2^(k_max)
结论：可以通过伯努利实验中最大抛掷次数来估算总伯努利实验次数 - 比特串
hash(id) = 比特串
不同的用户 id，必然拥有不同的比特串。每一个比特串，也必然会至少出现一次 1 的位置。我们类比每一个比特串为一次伯努利试验
不同的用户 id，必然拥有不同的比特串。每一个比特串，也必然会至少出现一次 1 的位置。我们类比每一个比特串为一次伯努利试验。
现在要分轮，也就是分桶。所以我们可以设定，每个比特串的前多少位转为10进制后，其值就对应于所在桶的标号。假设比特串的低两位用来计算桶下标志，此时有一个用户的id的比特串是：1001011000011。它的所在桶下标为：11(2) = 1*2^1 + 1*2^0 = 3，处于第3个桶，即第3轮中。
上面例子中，计算出桶号后，剩下的比特串是：10010110000，从低位到高位看，第一次出现 1 的位置是 5 。也就是说，此时第3个桶，第3轮的试验中，k_max = 5。5 对应的二进制是：101，又因为每个桶有 p 个比特位。当 p>=3 时，便可以将 101 存进去。
模仿上面的流程，多个不同的用户 id，就被分散到不同的桶中去了，且每个桶有其 k_max。然后当要统计出 mian 页面有多少用户点击量的时候，就是一次估算。最终结合所有桶中的 k_max，代入估算公式，便能得出估算值。
注意：如果入了同一个桶，如何更新桶里的值？取值大的那个 -
分桶
分桶数组是为了消减因偶然性带来的误差，提高预估的准确性
分桶平均的基本原理是将统计数据划分为m个桶，每个桶分别统计各自的k_max，并能得到各自的基数预估值 n ，最终对这些 n 求平均（调和平均数）得到整体的基数估计值。
DV - 就是要求的基数n
const -是修正因子
m - 表示第几轮次实验：进行一轮次实验，只能得到一个k_max，若进行的伯努利试验次数少，估算不准确，
所以采用多轮次实验，得到多个k_max值，然后根据以下公式进行评估得到相对准确的伯努利试验次数，也就是基数
RJ - 表示调和平均数
以下是调和平均数公式，调和平均数可以减轻大数的影响
image.png
image.png
- redis 实现源码
// 密集模式添加元素
int hllDenseAdd(uint8_t *registers, unsigned char *ele, size_t elesize) {
uint8_t oldcount, count;
long index;
// 计算该元素第一个1出现的位置
count = hllPatLen(ele,elesize,&index);
// 得到第index个桶内的count值
HLL_DENSE_GET_REGISTER(oldcount,registers,index);
if (count > oldcount) {
// 如果比现有的最大值还大，则添加该值到数据部分
HLL_DENSE_SET_REGISTER(registers,index,count);
return 1;
} else {
// 如果小于现有的最大值，则不做处理，因为不影响基数
return 0;
}
}
// 用于计算hash后的值中，第一个出现1的位置
int hllPatLen(unsigned char *ele, size_t elesize, long *regp) {
uint64_t hash, bit, index;
int count;
// 利用MurmurHash64A哈希函数来计算该元素的hash值
hash = MurmurHash64A(ele,elesize,0xadc83b19ULL);
// 计算应该放在哪个桶
index = hash & HLL_P_MASK;
// 为了保证循环能够终止
hash |= ((uint64_t)1<<63);
bit = HLL_REGISTERS;
// 存储第一个1出现的位置
count = 1;
// 计算count
while((hash & bit) == 0) {
count++;
bit <<= 1;
}
*regp = (int) index;
return count;
}
感谢这两位位大神
https://juejin.im/post/5c7900bf518825407c7eafd0
http://www.rainybowe.com/blog/2017/07/13/%E7%A5%9E%E5%A5%87%E7%9A%84HyperLogLog%E7%AE%97%E6%B3%95/index.html
http://www.rainybowe.com/blog/2017/07/13/%E7%A5%9E%E5%A5%87%E7%9A%84HyperLogLog%E7%AE%97%E6%B3%95/index.html
网友评论