面试问题：查找出现次数最多的ip

Question

就是 现在有一个log 里面全都是访问者的ip(数据很大很大) 一行一个ip比如123.22.22.187123.22.22.182123.22.21.187123.22.42.187123.23.22.187123.22.22.182121.22.22.182.... 怎么查出来访问次数最多的10个IP? 数据量非常大 不可能直接读进来 然后排序。。。 方式：第一步： 如下读取：声明一个变量 dictionary <string ,long> record123.22.22.187123.22.22.182123.22.21.187123.22.42.187123.23.22.187123.22.22.182121.22.22.182先与蓝色部分为key ，key 出现的次数为value 存在 record中。这样 ，record的最大个数是255个，不算多，更说不上要多少内存。 再来一次大扫除， 使record 剩下 最多的 10 个元素 以这10 个元素为条件，再扫描一次表，把符合条件的数据写到另一个[文件A]中， 第二步：扫描 [文件A] 以下面数据蓝色部分为key ，以出现次数为value 写到 变量 dictionary <string ,long> record 中 123.22.22.187 123.22.22.182 123.22.21.187 123.22.42.187 123.23.22.187 123.22.22.182 121.22.22.182。。。第三步：。。。第四步：。。。就这样，用4 步相同的方法，提出最多的数据：10条， 问题，上面这种方式感觉不行啊，是我没理解吗？？比如说：123，125，196，158，假设这个ip地址出现的次数最多，那么如下，121，123121，14121，56123，125，196，158，123，125，196，158， 如果分段比较次数，那么123，125，196，158， 这个ip在第一步就被淘汰了？

Answer 1

a.b.c.d

先处理a。

所有文件分为多次(比如255次)的读取。

记录然后分别存入255个文件中，分别对应 a (比如1.b.c.d ; 2.b.c.d;)

这样可以得到最大的十个。

接下来处理b。

。。。

最后得到答案。

Answer 2

这类问题可以使用最大-最小堆。

Answer 3

先排序吧，排序之后就好处理了。

Answer 4

这个问题应该需要拆成两部分理解，
1、文件很大读取一次读取效率低
2、找出出现次数最多的前10条记录
问题1：对于大文件读取可以使用java AIO实现方式异步读取文件
问题2：需要扩展LindedList，每次追加记录时先取是否存在记录，有的话就把记录位置往前推（这比较类似于java memcached 缓存算法）

Answer 5

这类问题都有一个相同的思想，“分而治之”。
每个ip相当于一个32位整型数字，遍历所有日志里的ip，按值的范围分成n个文件保存起来（确保每个文件足够小），这样的话相同的ip肯定会被分到同一个文件中；然后逐个处理这n个文件，统计每个文件里出现次数前10的ip；最后从这10*n个ip中得前10。