查找最热门查询串的指南

【出自TX面试题】

难度系数：★★★★☆ 被考察系数：★★★★★

题目描述：

搜索引擎会通过日志文件把用户每次检索使用的所有查询串都记录下来，每个查询串的长度为1～255B。

假设目前有1000万个记录（这些查询串的重复度比较高，虽然总数是1000万，但如果除去重复后，不超过300万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门），请统计最热门的10个查询串，要求使用的内存不能超过1GB。

分析与解答：

从题目中可以发现，每个查询串最常为255B，1000万个字符串需要占用2.55GB内存，因此无法把所有的字符串全部读入到内存中处理。对于这类型的题目，分治法是一个非常实用的方法。

方法一：分治法

对字符串设置一个Hash函数，通过这个Hash函数把字符串划分到更多更小的文件中，从而保证每个小文件中的字符串都可以直接被加载到内存中处理，然后求出每个文件中出现次数最多的10个字符串；最后通过一个小顶堆统计出所有文件中出现最多的10个字符串。

从功能角度出发，这种方法是可行的，但是由于需要对文件遍历两遍，而且Hash函数也需要被调用1000万次，所以性能不是很好，针对这道题的特殊性，下面介绍另外一种性能较好的方法。(www.xing528.com)

方法二：hash_map法

虽然字符串的总数比较多，但是字符串的种类不超过300万个，因此可以考虑把所有字符串出现的次数保存在一个hash_map中（键为字符串，值为字符串出现的次数）。hash_map所需要的空间为300万*（255+4）=3MB*259=777M（其中，4表示用来记录字符串出现次数的整数占用4B）。由此可见1G的内存空间是足够用的。基于以上的分析，本题的求解思路为：

（1）遍历字符串，如果字符串在hash_map中不存在，则直接存入hash_map中，键为这个字符串，值为1。如果字符串在hash_map中已经存在了，则把对应的值直接+1。这一步操作的时间复杂度为O（N），其中N为字符串的数量。

（2）在第一步的基础上找出出现频率最高的10个字符串。可以通过小顶堆的方法来完成，遍历hash_map的前10个元素，并根据字符串出现的次数构建一个小顶堆，然后接着遍历hash_map，只要遍历到的字符串的出现次数大于堆顶字符串的出现次数，就用遍历的字符串替换堆顶的字符串，然后把堆调整为小顶堆。

（3）对所有剩余的字符串都遍历一遍，遍历完成后堆中的10个字符串就是出现次数最多的字符串。这一步的时间复杂度为O（Nlog10）。

方法三：trie树法

方法二中使用hash_map来统计每个字符串出现的次数。当这些字符串有大量相同前缀的时候，可以考虑使用trie树来统计字符串出现的次数。可以在树的结点中保存字符串出现的次数，0表示没有出现。具体的实现方法是：在遍历的时候，在trie树中查找，如果找到，则把结点中保存的字符串出现的次数加1，否则为这个字符串构建新的结点，构建完成后把叶子结点中字符串的出现次数设置为1。这样遍历完字符串后就可以知道每个字符串的出现次数，然后通过遍历这个树就可以找出出现次数最多的字符串。

trie树经常被用来统计字符串的出现次数。它的另外一个大的用途就是字符串查找，判断是否有重复的字符串等。