Count-Min Sketch 频次估算器

功能说明

CountMinSketch 用固定大小的二维计数表估算元素在数据流中的出现次数，内存只与宽度和深度有关，适合高基数场景下的热点识别、限流键统计、日志 Top-K 预筛和广告曝光计数。estimate 返回上界估计，可能高估但不会低估。add 支持一次增加多个计数，count 返回累计总量。

关键代码

构造时创建 Uint32Array 作为计数表，宽度乘深度决定总槽位，默认宽度两千零四十八、深度五。每行使用不同种子，哈希采用 FNV-1a 变体并对宽度取模，降低不同行冲突的相关性。add 对每行对应槽位累加并使用无符号回绕，estimate 取所有行中的最小值，以抵消其他元素的碰撞噪声。种子数量必须与深度一致。

使用注意

计数会因哈希碰撞而偏高，深度越大误差越小但内存与写入成本越高。Uint32 回绕在极高频次下可能溢出，超大规模计数应改用 BigInt 或定期衰减。该结构不支持删除单个元素，衰减通常通过整体减半实现。种子应足够分散，自定义种子时避免全零或相邻值。结果适合排序与阈值判断，不适合精确计费。

验证方式

测试无碰撞时估计值等于真实值，重复添加同一元素累加正确。构造多个元素并比较估计值与真实计数，确认估计不小于真实值。测试自定义宽度、深度与种子，种子数量不匹配、零宽、负计数与非法参数会抛错。最后用大量随机键验证内存占用稳定，并测试空字符串与超长键的哈希路径。

代码示例

export interface CountMinOptions {
  width?: number;
  depth?: number;
  seeds?: readonly number[];
}

export class CountMinSketch {
  private readonly width: number;
  private readonly depth: number;
  private readonly table: Uint32Array;
  private readonly seeds: readonly number[];
  private total = 0;

  constructor(options: CountMinOptions = {}) {
    const width = options.width ?? 2048;
    const depth = options.depth ?? 5;
    if (!Number.isInteger(width) || width <= 0 || !Number.isInteger(depth) || depth <= 0) {
      throw new RangeError("width and depth must be positive integers");
    }
    this.width = width;
    this.depth = depth;
    this.table = new Uint32Array(width * depth);
    this.seeds = options.seeds ?? Array.from(
      { length: depth },
      (_, index) => Math.imul(index + 1, 0x9e3779b1) >>> 0,
    );
    if (this.seeds.length !== depth) {
      throw new RangeError("seeds length must equal depth");
    }
  }

  add(value: string, count = 1): this {
    if (!Number.isInteger(count) || count < 1) {
      throw new RangeError("count must be a positive integer");
    }
    for (let row = 0; row < this.depth; row += 1) {
      const index = row * this.width + this.hash(value, this.seeds[row]!);
      this.table[index] = (this.table[index]! + count) >>> 0;
    }
    this.total += count;
    return this;
  }

  estimate(value: string): number {
    let minimum = Number.POSITIVE_INFINITY;
    for (let row = 0; row < this.depth; row += 1) {
      minimum = Math.min(
        minimum,
        this.table[row * this.width + this.hash(value, this.seeds[row]!)]!,
      );
    }
    return minimum;
  }

  private hash(value: string, seed: number): number {
    let hash = seed >>> 0;
    for (let index = 0; index < value.length; index += 1) {
      hash ^= value.charCodeAt(index);
      hash = Math.imul(hash, 0x01000193) >>> 0;
    }
    return hash % this.width;
  }

  get count(): number {
    return this.total;
  }
}