HyperLogLog 以數 KB 記憶體計數數十億個不同項目

精確基數——也就是出現過多少個不同的使用者、IP 位址或搜尋查詢——通常需要與不同項目數量成正比的記憶體，這在網際網路規模下不可能做到。2007 年，Philippe Flajolet 與 INRIA 的同事發表了 HyperLogLog，這是一種機率草圖，能以約 1.5 KB 的記憶體、約 2% 的準確度估算超過十億的基數。

這個技巧建立在擲硬幣的直覺上：將每個元素雜湊成均勻分布的隨機數，並觀察最長的前導零連續長度。連續 n 個零很罕見——機率為 2^-n——因此當它出現時，集合可能大到足以產生它，而 2^n 就是基數的良好估計。HyperLogLog 將資料流拆成許多子集，每個子集保留一個暫存器記錄其最長零連續長度，並以調和平均數合併它們，使離群值不會扭曲估計。

此方法源自 Flajolet-Martin 1984 年的演算法與 LogLog 演算法。使其達到生產就緒的工程改良，來自 2013 年 Google 的 Heule、Nunkesser 與 Hall 所發表的論文《HyperLogLog in Practice》，該論文修正了大型與小型基數的偏差與稀疏性問題。

Redis 將 HyperLogLog 變成產品功能：其 PFADD、PFCOUNT 與 PFMERGE 指令可估算多達 2^64 個不同元素，每個鍵最多使用 12 KB 記憶體，標準誤差為 0.81%，且草圖可以合併，因此每日計數無需重新讀取原始資料流即可合併。

從雜湊前導零估算計數

雜湊將任意資料轉成均勻分布的隨機數，且基數不變

最長的前導零連續長度是集合大小的自然、可觀察估計

拆分成暫存器再加上調和平均數可抵銷雜訊

草圖可以合併，因此每日計數無需儲存原始資料流即可合併

當答案只需要近似值時，就別再儲存資料——改為儲存一個能透過隨機性揭示規模的微小草圖，以有界的誤差換取無界的規模。

HyperLogLog 成為分析與資料庫中的標準積木：Redis 將其作為資料型別提供，而 2013 年 Google 論文的改良，正是讓它能在生產系統中大規模使用的關鍵。此草圖的邏輯——保留少量證據紀錄，而非資料本身——也支撐了後來的結構，如 MinHash 與 Count-Min Sketch。