top-k-frequent-ip-in-one-hour

实时输出最近一个小时内访问频率最高的 10 个 IP，要求：

• 实时输出
• 从当前时间向前数的 1 个小时
• QPS 可能会达到 10W/s

这道题乍一看很像Top K 频繁项，是不是需要 Lossy Count 或 Count-Min Sketch 之类的算法呢？

其实杀鸡焉用牛刀，这道题用不着上述算法，请听我仔细分析。

1. QPS 是 10 万/秒，即一秒内最高有 10 万个请求，那么一个小时内就有 100000*3600=360000000≈$$2^{28.4}$$，向上取整，大概是 $$2^{29}$$个请求，也不是很大。我们在内存中建立 3600 个HashMap<Int,Int>，放在一个数组里，每秒对应一个 HashMap，IP 地址为 key, 出现次数作为 value。这样，一个小时内最多有$$2^{29}$$个 pair，每个 pair 占 8 字节，总内存大概是 $$2^{29} \times 8=2^{32}$$字节，即 4GB，单机完全可以存下。

2. 同时还要新建一个固定大小为 10 的小根堆，用于存放当前出现次数最大的 10 个 IP。堆顶是 10 个 IP 里频率最小的 IP。

3. 每次来一个请求，就把该秒对应的 HashMap 里对应的 IP 计数器增 1，并查询该 IP 是否已经在堆中存在，

   • 如果不存在，则把该 IP 在 3600 个 HashMap 的计数器加起来，与堆顶 IP 的出现次数进行比较，如果大于堆顶元素，则替换掉堆顶元素，如果小于，则什么也不做
   • 如果已经存在，则把堆中该 IP 的计数器也增 1，并调整堆

4. 需要有一个后台常驻线程，每过一秒，把最旧的那个 HashMap 销毁，并为当前这一秒新建一个 HashMap，这样维持一个一小时的窗口。

5. 每次查询 top 10 的 IP 地址时，把堆里 10 个 IP 地址返回来即可。

以上就是该方案的全部内容。

有的人问，可不可以用"IP + 时间"作为 key, 把所有 pair 放在单个 HashMap 里？如果把所有数据放在一个 HashMap 里，有两个巨大的缺点，

• 第 4 步里，怎么淘汰掉一个小时前的 pair 呢？这时候后台线程只能每隔一秒，全量扫描这个 HashMap 里的所有 pair,把过期数据删除，这是线性时间复杂度，很慢。
• 这时候 HashMap 里的 key 存放的是"IP + 时间"组合成的字符串，占用内存远远大于一个 int。而前面的方案，不用存真正的时间，只需要开一个 3600 长度的数组来表示一个小时时间窗口。