原題：搜索引擎會通過日志文件把用戶每次檢索使用的所有檢索串都記錄下來，每個查詢串的長度為1-255字節。假設目前有一千萬個記錄(這些查詢串的重復度比較高，雖然總數是1千萬，但如果除去重復后，不超過3百萬個。一個查詢串的重復度越高，說明查詢它的用戶越多，也就是越熱門)，請你統計最熱門的10個查詢串，要求使用的內存不能超過1G。

　　解答：

　　由上面第1題，我們知道，數據大則劃為小的，如如一億個Ip求Top 10，可先%1000將ip分到1000個小文件中去，并保證一種ip只出現在一個文件中，再對每個小文件中的ip進行hashmap計數統計并按數量排序，最后歸并或者最小堆依次處理每個小文件的top10以得到最后的結。

　　但如果數據規模比較小，能一次性裝入內存呢?比如這第2題，雖然有一千萬個Query，但是由于重復度比較高，因此事實上只有300萬的Query，每個Query255Byte，因此我們可以考慮把他們都放進內存中去(300萬個字符串假設沒有重復，都是最大長度，那么最多占用內存3M*1K/4=0.75G。所以可以將所有字符串都存放在內存中進行處理)，而現在只是需要一個合適的數據結構，在這里，HashTable絕對是我們優先的選擇。

　　所以我們放棄分而治之/hash映射的步驟，直接上hash統計，然后排序。So，針對此類典型的TOP K問題，采取的對策往往是: hashmap + 堆。如下所示：

　　hash_map統計：先對這批海量數據預處理。

　　具體方法是：維護一個Key為Query字串，Value為該Query出現次數的HashTable，即hash_map(Query，Value)，每次讀取一個Query，如果該字串不在Table中，那么加入該字串，并且將Value值設為1;如果該字串在Table中，那么將該字串的計數加一即可。最終我們在O(N)的時間復雜度內用Hash表完成了統計;堆排序: 第二步、借助堆這個數據結構，找出Top K，時間復雜度為N‘logK。即借助堆結構，我們可以在log量級的時間內查找和調整/移動。因此，維護一個K(該題目中是10)大小的小根堆，然后遍歷300萬的Query，分別和根元素進行對比。所以，我們最終的時間復雜度是: O(N) + N' * O(logK)，(N為1000萬，N’為300萬)。

　　別忘了這篇文章中所述的堆排序思路: “維護k個元素的最小堆，即用容量為k的最小堆存儲最先遍歷到的k個數，并假設它們即是最大的k個數，建堆費時O(k)，并調整堆(費時O(logk))后，有k1>k2>...kmin(kmin設為小頂堆中最小元素)。繼續遍歷數列，每次遍歷一個元素x，與堆頂元素比較，若x>kmin，則更新堆(x入堆，用時logk)，否則不更新堆。這樣下來，總費時O(k*logk+(n-k)logk)=O(nlogk)。此方法得益于在堆中，查找等各項操作時間復雜度均為logk。”--第三章續、Top K算法問題的實現。

　　當然，你也可以采用trie樹，關鍵字域存該查詢串出現的次數，沒有出現為0。最后用10個元素的最小推來對出現頻率進行排序。