扫码关注微信公众号
回复“面试手册”，获取本站PDF版
回复“简历”，获取高质量简历模板
回复“加群”，加入程序员交流群
回复“电子书”，获取程序员类电子书
实时输出最近一个小时内访问频率最高的10个IP，要求：
- 实时输出
- 从当前时间向前数的1个小时
- QPS可能会达到10W/s
这道题乍一看很像Top K 频繁项，是不是需要 Lossy Count 或 Count-Min Sketch 之类的算法呢？
其实杀鸡焉用牛刀，这道题用不着上述算法，请听我仔细分析。
- 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地址返回来即可。
以上就是该方案的全部内容。
有的人问，可不可以用”IP + 时间”作为key, 把所有pair放在单个HashMap里？如果把所有数据放在一个HashMap里，有两个巨大的缺点，
- 第4步里，怎么淘汰掉一个小时前的pair呢？这时候后台线程只能每隔一秒，全量扫描这个HashMap里的所有pair,把过期数据删除，这是线性时间复杂度，很慢。
- 这时候HashMap里的key存放的是”IP + 时间”组合成的字符串，占用内存远远大于一个int。而前面的方案，不用存真正的时间，只需要开一个3600长度的数组来表示一个小时时间窗口。
本站链接：https://www.mianshi.online，如需勘误或投稿，请联系微信：lurenzhang888
点击面试手册，获取本站面试手册PDF完整版