面试题：寻找热门查询

1000万条记录，每条记录最大为255Byte，那么日志文件最大有2.5G左右，大于1G内存。但是题目中又提到这样的1000万条记录中有许多是重复的，出去重复的话只有300万条记录，存储这样的300万条记录需要0.75G左右的内存，小于1G内存。那么我们可以考虑将这些无重复的记录装入内存，这是我们需要一种数据结构，这种数据结构即能够存储查询串，又能存储查询串的出现次数，我们可以通过hashmap<query,count>来保存。读取文件，创建一个hashmap，如果hashmap中存储了遍历到的query，则修改该query所对应的count值，使其+1；如果hashmap中没有这个query，那么往haspmap中插入<query,1>。这样我们就创建好了一个包含所有query和次数的hashmap。

然后我们创建一个长度为10最大堆MaxHeap（这里应该是最小堆MinHeap，求最多的要用最小堆，求最小的要用最大堆，ps：2012-10-8），最小堆的堆顶元素最小，如果堆顶这个最小的元素都大于其他非堆元素了，那么堆中的其他元素必定大于其他非堆中元素。遍历hashmap，如果MaxHeap未满，那么往MaxHeapMinHeap中插入这个键值对，如果MinHeap满了，则比较遍历到的元素的count值堆顶的count，如果遍历到元素的count大于堆顶count值，删除堆顶元素，插入当前遍历到的元素。遍历完整个hashmap以后，在MaxHeapMinHeap中存储的就是最热门10个查询串。

花了一天时间才写出这道题目的具体代码实现。具体思路前面已经说过了，主要分为以下几步：

首先我们遍历words.txt这个文件，并且创建一个hashmap，其中key就是words.txt中的查询串，而value则是这个查询穿出现的次数。这里通过判断key是否存在，如果不存在则put(key,1);如果存在的话，则先求value=get(key)，然后put(key,value+1)，这里的put相当于是修改value的值。

在构建好hashmap以后，我们需要创建一个最小堆（我们这里有LinkedList实现），假如堆没有满，我们将hashmpa中的元素放入到最小堆中，如果满的话，则比较hashmap中元素的value值与堆顶元素的value值，如果大于堆顶元素的value值，则删除堆顶元素，然后将这个hashmap元素插入到堆中，在调整堆结构，使其满足最小堆结构。

在遍历完hashmap以后，我们的最小堆中保存的元素就是最热门查询。

View Code

1）读取10个文件，按照hash(query)%10的结果将query写到对应的10个文件（file0,file1....file9）中，这样的10个文件不同于原先的10个文件。这样我们就有了10个大小约为1G的文件。任意一个query只会出现在某个文件中。

2）对于1）中获得的10个文件，分别进行如下操作

     - 利用hash_map（query，query_count）来统计每个query出现的次数。

     - 利用堆排序算法对query按照出现次数进行排序。

     - 将排序好的query输出的文件中。

    这样我们就获得了10个文件，每个文件中都是按频率排序好的query。

3）对2）中获得的10个文件进行归并排序，并将最终结果输出到文件中。

注：如果内存比较小，在第1）步中可以增加文件数。

利用hash_map（query，query_count）来统计每个query出现的次数。

创建一个长度为10的堆来保存一个文件中出现次数最多的hash_map（query，query_count），最后将这10个键值对输出到result文件中。

3）通过2）获得的result文件保存着每个文件出现次数最多的10条记录，对其中的100条记录按照query_count进行排序，最后输出query_count最大的10条query。

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