1. Bloom filter

適用范圍：可以用來實(shí)現(xiàn)數(shù)據(jù)字典，進(jìn)行數(shù)據(jù)的判重，或者集合求交集。
位數(shù)組+k個(gè)獨(dú)立hash函數(shù)。將hash函數(shù)對應(yīng)的值的位數(shù)組置1，查找時(shí)如果發(fā)現(xiàn)所有hash函數(shù)對應(yīng)位都是1說明存在，很明顯這個(gè)過程并不保證查找的結(jié)果是100%正確的。

給你A,B兩個(gè)文件，各存放50億條URL，每條URL占用64字節(jié)，內(nèi)存限制是4G，讓你找出A,B文件共同的URL。
若不允許有錯(cuò)誤率，則先hash，分到1000個(gè)小文件中，再得到hash值，對比每個(gè)小文件，若有相同hash值則說明有相同文件。不對應(yīng)的小文件中不可能有相同文件。

2. hashing

快速查找，刪除的基本數(shù)據(jù)結(jié)構(gòu)，通常需要總數(shù)據(jù)量可以放入內(nèi)存。

海量日志數(shù)據(jù)，提取出某日訪問百度次數(shù)最多的那個(gè)IP。
解決方案：mod1000，得到1000個(gè)文件，提取出1000個(gè)局部最大值，最后得到全局最大值。
又如：有一個(gè)1G大小的一個(gè)文件，里面每一行是一個(gè)詞，詞的大小不超過16字節(jié)，內(nèi)存限制大小是1M。返回頻數(shù)最高的100個(gè)詞。
又如：有10個(gè)文件，每個(gè)文件1G，每個(gè)文件的每一行存放的都是用戶的query，每個(gè)文件的query都可能重復(fù)。要求你按照query的頻度排序。
解決方案：先mod，后內(nèi)部排序，最后歸并排序。

3. bit-map

可進(jìn)行數(shù)據(jù)的快速查找，判重，刪除，一般來說數(shù)據(jù)范圍是int的10倍以下。

2.5億個(gè)整數(shù)中找出不重復(fù)的整數(shù)的個(gè)數(shù)，內(nèi)存空間不足以容納這2.5億個(gè)整數(shù)。
又如：給40億個(gè)不重復(fù)的unsigned int的整數(shù)，沒排過序的，然后再給一個(gè)數(shù)，如何快速判斷這個(gè)數(shù)是否在那40億個(gè)數(shù)當(dāng)中？
也可用《編程珠璣》里的方法，用二進(jìn)制表示，根據(jù)最高位為0 1 進(jìn)行二分查找。

4. 堆

海量數(shù)據(jù)前n大，并且n比較小，堆可以放入內(nèi)存 。

100w個(gè)數(shù)中找最大的前100個(gè)數(shù)。

5. trie樹

數(shù)據(jù)量大，重復(fù)多，但是數(shù)據(jù)種類小可以放入內(nèi)存。

請你統(tǒng)計(jì)最熱門的10個(gè)查詢串，要求使用的內(nèi)存不能超過1G，每個(gè)查詢串的長度為1-255字節(jié)。
解決方案：用trie樹存儲(chǔ)，關(guān)鍵字區(qū)域存儲(chǔ)出現(xiàn)次數(shù)，最后用堆動(dòng)態(tài)記錄出現(xiàn)次數(shù)最多的10個(gè)查詢串。

6. mapreduce

適用范圍：數(shù)據(jù)量大，但是數(shù)據(jù)種類小可以放入內(nèi)存。
基本原理及要點(diǎn)：將數(shù)據(jù)交給不同的機(jī)器去處理，數(shù)據(jù)劃分，結(jié)果歸約。

海量數(shù)據(jù)分布在100臺(tái)電腦中，想個(gè)辦法高效統(tǒng)計(jì)出這批數(shù)據(jù)的TOP10。
首先可以根據(jù)數(shù)據(jù)值或者把數(shù)據(jù)hash后的值，將數(shù)據(jù)按照范圍劃分到不同的機(jī)子，最好可以讓數(shù)據(jù)劃分后可以一次讀入內(nèi)存，這樣不同的機(jī)子負(fù)責(zé)處理各種的數(shù)值范圍，實(shí)際上就是map。得到結(jié)果后，各個(gè)機(jī)子只需拿出各自的出現(xiàn)次數(shù)最多的前N個(gè)數(shù)據(jù)，然后匯總，選出所有的數(shù)據(jù)中出現(xiàn)次數(shù)最多的前N個(gè)數(shù)據(jù)，這實(shí)際上就是reduce過程。

經(jīng)典問題分析

