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

Question

就是 现在有一个log 里面全都是访问者的ip(数据很大很大) 一行一个ip
比如
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
....

怎么查出来访问次数最多的10个IP?

数据量非常大 不可能直接读进来 然后排序。。。

方式：
第一步：
如下读取：
声明一个变量 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
先与蓝色部分为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，123
121，14
121，56
123，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。