如何从海量日志中提取访问次数最多的IP

题目：

每一个ip访问百度，其ip地址都会被记录到后台日志文件中，假设一天的访问日志有100G，求出一天中访问百度次数最多的ip地址，可以使用的内存大小是1G。

分析

首先解决大文件问题，也就是如何处理100G的一个大文件，这个通常的解决方法就是将大文件分解成许多小文件。我们可以通过对IP地址求hash然后对1024取模将一个100G的大文件分解成1024个小文件（file0,file1......file1023），注意这里的1024个文件并不是平均分的，也就是每个文件大小并不是（100G/1204）。当然我们考虑的时候可以假设文件是平均分的，那么每个文件大小为100M，这样一个100M的文件是可以全部读入大小为1G内存中。这样就解决了第一个文件太大不能一次读入内存的问题。

考虑到ip地址是32位，那么总共有2³²=4G种可能出现的ip地址，每个ip地址出现的次数不确定，这个具体是由100G大文件决定的。对每个小文件进行处理，我们知道前面每个文件中的ip是通过hash(ip)%1024。这样相当于将2³²=4G种ip地址进行了分段，每个文件中可能出现的ip最大范围是4G/1024=4M，并且每个文件之间的ip不会出现相同情况。

创建一个hashmap，读取小文件中的每个ip地址，判断hashmap中是否有这个ip，如果没有，这往haspmap中插入一个<ip,1>的键值对，即hashmap.put(ip,1)；如果haspmap中已经存在了这个ip，那么求出这个ip所对应的值count=haspmap.get(ip)，然后往修改这个ip所对应的value，使其数量增加1，即hashmap.set(ip,count+1)。

当我们求出每个文件中出现次数最大的ip地址以后，我们在比较这1024个文件中的那个ip出现次数最大。

hash(IP)%N get many small files

int max = 0;
String maxip = null;
for each file
    Hashmap hashmap;
    　　for each IP in file10     　　if(hashmap.has(IP)) {
        　　int cnt = hashmap.get(IP);
        　　hashmap.set(IP, cnt+1);
        　　if(cnt+1 > max) { 
            　　max = cnt+1;
            　　maxip = IP;
        　　}
    　　}
    　　else hashmap.put(IP, 1);