Skip to content

Latest commit

 

History

History
17 lines (10 loc) · 934 Bytes

find-top-1-ip.md

File metadata and controls

17 lines (10 loc) · 934 Bytes

如何找出某一天访问百度网站最多的 IP?

题目描述

现有海量日志数据保存在一个超大文件中,该文件无法直接读入内存,要求从中提取某天访问百度次数最多的那个 IP。

解答思路

这道题只关心某一天访问百度最多的 IP,因此,可以首先对文件进行一次遍历,把这一天访问百度 IP 的相关信息记录到一个单独的大文件中。接下来采用的方法与上一题一样,大致就是先对 IP 进行哈希映射,接着使用 HashMap 统计重复 IP 的次数,最后计算出重复次数最多的 IP。

注:这里只需要找出出现次数最多的 IP,可以不必使用堆,直接用一个变量 max 即可。

方法总结

  1. 分而治之,进行哈希取余;
  2. 使用 HashMap 统计频数;
  3. 求解最大的 TopN 个,用小顶堆;求解最小的 TopN 个,用大顶堆