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

　　解答：

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

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

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

　　hash_map統(tǒng)計(jì)：先對(duì)這批海量數(shù)據(jù)預(yù)處理。

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

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

　　當(dāng)然，你也可以采用trie樹，關(guān)鍵字域存該查詢串出現(xiàn)的次數(shù)，沒有出現(xiàn)為0。最后用10個(gè)元素的最小推來對(duì)出現(xiàn)頻率進(jìn)行排序。