常見的方法有Hash法缝左，位圖法褒链，Bloom-filter法、數(shù)據(jù)庫優(yōu)化法部默、倒排索引法沦疾、外排序法称近、Trie樹、堆哮塞、雙層桶法以及MapReduce法煌茬。
分而治之/hash映射+hash統(tǒng)計+堆/快速/歸并排序（先映射，然后統(tǒng)計彻桃，最后排序）
雙層桶排序（求第K大，中位數(shù)晾蜘，不重復(fù)或重復(fù)的數(shù)字）：通過多次劃分邻眷，逐步確定范圍，最后在一個可以接受的范圍內(nèi)進(jìn)行
Bloom filter（集合求交集剔交、數(shù)據(jù)判重）/BitMap
Trie樹/數(shù)據(jù)庫/倒排索引
外排序
分布式處理之Hadoop/MapReduce
TopK問題（先映射肆饶，然后統(tǒng)計，最后排序）
題目1：假設(shè)目前有一千萬個記錄（這些查詢串的重復(fù)度比較高岖常，雖然總數(shù)是1千萬驯镊，但如果除去重復(fù)后，不超過3百萬個。一個查詢串的重復(fù)度越高板惑，說明查詢它的用戶越多橄镜，也就是越熱門），請你統(tǒng)計最熱門的10個查詢串冯乘，要求使用的內(nèi)存不能超過1G洽胶。
解法：
3百萬*255B=0.75G <1G 可以將所有串放在內(nèi)存中進(jìn)行
Hashmap統(tǒng)計：先對數(shù)據(jù)預(yù)處理，維護(hù)一個key為query串裆馒，value為該query串出現(xiàn)次數(shù)的hashmap姊氓，若該query串在map中，那么將該query串的計數(shù)加一即可喷好，若該query串不在map中翔横，那么加入該query串，并將value設(shè)為1
堆排序：維護(hù)一個K(該題目中是10)大小的小根堆梗搅，然后遍歷300萬的Query禾唁，分別和根元素進(jìn)行對比。
題目2：有一個1G大小的一個文件些膨，里面每一行是一個詞蟀俊，詞的大小不超過16字節(jié)，內(nèi)存限制大小是1M订雾。返回頻數(shù)最高的100個詞肢预。
解法：
(1G/16B):(1M/16B)=2000 可取5000
分而治之/hash映射：順序讀文件中，對于每個詞x洼哎，取hash(x)%5000烫映，然后按照該值存到5000個小文件（記為x0,x1,...x4999）中。這樣每個文件大概是200k左右噩峦。如果其中的有的文件超過了1M大小锭沟，還可以按照類似的方法繼續(xù)往下分，直到分解得到的小文件的大小都不超過1M识补。
Hashmap統(tǒng)計：對每個小文件族淮，采用trie樹/hash_map等統(tǒng)計每個文件中出現(xiàn)的詞以及相應(yīng)的頻率。
堆排序/歸并排序：取出出現(xiàn)頻率最大的100個詞（可以用含100個結(jié)點的最小堆）后凭涂，再把100個詞及相應(yīng)的頻率存入文件祝辣，這樣又得到了5000個文件。最后就是把這5000個文件進(jìn)行歸并（類似于歸并排序）的過程了切油。
題目3：提取某日訪問網(wǎng)站次數(shù)最多的那個IP
解法：
分而治之/hash映射：首先是這一天蝙斜，并且是訪問百度的日志中的IP取出來，逐個寫入到一個大文件中澎胡。注意到IP是32位的孕荠，最多有個2^32個IP娩鹉。同樣可以采用映射的方法，比如%1000稚伍，把整個大文件映射為1000個小文件
Hashmap統(tǒng)計：采用hash_map對那1000個文件中的所有IP進(jìn)行頻率統(tǒng)計
堆/快速排序：進(jìn)行排序(可采取堆排序)弯予，得到次數(shù)最多的IP。
題目4：海量數(shù)據(jù)分布在100臺電腦中槐瑞，想個辦法高效統(tǒng)計出這批數(shù)據(jù)的TOP10熙涤。
解法：
如果每個數(shù)據(jù)元素只出現(xiàn)一次，而且只出現(xiàn)在某一臺機(jī)器中困檩，那么可以采取以下步驟統(tǒng)計出現(xiàn)次數(shù)TOP10的數(shù)據(jù)元素：
堆排序：：在每臺電腦上求出TOP10祠挫，可以采用包含10個元素的堆完成，求出每臺電腦上的TOP10后悼沿，然后把這100臺電腦上的TOP10組合起來等舔，共1000個數(shù)據(jù)，再利用上面類似的方法求出TOP10就可以了糟趾。
如果同一個元素重復(fù)出現(xiàn)在不同的電腦中：遍歷一遍所有數(shù)據(jù)慌植，重新hash取摸，如此使得同一個元素只出現(xiàn)在單獨(dú)的一臺電腦中义郑，然后采用上面所說的方法蝶柿，統(tǒng)計每臺電腦中各個元素的出現(xiàn)次數(shù)找出TOP10，繼而組合100臺電腦上的TOP10非驮，找出最終的TOP10
排序問題
映射之后排序
題目1：有10個文件交汤，每個文件1G，每個文件的每一行存放的都是用戶的query劫笙，每個文件的query都可能重復(fù)芙扎。要求你按照query的頻度排序。
解法：
hash映射：順序讀取10個文件填大，按照hash(query)%10的結(jié)果將query寫入到另外10個文件（記為a0,a1,..a9）中戒洼。這樣新生成的文件每個的大小大約也1G（假設(shè)hash函數(shù)是隨機(jī)的）。
hash_map統(tǒng)計：找一臺內(nèi)存在2G左右的機(jī)器允华，依次對用hash_map(query, query_count)來統(tǒng)計每個query出現(xiàn)的次數(shù)圈浇。
堆/快速/歸并排序：利用快速/堆/歸并排序按照出現(xiàn)次數(shù)進(jìn)行排序，將排序好的query和對應(yīng)的query_cout輸出到文件中靴寂，這樣得到了10個排好序的文件（記為b0,b1,...b10）磷蜀。最后，對這10個文件進(jìn)行歸并排序（內(nèi)排序與外排序相結(jié)合）榨汤。
外排序
題目1：如何給10^7個數(shù)據(jù)量的磁盤文件排序
解法：
(1) 內(nèi)存排序
由于要求的可用內(nèi)存為1MB，那么每次可以在內(nèi)存中對250K的數(shù)據(jù)進(jìn)行排序怎茫，然后將有序的數(shù)寫入硬盤收壕。
那么10M的數(shù)據(jù)需要循環(huán)40次妓灌，最終產(chǎn)生40個有序的文件。
(2) 歸并排序
將每個文件最開始的數(shù)讀入(由于有序蜜宪，所以為該文件最小數(shù))虫埂，存放在一個大小為40的first_data數(shù)組中；
選擇first_data數(shù)組中最小的數(shù)min_data圃验，及其對應(yīng)的文件索引index掉伏；
將first_data數(shù)組中最小的數(shù)寫入文件result，然后更新數(shù)組first_data(根據(jù)index讀取該文件下一個數(shù)代替min_data)澳窑；
判斷是否所有數(shù)據(jù)都讀取完畢斧散，否則返回 (2)。
