基数估计算法：HyperLogLog 的改进与对比 基数估计算法用于统计一个数据集中不重复元素的个数。HyperLogLog（HLL）是其中一种高效算法，但并非唯一选择。本专题将介绍其他经典基数估计算法，并与 HLL 进行对比。 1. 基数估计问题定义 问题：给定一个包含重复元素的大规模数据集，如何快速估算其中不重复元素的个数（基数）？ 挑战：精确计算（如使用哈希表）需要 O(n) 内存（n 为基数），对于海量数据不可行。 目标：使用亚线性内存（如几 KB）实现误差率可控的估算。 2. 线性计数（Linear Counting）算法 核心思想 ：使用一个长度为 m 的位图（初始全 0）。 对每个元素进行哈希，映射到 [ 0, m-1 ] 的某个位置，并将该位置设为 1。 统计位图中 0 的个数 U。 基数估计公式：n̂ = -m * ln(U/m)。 关键原理 ：若哈希函数均匀，U 的期望值与基数 n 存在对数关系，通过反函数估算 n。 优缺点 ： 优点：简单，在低基数时精度高。 缺点：当 n 接近 m 时，哈希冲突剧增，误差快速上升；内存消耗 O(m)。 3. LogLog 算法 核心思想 ：利用哈希值首现 1 的位序（rank）的几何平均数估算基数。 哈希函数生成足够长的二进制串（如 64 位）。 记录每个元素哈希值二进制表示中，从最低位开始首个 1 出现的位置（如 0001...1 → rank=4）。 取所有 rank 的最大值 M，基数估计：n̂ = α_ m * m * 2^M（m 为桶数，α_ m 为修正因子）。 关键原理 ：若基数 n 很大，至少有一个哈希值首现 1 的位序较高（如 2^M 量级），通过 M 反推 n。 优缺点 ： 优点：内存占用仅需存储 m 个计数器（每个占几个比特）。 缺点：方差较大，误差约 1.3/√m。 4. HyperLogLog 的改进 核心改进 ：使用调和平均数而非几何平均数，减少极端值影响。 步骤同 LogLog，但最终估计公式：n̂ = α_ m * m² / (Σ 2^{-M_ i})，其中 M_ i 为每个桶的 rank 最大值。 调和平均数对离群值不敏感，使估计更稳定。 优势 ：误差率降至 1.04/√m，相同内存下精度更高。 5. 算法对比与选择 内存效率 （固定误差率 1%）： Linear Counting：需约 10^4 位。 LogLog：需约 1.5KB。 HyperLogLog：需约 1.5KB（但误差更小）或更少内存达到相同误差。 适用场景 ： 低基数（n < m/10）：Linear Counting 更准。 高基数（n > m/10）：HyperLogLog 最优。 折中方案：实际系统（如 Redis）常结合 Linear Counting 和 HLL，根据基数动态切换。 6. 实际应用示例 Redis 的 PFCOUNT ：使用 HLL 实现，仅用 12KB 内存可估算万亿级基数，误差 <1%。 大数据去重 ：在数据流水线中预先用 HLL 估算唯一用户数，避免全量扫描。 通过对比可见，HyperLogLog 在多数场景下是内存效率与精度平衡的最佳选择，但理解其演进和替代方案有助于在特定需求下优化设计。