Flajolet–Martin 与 HyperLogLog

罕见事件图像 ​

出现 rank 20 意味着观察到概率约 $2^{-20}$ 的前缀事件，暗示独立不同元素规模约百万；它不是确定下界，因为少量元素也可能偶然产生长零串。多个桶提供许多近独立局部实验，才让估计稳定。

合并与边界 ​

两个 HLL 若使用相同哈希、桶数和 rank 定义，可逐寄存器取 max 得并集摘要。哈希偏差、对抗输入、少基数和哈希空间饱和都会产生系统误差；实际 HLL++ 使用小范围修正与偏差校准，常数须匹配版本。结果是概率估计，不是置信区间或确定上下界。

重复项与寄存器空间 ​

同一元素重复到达总产生相同桶与 rank，寄存器 max 不变，所以摘要天然估 distinct 而非流长度。每个寄存器只需存到哈希位宽的 rank，位数为 $O(\log \log U)$；总空间约 $m\log \log U$ 位加哈希种子。

小基数时许多寄存器仍为零，linear counting 修正利用零寄存器比例；大基数接近哈希空间时碰撞饱和。直接在所有范围都用原始调和公式会产生已知偏差。

寄存器状态的数值轨迹 ​

取 $p=2$ 时有四个寄存器，初态 [0,0,0,0]。若不同元素的 (桶号,rank) 依次为 (0,1),(2,3),(0,4),(2,2)，状态依次变为 [1,0,0,0]、[1,0,3,0]、[4,0,3,0]，最后一次不再改变。这个轨迹同时展示 max 更新、空桶和较小 rank 被吸收。

哈希位的拆分必须固定：前 $p$ 位只选桶，剩余位才计算 rank。若把同一批前缀位既用于桶号又计入前导零，桶选择与寄存器值产生相关性，标准误差分析不再适用。

寄存器可按固定小位宽紧凑打包，但更新某一字段时要掩码写回，避免进位污染相邻字段。由高精度摘要降采样到较小 $p$ 需要重新映射桶并修正 rank；它不是简单截断寄存器数组。

HLL 的逐寄存器 max 使分片摘要能在哈希配置一致时合并为并集基数估计，适合独立访客、去重计数与分布式监控。它只恢复基数而不恢复成员；需要列举元素、支持一般删除或抵抗已知哈希的对抗输入时，必须换用带不同状态契约的结构。