top-k-frequent-ip-in-one-hour
实时输出最近一个小时内访问频率最高的
- 实时输出
- 从当前时间向前数的
1 个小时 QPS 可能会达到10W/s
这道题乍一看很像
其实杀鸡焉用牛刀，这道题用不着上述算法，请听我仔细分析。
-
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 ，单机完全可以存下。 -
同时还要新建一个固定大小为
10 的小根堆，用于存放当前出现次数最大的10 个IP 。堆顶是10 个IP 里频率最小的IP 。 -
每次来一个请求，就把该秒对应的
HashMap 里对应的IP 计数器增1 ，并查询该IP 是否已经在堆中存在，- 如果不存在，则把该
IP 在3600 个HashMap 的计数器加起来，与堆顶IP 的出现次数进行比较，如果大于堆顶元素，则替换掉堆顶元素，如果小于，则什么也不做 - 如果已经存在，则把堆中该
IP 的计数器也增1 ，并调整堆
- 如果不存在，则把该
-
需要有一个后台常驻线程，每过一秒，把最旧的那个
HashMap 销毁，并为当前这一秒新建一个HashMap ，这样维持一个一小时的窗口。 -
每次查询
top 10 的IP 地址时，把堆里10 个IP 地址返回来即可。
以上就是该方案的全部内容。
有的人问，可不可以用
- 第
4 步里，怎么淘汰掉一个小时前的pair 呢？这时候后台线程只能每隔一秒，全量扫描这个HashMap 里的所有pair, 把过期数据删除，这是线性时间复杂度，很慢。 - 这时候
HashMap 里的key 存放的是"IP + 时间" 组合成的字符串，占用内存远远大于一个int 。而前面的方案，不用存真正的时间，只需要开一个3600 长度的数组来表示一个小时时间窗口。