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.total5. 复杂度与正确性
每次更新和查询都访问 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 结构。