Count-Min Sketch：用 KB 内存估算海量数据频率

Count-Min Sketch 用 KB 级固定内存估算数据流中每个元素的出现频率，误差单侧高估（永远不会低估）。常用于 Top-K 统计、网络流量分析、数据库查询频率估算。

目录

要解决的问题

在数据流中估算每个元素出现的频率，典型场景：

• 找出高频搜索词 / Top-K 元素
• 网络流量中的高频 IP 检测
• 数据库查询频率估算（索引优化依据）

精确计数需要 HashMap（O(n) 内存，n 为不同元素数）；Count-Min Sketch 只需 O(w × d) 固定内存，w 和 d 由精度要求决定，通常是 KB 级。

核心原理

数据结构：d 行 × w 列计数矩阵

维护 d 行 w 列的整数矩阵，配合 d 个相互独立的哈希函数：

• add(x)：对每一行 i，计算 hᵢ(x) % w 得到列号，将该格 +1
• query(x)：对每一行 i，读取 hᵢ(x) % w 的格子值，返回 d 行的最小值

为什么取最小值能降低误差？

每一格的计数可能因哈希冲突（多个元素映射到同一列）而被高估。不同行使用独立哈希函数，冲突位置不同——某行的冲突在另一行大概率不冲突。

取所有行的最小值，相当于选出"被冲突污染最少的那个估算"，有效降低了高估量。

误差保证

Count-Min Sketch 提供严格的单侧误差保证：

$$\hat{f}(x) \geq f(x) \quad \text{（永远不会低估）}$$

$$P\big[\hat{f}(x) - f(x) > \varepsilon \cdot N\big] \leq \delta$$

• f(x) 是元素 x 的真实频率
• N 是总插入次数
• ε 和 δ 是用户指定的精度参数

为什么只高估不低估：计数只增不减，哈希冲突只会让某格的值变大，不会变小。所以查询结果只可能 ≥ 真实值。

参数选择

w 和 d 直接由精度参数 ε、δ 推导：

示例：ε = 0.01（误差不超过总次数的 1%），δ = 0.01（失败概率 1%）：

w = ⌈e / 0.01⌉ = ⌈2.718 / 0.01⌉ = 272
d = ⌈ln(1/0.01)⌉ = ⌈ln(100)⌉ = ⌈4.605⌉ = 5

内存 = 272 × 5 × 8 bytes（long） = 10,880 bytes ≈ 11KB

直觉：ε 越小（要求越精确）→ w 越大；δ 越小（要求越可靠）→ d 越大。两者各自独立控制，调参互不干扰。

Java 实现

import java.nio.charset.StandardCharsets;

/**
 * Count-Min Sketch 频率估算器
 * 保证：P[估算值 - 真实值 > epsilon * N] ≤ delta
 */
public class CountMinSketch {
    private final int d;               // 行数（哈希函数数量）
    private final int w;               // 列宽
    private final long[][] table;
    private final long[] hashA, hashB; // 哈希参数：h_i(x) = (a*x + b) mod p
    private static final long MOD = (1L << 31) - 1; // 梅森素数，保证哈希均匀

    /**
     * @param epsilon 误差上界：估算误差 ≤ epsilon × 总插入次数
     * @param delta   超出误差上界的概率（失败概率）
     */
    public CountMinSketch(double epsilon, double delta) {
        this.w = (int) Math.ceil(Math.E / epsilon);
        this.d = (int) Math.ceil(Math.log(1.0 / delta));
        this.table = new long[d][w];
        this.hashA = new long[d];
        this.hashB = new long[d];
        java.util.Random rnd = new java.util.Random(42);
        for (int i = 0; i < d; i++) {
            hashA[i] = (long)(rnd.nextDouble() * (MOD - 1)) + 1; // a ≠ 0
            hashB[i] = (long)(rnd.nextDouble() * MOD);
        }
    }

    public void add(String item) { add(item, 1); }

    public void add(String item, long count) {
        long h = baseHash(item);
        for (int i = 0; i < d; i++) {
            table[i][hash(h, i)] += count;
        }
    }

    public long query(String item) {
        long h = baseHash(item);
        long min = Long.MAX_VALUE;
        for (int i = 0; i < d; i++) {
            min = Math.min(min, table[i][hash(h, i)]);
        }
        return min;
    }

    // 通用线性哈希：(a×baseHash + b) mod p，再 mod w 取列号
    private int hash(long baseHash, int row) {
        long val = (hashA[row] * baseHash + hashB[row]) % MOD;
        if (val < 0) val += MOD;
        return (int)(val % w);
    }

    // 多项式滚动哈希：将字符串转为 long
    private long baseHash(String s) {
        byte[] bytes = s.getBytes(StandardCharsets.UTF_8);
        long h = 0;
        for (byte b : bytes) h = h * 31 + (b & 0xFFL);
        return Math.abs(h);
    }
}

使用示例：

// 统计搜索词频率，允许 1% 误差，失败概率 1%
CountMinSketch cms = new CountMinSketch(0.01, 0.01);
// w=272, d=5，内存约 11KB

for (String keyword : searchStream) cms.add(keyword);

System.out.println("\"java\" 搜索次数：" + cms.query("java"));
System.out.println("\"python\" 搜索次数：" + cms.query("python"));

验证结果（apple×100、banana×50、cherry×10，ε=0.01，δ=0.01）：

样本量小时哈希冲突极少，三者均精确。在亿级数据流中，高估量受 ε·N 控制，不超过总次数的 1%。

对比与选型

选 Count-Min Sketch 的场景：

• 元素种类未知/无上界（网络 IP、用户 ID）
• 只关心高频元素（Top-K），低频误差无所谓
• 需要合并多节点统计结果（矩阵相加即可）

不适合的场景：

• 需要精确频率（如计费、审计）
• 需要删除操作（可用 Count-Mean-Min 变种解决）

参考资料

• An Improved Data Stream Summary: The Count-Min Sketch (Cormode & Muthukrishnan, 2003)