一句话定义:Count-Min Sketch(简称 CMS)是一种概率型数据结构(probabilistic data structure):用一块事先固定大小的内存,估算数据流里每个元素出现了多少次;它的答案只会偏大,不会偏小。
原理
它有两个参数:宽度 w 和深度 d。开 d 行计数器,每行 w 个格子,每行配一个不同的哈希函数(hash function)。来一条数据 x,就用 d 个哈希函数各算出一个位置,把对应的 d 个格子各加 1。查询 x 出现了几次时,同样算出这 d 个位置,读出 d 个数字,取最小值。
打个生活化的比方:一场几万人的投票,你手里只有五排纸箱,每排几十个。你不按人名分箱,而是用五套不同的“分类规则”把票投进五排箱子。查某人得票时,看每排里他对应的那个箱子,取五个数字里最小的那个。
为什么取最小?因为箱子会撞车:两个不同元素被哈希到同一格,计数就混在一起,读出来偏大。标准版 CMS 的计数器只加不减,所以误差是单向的:只会高估。五行同时被撞的概率很低,取最小就是把最“干净”的那次读数挑出来。
误差上界与取舍
经典结论是:取 w = ⌈e/ε⌉、d = ⌈ln(1/δ)⌉ 时,估计值不超过真实值 + εN 的概率至少 1−δ,其中 N 是流里元素总数。换算一下:想要 ε=0.1%、δ=1%,大约只要 2700 × 5 个计数器,几十 KB 就能应付上千万条数据、上百万个不同元素,而精确保存它们需要几十 MB。
两个旋钮各管一头:加宽 w 降低哈希冲突,也就是降低 ε;加深 d 降低“所有行同时被撞”的概率,也就是降低 δ。代价是内存 w×d 和每次更新的哈希计算量。实践中通常只用几行,每行几千到几十万个格子。
注意 εN 是相对总量的误差,不是相对单个元素的——热门元素的相对误差很小,冷门元素可能估得离谱,这正好符合“找热点”的用途。
和相邻概念的区别
| 结构 | 回答的问题 | 内存 | 误差方向 |
|---|---|---|---|
| 哈希表 hash table | 精确出现几次 | 随去重元素数增长 | 无 |
| Count-Min Sketch | 大约出现几次 | 固定,与元素数无关 | 只高估 |
| Bloom Filter | 在不在集合里 | 固定 | 只误判“在” |
| HyperLogLog | 有多少个不同元素 | 固定 | 有偏,可校正 |
三者都是“用精度换内存”,但回答的问题不同:CMS 数次数,Bloom Filter 判存在,HyperLogLog 数种类。
实际意义
对从业者:CMS 常用于流式系统找 Top-K 重击者(heavy hitters)——先粗筛候选,再精确统计;也用于广告频次控制、数据库 join 大小估计、异常流量检测。它还可合并:各机器分别算自己的 sketch,直接相加即可得到全局结果,非常适合分布式统计。局限是标准版不支持删除,也拿不出所有 key 的列表,通常要配合其他结构使用。具体实现变体以官方文档为准。
对普通人:手机 App 不卡、热搜榜更新得快,背后可能就有它的功劳——服务端没有傻傻地把每个 key 都存一遍,而是用几十 KB 换来了“够用”的答案。
