HeavyKeeper 算法

HeavyKeeper 是一种用于在数据流中高效检测重频元素（Heavy Hitters）的概率算法。它适合处理高速、高频、内存受限场景，如网络流量监控、日志分析、推荐系统等。

📌 核心目标

从一个连续到达的数据流中，估计频率最高的前-K个元素，在不可能存储所有元素及其精确频率的情况下，HeavyKeeper 提供了一个近似但效果优秀的方案。

🧠 算法原理

1. 数据结构（类似 Count-Min Sketch）

HeavyKeeper 使用一个二维数组（通常是 w × d）来保存计数信息，其中：

• w 是桶的宽度（列数）
• d 是哈希函数数量（行数）

每个桶保存一个 (item, counter) 对。
每次输入一个元素，通过 d 个哈希函数映射到 d 个桶，每个桶处理一次更新逻辑。

2. 更新策略（带有衰减）

设：

• item 是当前元素
• counter 是桶中已有的计数值
• item_bucket 是桶中的已有元素

更新步骤：

1. 对于每个哈希函数 hi：
   • 计算哈希位置：pos = hi(item)
   • 如果 item_bucket == item：
     • counter++
   • 否则：
     • 以概率 b^(-counter)（其中 b > 1，如 1.08）进行“衰减”：
       • 有可能将当前桶替换为新元素，并把 counter 初始化为 1

这种概率衰减机制允许频繁出现的元素保留它们的位置，偶尔出现的元素容易被踢出

⏱ 查询方式

要查询某个元素的频率估计值，只需通过相同的 d 个哈希函数，找到所有包含该元素的桶的计数值，取其中的最大值（或中位数）作为估计值。

🎯 特点

特性	说明
空间效率高	只需 w × d 大小
支持删除（可扩展）	可结合 Time Decay 或 TTL 实现
误差可控	高频元素估计误差小，低频元素容易被挤掉
适合 Top-K 查询	常与小顶堆结合

🔧 示例参数

w = 1000      // 宽度
d = 4         // 哈希函数数量
b = 1.08      // 衰减基数（> 1）

🧪 应用示例

• CDN 热门资源监控：识别最常访问的 URL
• 推荐系统：捕捉用户高频交互物品
• DDoS 检测：检测访问频率最高的 IP
• 日志处理：找出最频繁的错误代码