核心思想为什么可行草图算法通常基于一些关键的概率论和随机化思想使用随机哈希函数用统计方法估计结果接受小概率误差换取巨大效率提升常见草图算法举例1. HyperLogLog去重计数用于估计集合中“不同元素的数量”空间几 KB能处理数十亿级数据应用网站 UV独立访客数2. Count-Min Sketch频率统计用于估计某个元素出现了多少次支持快速更新有误差但误差可控常用于热门搜索词网络流量分析3. Bloom Filter集合判定判断某个元素“是否可能存在”不会漏判no false negative但可能误判false positive常见应用数据库缓存URL 去重4. Heavy Hitters / Top-K找出最频繁出现的元素常用于热门商品高频 IP草图算法 vs 传统算法特性传统方法草图算法精确性精确近似空间很大很小速度较慢很快是否适合流式数据❌✅回到顶部HyperLogLog核心问题HyperLogLog (HLL) 解决的是基数估计问题在一个大数据集中统计不重复元素的个数即集合的势/cardinality。比如统计一个网站今天有多少不重复的 UV朴素方案是用 HashSet但当数据量达到亿级时内存开销极大。数学基础伯努利试验与最大前导零直觉理解把每个元素哈希成一串二进制观察这串二进制从最高位起连续 0 的个数前导零数量。出现 1 个前导零的概率 1/2出现 2 个前导零的概率 1/4出现 k 个前导零的概率 1/2ᵏ关键推论如果在所有元素中观察到的最大前导零数为 k那么可以估计集合基数大约为2ᵏ。元素哈希值: 00110101... → 前导零数 2 00011010... → 前导零数 3 ← 最大 01010101... → 前导零数 1 最大前导零 k 3 → 估计基数 ≈ 2³ 8核心改进分桶 调和平均单一估计误差很大HLL 的关键优化是① 分桶Stochastic Averaging用哈希值的前 b 位决定放入哪个桶共 m 2ᵇ 个桶其余位用于计算前导零。每个桶独立记录自己遇到的最大前导零数 Mᵢ。哈希值 64 位: [ 前b位 → 桶索引 ][ 剩余位 → 计算前导零 ] |___________| |________________________| 桶选择 计数部分② 调和平均Harmonic Mean最终估计公式E α_m × m² × (Σ 2^(-Mᵢ))⁻¹m 桶的数量Mᵢ 第 i 个桶的最大前导零数α_m 修正常数消除系统性偏差调和平均比算术平均对离群值更鲁棒大幅降低误差。精度与内存桶数 m内存占用标准误差512~0.3 KB4.1%1024~0.6 KB2.9%4096~2.5 KB1.6%16384~10 KB0.8%Redis 的实现固定使用 16384 个桶每个桶 6 bits总共仅需12 KB内存误差率约0.81%却能统计2⁶⁴ 量级的基数。对比一下朴素 HashSet 存 1 亿个 UUID约需1.6 GB。算法流程图适合与不适合的场景适合对精确度要求不高可接受 1% 误差数据量巨大千万、亿级只需要基数不需要枚举具体元素典型UV 统计、独立 IP 计数、去重词汇量统计不适合需要精确数字如账单、订单去重需要查询某元素是否存在用 Bloom Filter数据量本身就很小直接用 Set 更简单更准回到顶部Count-Min SketchCount-Min SketchCMS解决的是另一个经典问题频率估计——在海量数据流中快速估算某个元素出现了多少次。和 HyperLogLog 的关系HyperLogLogCount-Min Sketch问题有多少种不同元素某个元素出现了多少次答案整体基数单个元素频率核心数据结构CMS 是一个d 行 × w 列的二维计数器矩阵配合 d 个独立哈希函数。插入操作每插入一个元素x对 d 个哈希函数分别计算列索引然后对应格子 1对 i 1..d j hᵢ(x) mod w matrix[i][j] 1时间复杂度 O(d)空间 O(d × w)。查询操作查询元素x的频率时读取 d 个格子的值取最小值作为估计freq(x) min over i of matrix[i][hᵢ(x)]为什么取最小值每个格子存的是哈希到同一列的所有元素的总计数。由于哈希碰撞某些格子会被其他元素污染而偏大但不会偏小只增不减。所以 d 行中被污染最少的那行就是最准确的取最小即可。这也解释了 CMS 的误差特性只会高估不会低估。误差上界的数学保证设总插入次数为 N矩阵宽度为 w行数为 d。单行的期望误差某行中元素x的格子被其他元素污染的期望值为 N/w其他元素均匀分散到 w 列。多行取最小d 行独立每行误差超过 ε·N 的概率为 1/e当 w e/ε 时。d 行同时超标的概率为 (1/e)d(1/)。因此设w ⌈e/ε⌉d ⌈ln(1/δ)⌉可以保证P[^f(x)−f(x)ε⋅N]δP[^()−()⋅]参数含义典型值ε允许的相对误差0.011%δ超过误差的概率0.001w e/ε列数≈ 272d ln(1/δ)行数≈ 7内存w × d × 4 bytes≈ 7.6 KB与 HyperLogLog 的搭配使用在实际系统里两者经常组合HyperLogLog → 今天来了多少不同用户基数 Count-Min Sketch → 某个用户今天请求了多少次频率Redis 本身内置了PFADD/PFCOUNTHLL而 CMS 在 Redis 4.0 以上的 RedisBloom 模块中作为CMS.INCRBY/CMS.QUERY提供。典型使用场景热点 TopK 检测结合 min-heap实时维护访问频率最高的 K 个 URL / 商品 / IP内存只需 KB 级别。网络流量监控统计每个 IP 的包频率快速识别 DDoS 攻击中的高频来源。推荐系统去噪用户行为流中过滤掉低频可能是爬虫的操作只保留频率超过阈值的真实行为。数据库查询优化PostgreSQL 的统计模块用类似思路估算列值频率辅助查询计划器选择最优索引。局限性CMS 有两个先天限制值得注意。第一它不支持删除——计数格子只加不减一旦减就可能引入负误差。要支持删除需要改用 Count-Mean-Min Sketch 或 Conservative Update 变体。第二高频元素误差更大——因为热点元素本身就占了 N 中的大部分ε·N 对它反而不那么宽松需要适当加宽 w。回到顶部Heavy Hitters / Top-K1️⃣ 它在解决什么问题Heavy Hitters / Top-K 的目标是找出数据中出现最频繁的元素最“重”的那些比如搜索引擎最热门的搜索词电商最热卖商品网络监控流量最大的 IP核心难点是 数据量巨大 可能是数据流不能全部存下来排序2️⃣ 一个直观例子假设有数据流A, B, A, C, A, B, D, A, B, B统计结果其实是A 4 B 4 C 1 D 1Top-2 A 和 B但问题是 在真实场景中你不能存所有元素再统计3️⃣ 核心思路和 HyperLogLog 很不一样Heavy Hitters 不是“估计总量”而是优先保留“可能很重要的元素”忽略小的本质是用有限空间维护一个“候选排行榜”4️⃣ 经典算法Misra-Gries假设我们只想找 Top-2K2我们最多只保留 K 个候选处理流程一步步我们维护一个小表最多 2 个元素开始{}读 AA:1读 BA:1, B:1读 AA:2, B:1读 C关键步骤表满了已有2个且 C 不在里面➡️ 所有计数 -1A:1, B:0 → 删除B变成A:1后面继续…最终可能得到A:?, B:?它们就是“重元素候选”5️⃣ 为什么这样能找到 Top-K关键直觉高频元素不容易被“抵消掉”出现很多次 → 会不断被加回来低频元素 → 很容易被减掉消失所以最后留下的很可能就是 Heavy Hitters6️⃣ 和 Count-Min Sketch 的区别可以简单对比一下博客很好用方法做什么特点Misra-Gries找 Top-K 候选精简、确定性Count-Min Sketch估计频率有误差但更灵活
