前言
这道题目网上到处都是,但是好多都没有讲清楚,然后大家又相互转载,错误泛滥,现在我来完善这道题目。
题目:每一个ip访问百度,其ip地址都会被记录到后台日志文件中,假设一天的访问日志有100G,求出一天中访问百度次数最多的ip地址,可以使用的内存大小是1G。
分析
首先解决大文件问题,也就是如何处理100G的一个大文件,这个通常的解决方法就是将大文件分解成许多小文件。我们可以通过对IP地址求hash然后对1024取模将一个100G的大文件分解成1024个小文件(file0,file1......file1023),注意这里的1024个文件并不是平均分的,也就是每个文件大小并不是(100G/1204)。当然我们考虑的时候可以假设文件是平均分的,那么每个文件大小为100M,这样一个100M的文件是可以全部读入大小为1G内存中。这样就解决了第一个文件太大不能一次读入内存的问题。考虑到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)。当我们求出每个文件中出现次数最大的ip地址以后,我们在比较这1024个文件中的那个ip出现次数最大伪代码实例
Mark for future referencehash(IP)%N get many small filesint max = 0;String maxip = null;for each fileHashmap 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);