一、为什么需要 Count-Min Sketch
你运营一个日活千万的新闻 App，产品经理想实时看每篇文章被点击了多少次。简单方案：用哈希表记录每个文章 ID 的点击数。问题来了，文章 ID 加上用户行为组合可能有上亿种，哈希表内存轻松破百 GB。更麻烦的是，大部分长尾文章只被点了一两次，但你也得为它们分配完整的哈希表条目。
如果只需要近似答案呢？比如「这篇文章大概被点了 1020 次，误差在 ±50 以内」，对于热门文章的排序、流量监控、异常检测来说，这个精度完全够用。关键在于：用固定大小的内存估算频率，不管数据量怎么增长，内存始终不变。
Count-Min Sketch 就是这个思路的数据结构。它用二维计数器数组和多个哈希函数，以极小的内存开销估算每个元素的出现频率。估算值只会偏大不会偏小（单向误差），误差范围可控。如果你已经了解布隆过滤器，可以把 Count-Min Sketch 理解为布隆过滤器的「计数版」，布隆过滤器回答「在不在」，Count-Min Sketch 回答「出现了几次」。
二、现实类比
想象一个农贸市场，管理员想统计每种蔬菜当天的销量。他不是逐笔记账（那太费纸了），而是在门口放了几块计数板。每块板子按不同规则把蔬菜归类，比如第一块按颜色分，第二块按形状分，第三块按产地分。西红柿是红色的、圆形的、本地产的，于是三块板子上对应的格子各加 1。
查询西红柿的销量时，看三块板上对应格子的计数，取最小值，因为红色、圆形、本产的格子可能被其他蔬菜「污染」而偏大，但取最小值能最大程度抵消这种正偏差。这就是 Count-Min Sketch 的核心：多维度计数，取最小值估算。
三、核心思想
Count-Min Sketch 由 d 行 w 列的二维计数器数组构成，每行对应一个独立的哈希函数。插入元素 x 时，对每一行用对应的哈希函数计算位置，将该位置的计数器加 1。查询 x 的频率时，取所有行中对应位置计数器的最小值。
查询 apple 的频率：取 counter[0][2]=1、counter[1][5]=1、counter[2][1]=1 的最小值 = 1。
3.1 为什么取最小值
每个计数器可能被其他元素的哈希碰撞「污染」，导致计数偏大。但所有行同时被同一个其他元素碰撞的概率很低。取最小值能最大程度抵消正偏差，直觉上，行数越多，至少有一行没被严重污染的概率越大。
3.2 误差分析
设计数器宽度为 w，深度为 d，总元素数为 n，则频率估算的误差上界为：
实际值 ≤ 估算值 ≤ 实际值 + ε × n其中 ε = e/w。概率上，误差超过 ε × n 的概率不超过 (1/e)^d。这意味着：
- 想降低误差 ε，增大宽度 w
- 想提高正确率，增大深度 d
典型参数：w = 10000、d = 7 时，ε ≈ 0.0003，误差超过 0.03% × n 的概率 < 0.1%。
3.3 核心操作与复杂度
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 插入（Add） | O(d) | d 行各做一次哈希和一次加法 |
| 查询（Estimate） | O(d) | d 行各做一次哈希，取最小值 |
| 合并（Merge） | O(d × w) | 两个相同结构的 Sketch 逐计数器相加 |
| 空间 | O(d × w) | 固定大小，与元素数量无关 |
Count-Min Sketch 的估算值只可能偏大、不可能偏小，因为哈希碰撞只会增加计数器，不会减少。这个单向误差在实际使用中很重要：如果你用估算值做阈值过滤，假阳性（多算的）只会让你多检查几次，但不会漏掉真正的高频元素。
四、变体与对比
| 特性 | Count-Min Sketch | Bloom Filter | HyperLogLog | Count-Mean-Min Sketch |
|---|---|---|---|---|
| 回答的问题 | 出现了几次？ | 在不在？ | 有多少不同元素？ | 出现了几次（修正版）？ |
| 误差方向 | 只偏大 | 只有假阳性 | 标准误差约 1.04/√m | 双向，更准确 |
| 空间 | O(dw) | O(m) | O(m)，m 很小 | O(dw) |
| 删除 | 不支持 | 不支持 | 不支持 | 不支持 |
| 典型场景 | 频率统计、热门排行 | 存在性判断 | 基数估计 | 低频元素更准确的统计 |
Count-Mean-Min Sketch 是 Count-Min Sketch 的改进版。查询时不是简单取最小值，而是先从每行的计数器中减去该行的噪声估计（(总计数 - 该位置计数) / (w-1)），然后再取中位数。这大幅改善了低频元素的估算精度，因为低频元素受哈希碰撞噪声影响最大。
Bloom Filter 与 Count-Min Sketch 的关系：两者都是概率型数据结构，都用多维哈希。Bloom Filter 的每个位置只有 0/1，回答「可能存在 / 一定不存在」；Count-Min Sketch 的每个位置是计数器，回答「至少出现了几次」。可以说 Count-Min Sketch 是布隆过滤器从布尔到整数的推广。
HyperLogLog 解决的是另一个问题，基数估计（有多少种不同元素），而不是频率统计。它的空间更省（通常不到 2 KB），但不能告诉你某个具体元素出现了几次。
五、多语言实现
package cms
import ( "encoding/binary" "hash/fnv" "math")
// CountMinSketch 用 d 行 w 列计数器估算元素频率type CountMinSketch struct { counters [][]uint32 // d 行 w 列 d int // 哈希函数数量（行数） w uint // 每行计数器数量（列数）}
// New 创建 Count-Min Sketch// epsilon: 误差率，delta: 误差超过阈值的概率func New(epsilon float64, delta float64) *CountMinSketch { w := uint(math.Ceil(math.E / epsilon)) // 列数 d := int(math.Ceil(math.Log(1 / delta))) // 行数 counters := make([][]uint32, d) for i := range counters { counters[i] = make([]uint32, w) } return &CountMinSketch{counters: counters, d: d, w: w}}
// Add 将元素加入 Sketch，计数器加 1func (cms *CountMinSketch) Add(data []byte) { for i := 0; i < cms.d; i++ { pos := cms.hash(data, i) cms.counters[i][pos]++ }}
// Estimate 估算元素的出现频率func (cms *CountMinSketch) Estimate(data []byte) uint32 { min := uint32(math.MaxUint32) for i := 0; i < cms.d; i++ { pos := cms.hash(data, i) if cms.counters[i][pos] < min { min = cms.counters[i][pos] // 取最小值抵消正偏差 } } return min}
// hash 用行索引做种子的双哈希func (cms *CountMinSketch) hash(data []byte, row int) uint { h := fnv.New128a() h.Write(data) binary.Write(h, binary.LittleEndian, uint32(row)) sum := h.Sum(nil) return uint(binary.BigEndian.Uint64(sum)) % cms.w}class CountMinSketch { private counters: Uint32Array[]; private seeds: number[];
constructor( private w: number, // 每行计数器数量 private d: number // 行数（哈希函数数量） ) { this.counters = Array.from({ length: d }, () => new Uint32Array(w)); // 每行用不同的种子生成独立哈希 this.seeds = Array.from({ length: d }, (_, i) => (i + 1) * 0x811c9dc5 ); }
// 从误差参数创建 static fromError(epsilon: number, delta: number): CountMinSketch { const w = Math.ceil(Math.E / epsilon); const d = Math.ceil(Math.log(1 / delta)); return new CountMinSketch(w, d); }
private hash(data: string, row: number): number { let h = this.seeds[row]; for (let i = 0; i < data.length; i++) { h = ((h ^ data.charCodeAt(i)) * 0x01000193) >>> 0; } return h % this.w; }
// 插入元素，计数器加 1 add(data: string): void { for (let i = 0; i < this.d; i++) { this.counters[i][this.hash(data, i)]++; } }
// 估算元素出现次数，取所有行中的最小值 estimate(data: string): number { let min = Infinity; for (let i = 0; i < this.d; i++) { const count = this.counters[i][this.hash(data, i)]; if (count < min) min = count; } return min; }}
// 使用示例：ε=0.001, δ=0.01const cms = CountMinSketch.fromError(0.001, 0.01);cms.add("hello");cms.add("hello");cms.add("world");console.log(cms.estimate("hello")); // 2（精确）console.log(cms.estimate("world")); // 1（精确）console.log(cms.estimate("other")); // 0 或 ≥0（可能因碰撞偏大）六、生产验证
Cassandra ， 热点 partition 采样
Apache Cassandra 在检测热点 partition 时并不用 Count-Min Sketch。它走的是 StorageService 的 samplePartitions 路径，最终落到 ColumnFamilyStore.beginLocalSampling 和 metrics.samplers，背后的近似频率统计由 FrequencySampler 完成，实现用的是 stream-lib 的 StreamSummary，也就是 Space-Saving 算法，而不是 CMS。Cassandra 的 classpath 里虽然带着 stream-lib（其中包含 CountMinSketch 类，底层是 long[][] 计数器、width = ceil(2/ε)、depth = ceil(-log2(1-δ))），但 Cassandra 自身源码里没有调用它。
顺带提一句常见误解：就算给 CMS 喂 ε = 0.0001、δ = 0.01，按文章 3.2 节的标准公式 w = ceil(e/ε) 算出来是 27183 列（不是「约 2 万」），d = ceil(ln(1/δ)) 是 5 行，5 行 × 27183 列 × 4 字节已经 ≈ 530 KB，若用 stream-lib 实际的 long（8 字节）计数器则 ≈ 1 MB，都不到 500 KB 这个说法站不住。
Redis ， TopK 数据结构
RedisBloom 的 TOPK 模块维护前 K 个高频元素。实现位于 src/topk.c（属于独立的 RedisBloom 模块仓库，不在核心 Redis 的 redis/redis 仓库里），底层用一组带概率衰减的计数器桶加 min-heap：每个桶存指纹（fingerprint）和计数，计数较大时按 decay 概率衰减驱逐，堆负责维护 Top-K 排序。这套机制属于 HeavyKeeper（Yang 等 2018），与 Count-Min Sketch 同属频率估算家族，但靠概率衰减驱逐而非单纯取最小值。插入元素时先在桶里查频率，若可能进入 Top-K 则更新堆，避免对每个元素都做堆操作。
Brave ， 分布式追踪采样
Brave（Zipkin 的 Java 追踪库）并没有用 Count-Min Sketch 做自适应采样。它的采样器都是基于固定比率或速率的：BoundarySampler 按 trace ID 取模做概率采样，RateLimitingSampler 按每秒令牌数限速，CountingSampler 预生成随机位集按比例放行。采样决策在 trace 根处一次性作出（before-the-fact sampling），并不依赖请求路径的实测频率。CMS 这种实时频率估算，并不属于 Brave 的采样机制。需要说明的是，基于频率的自适应采样在追踪系统里确实是个有价值的话题，只是 Brave 目前没这么做。
七、小结
什么时候用
- 热门排行 / Top-K：需要快速找出出现频率最高的元素，不需要精确计数，估算即可
- 流量监控 / 异常检测：实时统计 QPS、错误率，偏差几个百分点不影响告警判断
- 热点检测：在分布式存储中检测热点 key 或热点 partition，避免流量倾斜
- 自适应采样：根据元素频率动态调整采样策略，高频少采、低频多采
什么时候别用
- 需要精确计数：金融交易计数、库存管理等不能容忍任何误差的场景，老老实实用哈希表
- 需要删除元素：Count-Min Sketch 不支持删除（计数器只增不减），如需删除请用 Counting Bloom 或 Stream-Summary
- 低频元素需要精确：Count-Min Sketch 对低频元素的估算偏差较大（正偏差显著），如果关心长尾分布请用 Count-Mean-Min 变体
- 数据量很小：元素种类少、频率低时，哈希表的开销可以接受，CMS 的固定开销反而浪费
八、参考资料
- An Improved Data Stream Summary: The Count-Min Sketch and Its Applications - Cormode, Muthukrishnan, 2005, Journal of Algorithms 期刊扩展版（会议首发于 LATIN 2004）
- Count-Min Sketch Wikipedia - 误差分析与参数选择
- Apache Cassandra 源码 - 热点 partition 采样走 TopKSampler/StreamSummary（Space-Saving），非 CMS
- RedisBloom TopK 模块 - RedisBloom 仓库 src/topk.c，基于 HeavyKeeper + 堆
- Probabilistic Data Structures for Web Analytics - 多种概率数据结构的对比与工程实践
支持与分享
如果这篇文章对你有帮助，欢迎支持作者或分享给更多人
部分信息可能已经过时