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) 的量級，解釋小範圍線性計數和大範圍修正，並區分機率誤差與精確保證。
能處理分散式合併
應指出合併是逐暫存器取最大值，並明確所有分片必須共享雜湊函式、精度和編碼。
能識別產品邊界
應主動區分近似分析指標與精確名單、滑動視窗、刪除和計費場景，說明這些需求為何需要額外設計。