假設每日收到 30 億筆事件日誌,每筆含 16 字元 ID (128 bits)。若單純用 HashSet 存放唯一 ID,即便去重比例達 2/3,仍需約 119 GB 記憶體,且不含 Java 物件開銷。若要統計數週或數月資料,硬體成本將難以負擔。
位圖 將輸入透過雜湊函數映射到單一 bit,空間效率遠優於 HashSet。但統計十億基數仍需約 120 MB,且隨基數增長線性增長。稀疏位圖可壓縮,但效果有限。
基數估算 是熱門研究領域。開源專案 stream-lib 提供生產級實作。以下以統計莎士比亞全集不重複單詞為例,對比三種方法:

表中可見:HyperLogLog 僅用 512 bytes 即達 3% 誤差內,而 HashMap 需近 10 MB。在網路規模運算中,這類概率計數器能節省數量級空間。
適用於需控制誤差率的場景。兩階段運作:
n = -m * ln(Vn) 估算基數 n。m 可遠小於實際基數,碰撞導致誤差,但可透過調整 m 控制誤差範圍。
HLL 估算基數 Nmax 僅需 loglog(Nmax) + O(1) bits。核心思想:
S = h(M) ∈ {0,1}^∞。實際效能:1.5 KB 記憶體即可對十億級資料達 2% 精度,較 HashSet 的 120 MB 節省 5 個數量級。
真實場景中資料分佈於數百台伺服器。HLL 計數器具備 可合併性:兩個相容計數器的位圖直接做 OR 運算即可合併,無需集中原始資料。這極大降低網路傳輸與協調成本,是流式處理架構 (如 Storm, Flink) 的標準組件。
若您使用 JVM 語言 (Java, Scala, Kotlin) 且面臨大基數統計問題,請直接整合 stream-lib。它除提供 HLL、Linear Counting 外,還包含 Top-K、頻率估算等串流處理工具,生產環境驗證成熟。