百度面试题：从海量日志中提取访问百度次数最多的IP

前言

这道题目网上到处都是，但是好多都没有讲清楚，然后大家又相互转载，错误泛滥，现在我来完善这道题目。

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

分析

1. 首先解决大文件问题，也就是如何处理100G的一个大文件，这个通常的解决方法就是将大文件分解成许多小文件。我们可以通过对IP地址求hash然后对1024取模将一个100G的大文件分解成1024个小文件（file0,file1......file1023），注意这里的1024个文件并不是平均分的，也就是每个文件大小并不是（100G/1204）。当然我们考虑的时候可以假设文件是平均分的，那么每个文件大小为100M，这样一个100M的文件是可以全部读入大小为1G内存中。这样就解决了第一个文件太大不能一次读入内存的问题。
2. 考虑到ip地址是32为，那么总共有2^32=4G种可能出现的ip地址，每个ip地址出现的次数不确定，这个具体是由100G大文件决定的。对每个小文件进行处理，我们知道前面每个文件中的ip是通过hash(ip)%1024。这样相当于将2^32=4G种ip地址进行了分段，每个文件中可能出现的ip最大范围是4G/1024=4M。创建一个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)。
3. 当我们求出每个文件中出现次数最大的ip地址以后，我们在比较这1024个文件中的那个ip出现次数最大

伪代码实例

Mark for future reference

hash(IP)%N get many small files

int max = 0;
String maxip = null;
for each file
    Hashmap hashmap;
    String IP = readIP(file);
    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);

本文转自xwdreamer博客园博客，原文链接：http://www.cnblogs.com/xwdreamer/archive/2012/05/09/2492603.html，如需转载请自行联系原作者