一道Java算法类笔试题-大数据排序处理

题目：

如果有一个20g的日志文件，日志文件记录着用户访问过的url，每一行为一个url，给你一台512M的主机，找出出现次数最多的10个url

参考答案及思路：

1. Top K算法：使用堆排序算法＋大顶堆＋10个元素的数组。

2.

• IP地址最多有2^32=4G种取值情况，所以不能完全加载到内存中处理；
• 可以考虑采用“分而治之”的思想，按照IP地址的Hash(IP)%1024值，把海量IP日志分别存储到1024个小文件中。这样，每个小文件最多包含4MB个IP地址；
• 对于每一个小文件，可以构建一个IP为key，出现次数为value的Hash map，同时记录当前出现次数最多的那个IP地址；
• 可以得到1024个小文件中的出现次数最多的IP，再依据常规的排序算法得到总体上出现次数最多的IP；