Count-Min Sketch 是什么？它如何用哈希近似统计频率？
简化版
Count-Min Sketch 用多行计数数组和多个哈希函数近似统计元素频率。更新时每行对应位置加 1，查询时取多行计数的最小值。它省内存、适合流式统计，但结果可能高估，不会低估。
详细版
当数据流很大，无法为每个 key 保存精确计数时，可以用 Count-Min Sketch。
基本结构：
- 有 d 行计数数组，每行宽度 w。
- 每行使用一个哈希函数。
- 更新 key 时，d 行各自 hash 到一个位置并加 1。
- 查询 key 时，取 d 个位置计数的最小值。
- 冲突会让计数变大，所以估计值可能高估。
它常用于热点 key、流量统计、频率近似、异常检测等场景。
完整版教学
一、为什么需要近似频率统计
如果有 10 亿条日志，key 种类也可能非常多。用普通哈希表精确统计每个 key 的次数，内存可能扛不住。
Count-Min Sketch 选择牺牲一点精确性，换固定内存。
精确哈希表：key 越多，内存越大
CMS：数组大小固定，误差可控这类结构适合问“哪些 key 大概很热”，不适合问“这个 key 的精确次数必须一分不差”。
二、结构长什么样
CMS 是一个二维计数数组。假设 3 行、宽度 5：
row0: [0,0,0,0,0]
row1: [0,0,0,0,0]
row2: [0,0,0,0,0]每一行有自己的哈希函数。更新 apple 时，可能落到 row0[2]、row1[4]、row2[1]，这三个位置都加 1。
三、查询为什么取最小值
冲突只会让某个格子的计数变大，不会变小。一个 key 的真实次数被加到了每一行对应格子里，但这些格子还可能混入别的 key 的计数。
如果查询得到：
row0: 120
row1: 105
row2: 109估计值取 105。因为 120 和 109 可能混入更多冲突，最小值通常是污染最少的那个估计。它仍可能高于真实值，但不会低于真实值。
四、为什么多个哈希函数能降低误差
单行计数数组冲突可能很严重。多行独立哈希后，同一个 key 在每一行被不同 key 污染的概率不同。
| 行数 | 效果 |
|---|---|
| 1 行 | 容易被单次冲突严重污染 |
| 多行 | 取最小值降低偶然冲突影响 |
| 更多行 | 误差概率下降，但更新成本上升 |
宽度影响误差大小，行数影响误差概率。数组越宽，冲突越少；行数越多，取到较干净估计的机会越大。
五、CMS 的误差方向很重要
CMS 的估计值不会低估，只会等于或高于真实频率。这个性质适合热点检测：如果估计值都不高，那真实值一定不高；如果估计值高，还需要进一步确认。
真实次数 <= 估计次数如果业务不能接受误报，就要搭配精确表二次确认。例如先用 CMS 找候选热点，再用精确计数验证 Top N。
六、和布隆过滤器有什么区别
布隆过滤器判断“是否可能存在”，CMS 估计“出现了多少次”。两者都用哈希和数组，也都有误差，但回答的问题不同。
记忆钩子：Bloom Filter 管有没有，Count-Min Sketch 管大概有多少；CMS 取最小，是因为冲突只会把数抬高。
七、常见误区与追问
- 误区：CMS 是精确计数器。 它是近似结构，结果可能高估。
- 误区：CMS 会低估频率。 标准 CMS 冲突只增加计数，不会低估。
- 误区：行数越多越好。 行数增加会提高更新和查询成本，要和误差要求平衡。
- 追问：为什么查询取 min？ 因为每行都可能被冲突抬高，最小值通常污染最少。
- 追问：如何找热点 key？ CMS 只能估计频率，候选 key 还需要来源记录或额外结构维护。
八、加强记忆
Count-Min Sketch 是流式频率统计的“哈希计数矩阵”。更新时多行加数，查询时多行取最小。它省内存、速度快、可控误差，但只适合近似判断，重要决策通常要二次精确确认。