Redis hyperloglog学习

背景知识

【伯努利试验】：

【伯努利试验】是一个概率论中的概念，指在相同的条件下重复进行n次独立的试验，每次试验只有两种可能的结果，且这两种结果发生的概率是固定的
抛硬币作为伯努利试验：在抛硬币时，我们可以将正面出现视为“成功”，反面出现视为“失败”。如果硬币是公平的，那么每次抛掷正面或反面出现的概率都是1/2，这符合伯努利试验的定义。
n(一般实验次数) = 2^K K第K次抛出正面

【调和平均值算法】

平均值 = (数据1 + 数据2 + … + 数据n) / n 普通平均值算法对极端值敏感，例如 我和马云资产平均一下500亿，因此引入调和平均值
调和平均值 = n / (1/数据1 + 1/数据2 + … + 1/数据n) 这种平均值算法减少了极端值的影响

什么是hyperLoglog？

介绍：
hyperLoglog是Redis中的一种数据结构，用于进行基数估计（cardinality estimation）。基数估计是指在一个数据流或数据集中，估算不重复元素的数量。hyperLoglog通过一种概率算法，能够在使用较少内存的情况下，高效地估算出数据集的基数。特点：
内存效率高：与传统的集合数据结构（如Redis的set）相比，hyperLoglog能够使用极少的内存空间来估算基数。这对于处理大规模数据流或数据集非常有用。 大小仅需12kb，误差率在0.2%左右
概率算法：hyperLoglog使用一种概率算法来估算基数，这意味着估算结果不是绝对准确的，但误差通常在一个可接受的范围内。这种算法的时间复杂度较低，使得估算过程非常高效。
适用于数据流：由于hyperLoglog的内存效率高且支持增量更新，它非常适合用于处理数据流场景，如网站访问量统计、用户行为分析等。使用场景：
大规模数据集的基数估计：当需要估算一个大规模数据集中不重复元素的数量时，hyperLoglog是一个很好的选择。
数据流处理：在处理实时数据流时，hyperLoglog可以高效地估算出数据流中不重复元素的数量。
去重统计：在需要对数据进行去重统计时，hyperLoglog可以提供一个快速且内存高效的解决方案。优点&缺点：
优点： 大小仅需12kb，误差率在0.2%左右
缺点：估算结果不是绝对准确的，但误差通常在一个可接受的范围内。

实现原理概述

hyperloglog实现原理： 根据实验值反推实验次数，将用户id 转成64位hash值，其中14位低位值用于分桶，分桶个数2的14次方个，高50位用于计算第一个1出现位置的索引值(0-50的一个值)，因此使用6位存储足够， hyperlog内存12k计算：2∧14×6位/8比特/1024=12k
由于实验现象存在误差和偶然现象因此采用分组实验（这里叫分桶），分组结果求平均次数得出最终值，但是传统平均算法会有大值影响，典型案例我和马云工资平均50亿，为了避免这个问题才用了调和平均算法使得结果更加精准1. 字符元素转成64位二进制数，读取方向从地位往高位读
|----------------------高位50位---------------------|----低位14位----|
|10000000000000000000000000000000000000000000000001|10000000000001|2. 低位14位用于分桶，因此桶的数量就是2^14=16384个  高位50位用于计算第一个1出现位置的索引值
hyperloglog底层的存储就是[000000][000000][000000].....16384个,[000000]6位存储0-50的索引值，总共6*16384=98304位/8比特/1024=12k3. 求和
n = 偏差因子*桶数*桶内元数数量 （由于概率统计存在偏差，内部会使用偏差因子纠正偏差），纠正后 100w数量偏差在0.2%左右