如何实现 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 结构。