1. 题目
日志系统每天接收数十亿个用户标识，需要实时估算当天的独立用户数。内存预算只有几 KB，结果允许有小幅误差。请设计一个流式算法，并说明误差、合并多个分片的方法，以及它和精确去重的边界。
2. 约束与澄清
- 输入是持续到达的标识流，要求单次遍历、固定内存。
- 查询目标是一个时间窗口内的近似基数（distinct count）。
- 假设哈希函数分布均匀且所有分片使用同一哈希算法、寄存器数量和编码。
- 题目不要求删除元素；滑动窗口、过期和强一致精确值需要额外结构。
3. 核心思路
HyperLogLog（HLL）把哈希值拆成寄存器索引与剩余比特。设寄存器数量为 m = 2^p：前 p 位选择寄存器，剩余比特中从最高位开始连续零的长度加一记为 rho。每个寄存器只保存见过的最大 rho。
直觉是：某个寄存器观察到很长的前导零，说明样本空间中出现了更多不同元素。用所有寄存器的调和平均估计基数：
E = alpha_m * m^2 / sum(2^(-M[j]))
其中 M[j] 是第 j 个寄存器的值，alpha_m 是与寄存器数有关的校正常数。常用实现还会在小基数时使用线性计数修正，在极大值接近哈希空间上限时使用大范围修正。
4. 参考实现
下面的伪代码展示更新、估算和合并。真实实现应使用固定宽度整数、明确的哈希函数，并处理 rho 的上限。
init(p):
m = 1 << p
M = array(m, fill=0)
add(x):
h = hash64(x)
j = high_bits(h, p)
w = remaining_bits(h, p)
r = leading_zero_count(w) + 1
M[j] = max(M[j], r)
estimate():
z = sum over j of 2^(-M[j])
e = alpha(m) * m * m / z
if e <= small_range_threshold(m) and zero_registers(M) != 0:
e = m * log(m / zero_registers(M))
return large_range_correction_if_needed(e)
merge(other):
require same p, hash function, and register encoding
for j in 0..m-1:
M[j] = max(M[j], other.M[j])5. 复杂度与正确性
每个元素只做一次哈希、一次寄存器更新，时间复杂度是 O(1)；空间复杂度是 O(m)，与流中元素总数无关。标准 HLL 的相对标准误差约为 1.04 / sqrt(m)：例如 m = 16,384 时约为 0.81%，这是概率保证意义上的估计误差，不是每次查询都严格落在固定区间。
寄存器更新取最大值，因此重复加入同一元素不会继续增大状态，满足幂等性。多个分片可以逐寄存器取最大值后合并，前提是哈希函数、p 和编码完全一致；否则统计分布不兼容，结果没有可靠含义。
6. 追问与陷阱
- HLL 返回近似值，不能替代需要逐用户准确名单、审计或计费的精确集合。
- 清空寄存器只能表示全新窗口。滑动窗口需要按时间分桶、多个 HLL 或可删除的变体，并处理桶边界和存储成本。
- 哈希碰撞和输入分布偏差会影响估计；应选择质量稳定的 64 位或更宽哈希，并在系统边界统一实现。
- 小基数时直接使用原始调和平均会有偏差，线性计数修正利用零寄存器数量降低偏差。
7. 延伸阅读
- Redis 的 PFCOUNT 命令与 HyperLogLog 数据类型文档。
- Snowflake 的 approximate cardinality 文档。
- Meta Engineering 关于 Presto HyperLogLog 的介绍。
8. 面试评分点
能说明状态结构
候选人应说清楚 m = 2^p 个寄存器、索引和 rho 的来源，以及寄存器只保留最大值的原因。
能推导误差与修正
应给出 1.04 / sqrt(m) 的量级，解释小范围线性计数和大范围修正，并区分概率误差与精确保证。
能处理分布式合并
应指出合并是逐寄存器取最大值，并明确所有分片必须共享哈希函数、精度和编码。
能识别产品边界
应主动区分近似分析指标与精确名单、滑动窗口、删除和计费场景，说明这些需求为何需要额外设计。