相異元素估計（distinct-elements estimation, HyperLogLog）

今天有多少「不重複」的訪客來到一個網站，而同一個人可能出現上千次、總命中數達數十億？精確地數相異事物，意味著要記住你已經看過的每一樣東西——一個巨大的集合——而這正是串流中我們負擔不起的。相異元素估計回答「有多少不同的項目？」，所用的草圖比真實集合小上數千倍，靠的是利用隨機雜湊的一個簡單統計事實。HyperLogLog 就是做這件事的著名、實用的演算法。

核心直覺是一場擲硬幣遊戲。把每個項目雜湊成一個均勻隨機的位元串；同一項目的重複會雜湊到相同的串，所以它們自動被忽略，重點是那組「相異」的雜湊值。現在觀察你在這些雜湊中見過的「最長前導零數」。一個以 k 個零開頭的雜湊，發生機率是 1/2^k，所以看到 k 個前導零的串，就是「你大約已雜湊了約 2^k 個相異項目」的證據——罕見事件只在你抽了許多樣本後才出現。樸素估計 2^(最大前導零數) 極為嘈雜，所以 HyperLogLog 精煉它：用前幾個雜湊位元把項目分進 m 個桶，追蹤每個桶內的最大前導零數，再用調和平均把 m 個桶合併。平均許多桶能壓垮變異，得到約 1.04/sqrt(m) 的相對誤差。用 m = 16384 個桶——幾 KB——你能把數十億個相異項目估到約 1% 以內。

這之所以重要，是因為相異計數是世上最被需要的分析之一：不重複使用者、不重複搜尋詞、攻擊中的相異 IP、資料庫某欄的相異值（用於查詢規劃）。HyperLogLog 在固定的微小記憶體中給出近乎精確的答案，跨機器合併輕而易舉（取各桶的最大值），且每項目 O(1)——這就是為什麼資料庫與分析系統都內建它。誠實的提醒：答案是帶有已知誤差帶的估計，不是精確計數；準確度由 m 事先設定（更多桶、更小誤差、更多記憶體）；而小基數需要修正，因為原始估計量在只見過少數項目時有偏差。