上千萬or億數(shù)據(jù)（有重復(fù)），統(tǒng)計(jì)其中出現(xiàn)次數(shù)最多的前N個(gè)數(shù)據(jù),分兩種情況：可一次讀入內(nèi)存，不可一次讀入。
可用思路：trie樹+堆，數(shù)據(jù)庫索引，劃分子集分別統(tǒng)計(jì)，hash，分布式計(jì)算，近似統(tǒng)計(jì)，外排序
所謂的是否能一次讀入內(nèi)存，實(shí)際上應(yīng)該指去除重復(fù)后的數(shù)據(jù)量。如果去重后數(shù)據(jù)可以放入內(nèi)存，我們可以為數(shù)據(jù)建立字典，比如通過 map，hashmap，trie，然后直接進(jìn)行統(tǒng)計(jì)即可。當(dāng)然在更新每條數(shù)據(jù)的出現(xiàn)次數(shù)的時(shí)候，我們可以利用一個(gè)堆來維護(hù)出現(xiàn)次數(shù)最多的前N個(gè)數(shù)據(jù)，當(dāng)然這樣導(dǎo)致維護(hù)次數(shù)增加，不如完全統(tǒng)計(jì)后在求前N大效率高。
如果數(shù)據(jù)無法放入內(nèi)存。一方面我們可以考慮上面的字典方法能否被改進(jìn)以適應(yīng)這種情形，可以做的改變就是將字典存放到硬盤上，而不是內(nèi)存，這可以參考數(shù)據(jù)庫的存儲(chǔ)方法。
當(dāng)然還有更好的方法，就是可以采用分布式計(jì)算，基本上就是map-reduce過程，首先可以根據(jù)數(shù)據(jù)值或者把數(shù)據(jù)hash(md5)后的值，將數(shù)據(jù)按照范圍劃分到不同的機(jī)子，最好可以讓數(shù)據(jù)劃分后可以一次讀入內(nèi)存，這樣不同的機(jī)子負(fù)責(zé)處理各種的數(shù)值范圍，實(shí)際上就是map。得到結(jié)果后，各個(gè)機(jī)子只需拿出各自的出現(xiàn)次數(shù)最多的前N個(gè)數(shù)據(jù)，然后匯總，選出所有的數(shù)據(jù)中出現(xiàn)次數(shù)最多的前N個(gè)數(shù)據(jù)，這實(shí)際上就是reduce過程。
實(shí)際上可能想直接將數(shù)據(jù)均分到不同的機(jī)子上進(jìn)行處理，這樣是無法得到正確的解的。因?yàn)橐粋€(gè)數(shù)據(jù)可能被均分到不同的機(jī)子上，而另一個(gè)則可能完全聚集到一個(gè)機(jī)子上，同時(shí)還可能存在具有相同數(shù)目的數(shù)據(jù)。比如我們要找出現(xiàn)次數(shù)最多的前100個(gè)，我們將1000萬的數(shù)據(jù)分布到10臺(tái)機(jī)器上，找到每臺(tái)出現(xiàn)次數(shù)最多的前 100個(gè)，歸并之后這樣不能保證找到真正的第100個(gè)，因?yàn)楸热绯霈F(xiàn)次數(shù)最多的第100個(gè)可能有1萬個(gè)，但是它被分到了10臺(tái)機(jī)子，這樣在每臺(tái)上只有1千個(gè)，假設(shè)這些機(jī)子排名在1000個(gè)之前的那些都是單獨(dú)分布在一臺(tái)機(jī)子上的，比如有1001個(gè)，這樣本來具有1萬個(gè)的這個(gè)就會(huì)被淘汰，即使我們讓每臺(tái)機(jī)子選出出現(xiàn)次數(shù)最多的1000個(gè)再歸并，仍然會(huì)出錯(cuò)，因?yàn)榭赡艽嬖诖罅總€(gè)數(shù)為1001個(gè)的發(fā)生聚集。因此不能將數(shù)據(jù)隨便均分到不同機(jī)子上，而是要根據(jù)hash 后的值將它們映射到不同的機(jī)子上處理，讓不同的機(jī)器處理一個(gè)數(shù)值范圍。
而外排序的方法會(huì)消耗大量的IO，效率不會(huì)很高。而上面的分布式方法，也可以用于單機(jī)版本，也就是將總的數(shù)據(jù)根據(jù)值的范圍，劃分成多個(gè)不同的子文件，然后逐個(gè)處理。處理完畢之后再對這些單詞的及其出現(xiàn)頻率進(jìn)行一個(gè)歸并。實(shí)際上就可以利用一個(gè)外排序的歸并過程。
另外還可以考慮近似計(jì)算，也就是我們可以通過結(jié)合自然語言屬性，只將那些真正實(shí)際中出現(xiàn)最多的那些詞作為一個(gè)字典，使得這個(gè)規(guī)模可以放入內(nèi)存。