如何實作 Count-Min Sketch 估算資料流中的頻率？

1. 題目

日誌平台持續收到事件鍵（例如 URL 或商品 ID），總量可能達到數十億筆。請在固定記憶體內實作 add(key) 與 estimate(key)，回傳鍵的近似出現次數；說明誤差、分片合併、計數器溢位，以及何時必須使用精確結構。

2. 約束與釐清

• 事件只能走過一次，不能把所有鍵放進雜湊表。
• 允許估計值偏大，但希望用參數控制誤差機率。
• 先討論非負計數；刪除、負權更新和依時間到期需要額外限制。
• 分片必須使用相同寬度、深度、雜湊種子和計數器編碼，才能直接合併。

3. 核心思路

Count-Min Sketch（CMS）維護 d 列、每列 w 欄的非負計數器。每列使用獨立雜湊函式把鍵映射到一欄；更新時所有對應計數器加一，查詢時取這些計數器的最小值。真實鍵的計數會出現在每列對應位置，其他鍵的碰撞只會增加計數，所以最小值是不會低估的上界。

常見參數以誤差 epsilon 和失敗機率 delta 表示：w = ceil(e / epsilon)，d = ceil(ln(1 / delta))。總更新量為 N 時，查詢值以至少 1 - delta 的機率不超過真實值加上 epsilon * N；這是機率誤差界，不是每次查詢的絕對保證。

4. 參考實作

init(epsilon, delta):
  w = ceil(e / epsilon)
  d = ceil(ln(1 / delta))
  table = array(d, w, fill=0)
  seeds = choose_d_independent_seeds()

add(key, weight=1):
  require weight >= 0
  for row in 0..d-1:
    col = hash(key, seeds[row]) mod w
    table[row][col] += weight
  total += weight

estimate(key):
  values = []
  for row in 0..d-1:
    col = hash(key, seeds[row]) mod w
    values.append(table[row][col])
  return min(values)

merge(other):
  require same w, d, seeds, counter encoding
  for each cell (r, c):
    table[r][c] += other.table[r][c]
  total += other.total

5. 複雜度與正確性

每次更新和查詢都存取 d 個單元，時間複雜度為 O(d)；空間複雜度為 O(d * w)，與不同鍵的數量無關。非負更新下，查詢取最小值仍不低於真實頻率。增加寬度可減少碰撞偏差，增加深度可降低超過誤差界的機率，但會線性增加記憶體和雜湊成本。

計數器必須選擇足夠寬的整數，或明確採用飽和策略；無號溢位會讓「不會低估」的性質失效。分片合併應逐單元相加，且參數和雜湊映射完全一致；直接合併不同配置會得到無法解釋的結果。

6. 追問與陷阱

• CMS 能回答「某個已知鍵大約出現多少次」，不會自動列出 Top-K；需要另一個候選集合或 heavy-hitter 結構。
• 碰撞只造成高估，不能從估計值反推出精確頻率或精確去重集合。
• 負權更新會破壞單調性和簡單誤差證明；刪除與滑動視窗通常需要時間分桶或可衰減結構。
• 不同時間視窗不能只把舊計數減掉，除非同時保存可回滾的分桶狀態。

7. 延伸閱讀

可以比較 CMS 與精確雜湊表、Bloom filter、HyperLogLog 和 Frequent Items Sketch：它們分別解決頻率查詢、成員判斷、基數估計和高頻項目辨識。面試時應依查詢目標、誤差預算、是否需要刪除，以及是否要輸出候選鍵來選擇結構。

8. 面試評分點

能畫出二維計數器

應說明每列獨立雜湊、更新所有列、查詢取最小值，並能解釋碰撞為何只會抬高計數。

能給出誤差參數

應把 epsilon、delta、w、d 與總更新量 N 連結起來，區分機率界和絕對精確保證。

能處理工程邊界

應討論計數器溢位、分片參數一致性、合併時逐單元相加，以及負權和滑動視窗的額外設計。

能判斷結構是否匹配

應指出 CMS 不提供 Top-K、精確名單或精確基數；需求改變時能選擇精確表、HLL 或 heavy-hitter 結構。