Redis HyperLogLog 的实现原理与误差范围
哪些公司问过
答案要点
- 概率型基数估计,单个 key 密集编码约 12KB,标准误差约 0.81%
- 64 位哈希,14 位选 16384 个寄存器,剩余位记录首个 1 位置的最大值,每个寄存器 6 bit
- 用调和平均合并各桶估计,并对小基数做偏差修正
- 小基数时采用稀疏编码,增长后转为密集编码
- PFADD 添加、PFCOUNT 估计、PFMERGE 合并,适合 UV、独立 IP 等统计
易错点
- 以为 HLL 能判断元素是否存在或取出元素
- 认为误差会随数据量增大而变大,其实相对误差基本稳定
- 把稀疏编码下的小 key 也按 12KB 估算内存
面试官常见追问
- 为什么用调和平均而不是算术平均?
- 统计 UV 时 HLL、Set、Bitmap 怎么选?
- 多天 UV 怎么合并?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。