<antirez>
8 hours ago
- HyperLogLog 是一种随机算法，使用恒定的小内存近似计算集合中唯一元素的数量。
- 它使用哈希将元素分配到寄存器中，并通过统计前导位中最长的连续零来估算基数。
- Redis 为每个键实现了 HyperLogLog，使用 12KB 容量、16384 个寄存器，标准误差为 0.81%。
- API 包括 PFADD、PFCOUNT 和 PFMERGE 命令，这些命令都作用于字符串编码的 HLL 值。
- 性能优化包括循环展开、预计算查找表以及对最近计算的基数进行缓存。
- 对于小基数的偏差校正，采用基于四次多项式回归的方法，在 40k–72k 范围内提高了准确性。
- 该实现使用 64 位哈希函数和 6 位计数器，消除了对上限达 2^64 的基数的实际限制。