Count–Min Sketch

每一行都把目标频率与碰撞噪声加在同一个桶里；在非负流中噪声只能向上推高估计。多行独立哈希后取最小值，相当于等待至少一行避开严重碰撞，因此保留“不低估”的方向并把同时坏掉的概率指数压低。

Count–Min 对非负频率使用无符号桶和逐行最小值，碰撞只会造成单边高估；CountSketch公理库CountSketchCountSketch · Count Sketch以桶哈希和随机符号抵消碰撞，再跨行取中位数估计频率与 L2 heavy hitters。加入随机符号并取中位数，误差围绕真实频率摆动，更适合 turnstile 流和 ${\ell }_2$ 尾部保证。

频率查询例子 ​

统计 API 路径请求量时，每次请求把对应键加一。冷门路径可能因热门路径碰撞被高估，但多行中只要一行避开主要碰撞，最小值就恢复较小误差；结构不会把真实请求数估得更低。

边界与保证类型 ​

误差是全局 $L_1$ 的加性误差，不是相对误差 $\epsilon f_i$。严格 turnstile 的负更新会让碰撞项可正可负，破坏“只高估”和 min 逻辑；需其他 sketch。哈希独立性、一次固定查询与许多自适应查询的失败概率不同。conservative update 是工程变体，不能沿用所有原始线性性质。

合并与范围聚合 ​

使用相同 $d,w$ 和同一组哈希函数的两个 sketch 可逐计数器相加，得到串接两条流的 sketch；函数不同则桶语义不一致，不能合并。这个性质来自每行计数的线性更新。

若键有顺序，不能直接从单个 CMS 回答任意范围和，因为哈希打散顺序；可在 dyadic interval 层级各维护 sketch，把范围分解成 $O(\log U)$ 个节点，但误差与失败概率也要跨节点累积。

从固定查询到查询集合 ​

上述概率界先固定一个键 $i$。若系统预先知道要同时保证 $q$ 个键，可把单键失败率设为 $\delta /q$，即把深度增至 $d=\lceil \ln \left(q/\delta \right)\rceil$，再用 union bound 得到整组查询共同成功的概率至少 $1-\delta$。查询由先前答案自适应生成时，这个直接换参并不自动成立。

计数器还要按流总质量选择位宽。若使用饱和整数，热门桶到上限后便不再是频率向量的线性映射；若发生无符号回绕，min 甚至可能严重低估。工程实现必须把溢出策略作为误差模型的一部分，而不是把它归入哈希碰撞误差。

CMS 只提供候选键的点估计，不会自行列出 heavy hitters。若宇宙很大，仍需 Misra–Gries、分层编码或外部候选生成器；对全宇宙逐键查询虽正确，却要 $\mathrm{\Theta }(Ud)$ 时间。