HyperLogLog的“数学基石”：伯努利试验+调和平均数
Redis HyperLogLog能实现“小空间估算基数”，核心依赖两个数学工具：伯努利试验（提供估算的理论基础）和调和平均数（降低估算误差）。
一、先讲：伯努利试验——HLL估算的“源头”
1. 什么是伯努利试验？
它是一种重复、独立、只有两种结果的随机试验：比如“抛硬币”（正面/反面）、“投篮”（命中/不命中）、“抽卡”（抽到/没抽到）。
关键特点：
- 每次试验结果互不影响（独立）；
- 只有“成功”或“失败”两种结果；
- 每次试验“成功”的概率固定（比如抛硬币正面概率是50%）。
2. 伯努利试验和HLL的关联
HLL把“统计元素基数”转化成了**“伯努利试验找最长连续失败次数”**的问题，具体对应：
- 把“元素通过哈希函数转成二进制串”看作一次伯努利试验；
- 把“二进制位是0”看作“失败”，“是1”看作“成功”；
- 对每个元素的哈希串，统计“从左数第一个1出现前，连续0的个数”（记为
k）——相当于“连续失败k次后首次成功”。
举个例子：
假设某元素的哈希串是00101...，从左数前两位是0（连续失败2次），第三位是1（首次成功），那么这个元素对应的k=2。
3. 核心推论：用“最大k”估算基数
伯努利试验有个结论：
若每次试验成功概率是
p，那么“首次成功前连续失败k次”的概率是(1-p)^k × p； 当试验次数足够多时，出现的最大连续失败次数max_k，和试验总次数（即基数）正相关。
对应到HLL：
- 哈希函数保证每个位是0/1的概率接近50%（
p=0.5）； - 若统计到的最大
k是max_k，则基数≈2^max_k（比如max_k=20，基数≈100万）。
但这里有个问题：只看单个max_k误差会很大（比如碰巧某个元素的哈希串有超长连续0）——这时候就需要调和平均数来“修正误差”。
二、再讲：调和平均数——HLL降低误差的“利器”
1. 什么是调和平均数？
先回忆三个常见的平均数：
- 算术平均数：(a1+a2+...+an)/n（易受极端值影响）；
- 几何平均数：n√(a1×a2×...×an)（适合比例数据）；
- 调和平均数：n / (1/a1 + 1/a2 + ... + 1/an)（更“照顾”小值，能降低极端值的影响）。
举个例子：
数据是1、2、100：
- 算术平均数：(1+2+100)/3≈34.3（被100带偏了）；
- 调和平均数：3/(1+0.5+0.01)≈1.98（更接近小值，弱化了极端值的影响）。
2. 调和平均数在HLL里的作用
HLL的解决方案是**“分桶+调和平均”**：
- 分桶：把哈希串的前几位（比如Redis HLL用前14位）作为“桶编号”，把所有元素分配到16384个桶中；
- 每个桶独立统计max_k：每个桶里的元素各自算
k，取桶内的max_k； - 对所有桶的2^max_k取调和平均：用调和平均后的结果作为最终基数的估算值。
这么做的好处是：
单个桶的max_k可能因为“运气”出现极端值，但16384个桶的调和平均，会把极端值的影响降到最低——这也是HLL能把误差控制在0.81%的关键。
三、总结：伯努利试验+调和平均数=HLL的“数学闭环”
- 伯努利试验：把“统计基数”转化为“统计最长连续失败次数”，提供了“用max_k估算基数”的理论基础；
- 调和平均数：通过“分桶+调和平均”修正了单样本的极端误差，让估算结果更稳定。
这两个数学工具的结合，才让HLL实现了“用15KB内存估算亿级数据基数”的奇迹——技术的背后，其实是数学的力量。
注意：本文归作者所有，未经作者允许，不得转载
