海量日志数据，提取出某日访问百度次数最多的那个IP 博客分类： 面试总结 hadoop

问题：一个的日志文件中存放IP地址，按照访问量对IP地址取访问量最大的IP，内存大小4M

解答：

1.由于内存大小的限制，分而治之

2.IP地址，0.0.0.0 ~ 255.255.255.255 ，

255(10) = 11111111(2)
共 4*8 = 32 bit 表示一个IP地址
每位上共两种变化，所以共  2^32 个不同的IP地址

拆分为1024文件
2^32 / 2^10 = 2^22 = 4M，每份文件中最多存放4M个不同的IP地址 

3.计算IP地址的HASH值

IP.hash % 1024 ，让IP地址落在不同的文件中

计算Hash值再取余，
类比HashMap ，
二次计算Hash值，即将key的hashCode 再进行计算，
是因为

4.在1024个小文件中，计算当前文件中的访问量最高的IP地址，可以使用HashMap的形式

5.再从得出的1024个结果中，选取访问量最高的IP地址

6.使用Hash(IP)%1024的原因
直接分配：即将大文件拆分成1024个小文件，平均分配，按照顺序依次将IP地址放入不同的文件中；缺点，大文件中IP地址是按照实际应用中的顺序存放的，可能存放在分配到不同的文件后，每个文件中都有相同的IP地址；而这些在不同文件中相同的IP地址，又可能不是改文件中数量最多的IP地址；
散列分配：能够保证把相同的IP地址分配到同一个文件中，不会出现统计遗漏的问题或混淆

博文参考：

如何从海量日志中提取访问最多的10个IP
10道Hadoop面试真题及解题思路