CodeWalk

Count-Min Sketch算法的原理与大数据近似计数应用

作者：Yahuda · 2026-05-30 12:55

Count-Min Sketch（CMS）是一种概率性数据结构，请解释CMS的底层原理：如何通过二维计数矩阵和多个哈希函数估计元素频次？它的查询结果是近似值且可能高估（Overestimate），为什么不会低估（Underestimate）？与HyperLogLog和Bloom Filter相比，CMS分别解决什么问题？给出一个CMS在大数据流中的TopK近似统计应用。

回答

Yahuda

Count-Min Sketch（CMS）原理：

1. 数据结构：

  • 二维数组count[d][w]，d行（哈希函数数），w列（计数器宽度）
  • d个独立的哈希函数h1...hd，映射到[0, w-1]

2. 操作：

# 初始化
d, w = 5, 2000  # 5行，2000列
count = [[0]*w for _ in range(d)]

# 增加频次（元素x出现c次）
for i in range(d):
    count[i][h_i(x)] += c

# 查询频次：取所有哈希位置的最小值
freq = min(count[i][h_i(x)] for i in range(d))
  • 为什么只高估不低估：不同元素哈希可能冲突导致计数器变大，所以结果≥真实频次
  • 取最小值可减少冲突的影响

3. 误差控制：

  • 误差ε = e/w（w越大误差越小）
  • 概率δ = e^(-d)（d越大置信度越高）
  • 内存占用：d×w×4字节（int计数器）

4. 三者的关系： | 算法 | 解决的问题 | 输出 | |------|-----------|------| | Bloom Filter | 元素是否存在 | 可能存在/绝对不存在 | | HyperLogLog | 不重复元素数（基数）| 近似基数 | | Count-Min Sketch | 元素出现频次 | 近似频次（高估）|

5. 应用场景：

  • TopK近似统计：CMS + 小顶堆，找出Stream中TopK高频元素
  • 检测热点Key：缓存场景中识别访问量最高的Key
  • 网络流量监控：统计IP/URL的访问频率
  • 数据库查询计划：估计Join的选择率（Cardinality Estimation）

6. 流式TopK实现：

import hashlib
import heapq

class CountMinSketchTopK:
    def __init__(self, k=100, d=5, w=10000):
        self.k = k
        self.cms = [[0]*w for _ in range(d)]
        self.heap = []  # 小顶堆
    
    def add(self, item, count=1):
        for i in range(len(self.cms)):
            idx = int(hashlib.md5(f"{i}{item}".encode()).hexdigest(), 16) % len(self.cms[0])
            self.cms[i][idx] += count
        freq = self.query(item)
        # 更新堆
        if len(self.heap) < self.k:
            heapq.heappush(self.heap, (freq, item))
        elif freq > self.heap[0][0]:
            heapq.heappop(self.heap)
            heapq.heappush(self.heap, (freq, item))