跳到主内容
快讯直播
AI智模界
AI 词典

Count-Min Sketch:用固定内存估算海量频率

一句话定义: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 换来了“够用”的答案。

AI 生成本文由 AI 基于公开信息自动生成,仅供参考。