问题:
日志文件中, 寻找10个访问量最大的IP地址
类似的变种还有:
1, 搜索引擎搜索记录中, 寻找10个最热门的搜索词;
2, 一个大文件里面, 寻找10个出现频率最高的单词;
3, web proxy的记录里, 寻找前10个访问最多的url;
4, 对搜索引擎的搜索记录按照频率进行排序;
5, 海量数据中, 找到出现频率最高的一个;
这些问题一般都要求数据无法完全放入内存, 要么强调数据有100G, 300G, 要么强调只能用1G内存什么的. 这么要求的目的在于避免被提问者直接走一遍统计一下完事.
解决的思路是divide and conquer, 而divide的办法是对key或者元素进行hash, 然后分治处理. 选择hash的原因在于conquer的时候子问题的解可以得到原问题的解.
以上面的变种3为例, 对数据进行hash, hash的目的在于每个子集可以容纳到内存中, 可以恰当选择hash办法,譬如如果是url的话,可以将url用SHA-1这样的cryptographic hash function进行hash,然后对得到的digest取前面的k个bit. 之后,每个子集分别拉到内存里面进行频率处理, 譬如一个(key, count)的hash_map, 将子集元素走一遍, 得到每个子集里面的靠前的最高频元素.
之后, 前10个最高频元素肯定在各个子集的前10个最高频元素的集合中, 譬如一共分成了3000个子集,那么得到的3000个子集的所有前10个最高频元素(一共3000 * 10 = 30,000个)都扔进一个10个元素的最大小堆过滤一遍即可得到最大的10个. 有点选拔赛的感觉. 之所以每个子集选取前10名，是因为最终的前10名可能出自一个子集.
以上处理其实就是一个典型的map-reduce模型, hash是分解输入数据的办法.
一个类似的问题.
给定a,b两个文件, 各有50亿条url记录, 可用内存4G, 如何找到两个文件中相同的url记录?
仍然是用hash来divide & conquer, 按照某种hash(如取MD5(url)的前若干位)将两个文件拆分分别拆分成多个小文件a1-an, b1-bn. 然后,对于相同hash结果的小文件ai和bi, 都读到内存, 剩下的就随便怎么整了, 譬如构造两个set（基于binary tree、hash、bloom filter等）然后求交集, 参见前面的一篇博文, http://www.cnblogs.com/qsort/archive/2011/05/06/2039201.html
以上是基于hash的一些分治算法, 分治算法的关键在于选择合适的划分策略. 通过hash划分的好处在于同样的元素肯定会被划分到同一个子集里面, 这对统计频率等场景来说是非常合适的.