1. Bloom filter
適用范圍：可以用來實現(xiàn)數(shù)據(jù)字典扫责，進(jìn)行數(shù)據(jù)的判重吃谣，或者集合求交集撕予。
位數(shù)組+k個獨立hash函數(shù)鲫惶。將hash函數(shù)對應(yīng)的值的位數(shù)組置1，查找時如果發(fā)現(xiàn)所有hash函數(shù)對應(yīng)位都是1說明存在实抡，很明顯這個過程并不保證查找的結(jié)果是100%正確的欠母。
給你A,B兩個文件欢策，各存放50億條URL，每條URL占用64字節(jié)赏淌，內(nèi)存限制是4G踩寇，讓你找出A,B文件共同的URL。
若不允許有錯誤率六水，則先hash俺孙，分到1000個小文件中，再得到hash值掷贾，對比每個小文件睛榄，若有相同hash值則說明有相同文件。不對應(yīng)的小文件中不可能有相同文件想帅。
2. hashing
快速查找场靴，刪除的基本數(shù)據(jù)結(jié)構(gòu)，通常需要總數(shù)據(jù)量可以放入內(nèi)存港准。
海量日志數(shù)據(jù)旨剥，提取出某日訪問百度次數(shù)最多的那個IP。
解決方案：mod1000浅缸，得到1000個文件泞边，提取出1000個局部最大值，最后得到全局最大值疗杉。
又如：有一個1G大小的一個文件阵谚，里面每一行是一個詞，詞的大小不超過16字節(jié)烟具，內(nèi)存限制大小是1M梢什。返回頻數(shù)最高的100個詞。
又如：有10個文件朝聋，每個文件1G嗡午，每個文件的每一行存放的都是用戶的query，每個文件的query都可能重復(fù)冀痕。要求你按照query的頻度排序荔睹。
解決方案：先mod，后內(nèi)部排序言蛇，最后歸并排序僻他。
3. bit-map
可進(jìn)行數(shù)據(jù)的快速查找，判重腊尚，刪除吨拗，一般來說數(shù)據(jù)范圍是int的10倍以下。
2.5億個整數(shù)中找出不重復(fù)的整數(shù)的個數(shù)，內(nèi)存空間不足以容納這2.5億個整數(shù)劝篷。
又如：給40億個不重復(fù)的unsigned int的整數(shù)哨鸭，沒排過序的，然后再給一個數(shù)，如何快速判斷這個數(shù)是否在那40億個數(shù)當(dāng)中？
也可用《編程珠璣》里的方法，用二進(jìn)制表示，根據(jù)最高位為0 1 進(jìn)行二分查找哑诊。
4. 堆
海量數(shù)據(jù)前n大，并且n比較小，堆可以放入內(nèi)存 。
100w個數(shù)中找最大的前100個數(shù)仅乓。
5. trie樹
數(shù)據(jù)量大赖舟，重復(fù)多蓬戚，但是數(shù)據(jù)種類小可以放入內(nèi)存。
請你統(tǒng)計最熱門的10個查詢串宾抓，要求使用的內(nèi)存不能超過1G子漩，每個查詢串的長度為1-255字節(jié)。
解決方案：用trie樹存儲石洗，關(guān)鍵字區(qū)域存儲出現(xiàn)次數(shù)幢泼，最后用堆動態(tài)記錄出現(xiàn)次數(shù)最多的10個查詢串。
6. mapreduce
適用范圍：數(shù)據(jù)量大讲衫，但是數(shù)據(jù)種類小可以放入內(nèi)存缕棵。
基本原理及要點：將數(shù)據(jù)交給不同的機器去處理，數(shù)據(jù)劃分涉兽，結(jié)果歸約招驴。
海量數(shù)據(jù)分布在100臺電腦中，想個辦法高效統(tǒng)計出這批數(shù)據(jù)的TOP10枷畏。
首先可以根據(jù)數(shù)據(jù)值或者把數(shù)據(jù)hash后的值别厘，將數(shù)據(jù)按照范圍劃分到不同的機子，最好可以讓數(shù)據(jù)劃分后可以一次讀入內(nèi)存拥诡，這樣不同的機子負(fù)責(zé)處理各種的數(shù)值范圍触趴，實際上就是map。得到結(jié)果后渴肉，各個機子只需拿出各自的出現(xiàn)次數(shù)最多的前N個數(shù)據(jù)冗懦，然后匯總，選出所有的數(shù)據(jù)中出現(xiàn)次數(shù)最多的前N個數(shù)據(jù)仇祭，這實際上就是reduce過程批狐。
經(jīng)典問題分析
上千萬or億數(shù)據(jù)（有重復(fù)），統(tǒng)計其中出現(xiàn)次數(shù)最多的前N個數(shù)據(jù),分兩種情況：可一次讀入內(nèi)存，不可一次讀入嚣艇。
可用思路：trie樹+堆承冰，數(shù)據(jù)庫索引，劃分子集分別統(tǒng)計食零，hash困乒，分布式計算，近似統(tǒng)計贰谣，外排序
所謂的是否能一次讀入內(nèi)存娜搂，實際上應(yīng)該指去除重復(fù)后的數(shù)據(jù)量。如果去重后數(shù)據(jù)可以放入內(nèi)存吱抚，我們可以為數(shù)據(jù)建立字典百宇，比如通過 map，hashmap秘豹，trie携御，然后直接進(jìn)行統(tǒng)計即可。當(dāng)然在更新每條數(shù)據(jù)的出現(xiàn)次數(shù)的時候既绕，我們可以利用一個堆來維護(hù)出現(xiàn)次數(shù)最多的前N個數(shù)據(jù)啄刹，當(dāng)然這樣導(dǎo)致維護(hù)次數(shù)增加，不如完全統(tǒng)計后在求前N大效率高凄贩。
如果數(shù)據(jù)無法放入內(nèi)存誓军。一方面我們可以考慮上面的字典方法能否被改進(jìn)以適應(yīng)這種情形，可以做的改變就是將字典存放到硬盤上疲扎，而不是內(nèi)存昵时，這可以參考數(shù)據(jù)庫的存儲方法。
當(dāng)然還有更好的方法椒丧，就是可以采用分布式計算壹甥，基本上就是map-reduce過程，首先可以根據(jù)數(shù)據(jù)值或者把數(shù)據(jù)hash(md5)后的值瓜挽，將數(shù)據(jù)按照范圍劃分到不同的機子盹廷，最好可以讓數(shù)據(jù)劃分后可以一次讀入內(nèi)存，這樣不同的機子負(fù)責(zé)處理各種的數(shù)值范圍久橙，實際上就是map俄占。得到結(jié)果后，各個機子只需拿出各自的出現(xiàn)次數(shù)最多的前N個數(shù)據(jù)淆衷，然后匯總缸榄，選出所有的數(shù)據(jù)中出現(xiàn)次數(shù)最多的前N個數(shù)據(jù)，這實際上就是reduce過程祝拯。
實際上可能想直接將數(shù)據(jù)均分到不同的機子上進(jìn)行處理甚带，這樣是無法得到正確的解的她肯。因為一個數(shù)據(jù)可能被均分到不同的機子上，而另一個則可能完全聚集到一個機子上鹰贵，同時還可能存在具有相同數(shù)目的數(shù)據(jù)晴氨。比如我們要找出現(xiàn)次數(shù)最多的前100個，我們將1000萬的數(shù)據(jù)分布到10臺機器上碉输，找到每臺出現(xiàn)次數(shù)最多的前 100個籽前，歸并之后這樣不能保證找到真正的第100個，因為比如出現(xiàn)次數(shù)最多的第100個可能有1萬個敷钾，但是它被分到了10臺機子枝哄，這樣在每臺上只有1千個，假設(shè)這些機子排名在1000個之前的那些都是單獨分布在一臺機子上的阻荒，比如有1001個挠锥，這樣本來具有1萬個的這個就會被淘汰，即使我們讓每臺機子選出出現(xiàn)次數(shù)最多的1000個再歸并侨赡，仍然會出錯蓖租，因為可能存在大量個數(shù)為1001個的發(fā)生聚集。因此不能將數(shù)據(jù)隨便均分到不同機子上辆毡，而是要根據(jù)hash 后的值將它們映射到不同的機子上處理菜秦，讓不同的機器處理一個數(shù)值范圍甜害。
而外排序的方法會消耗大量的IO舶掖，效率不會很高。而上面的分布式方法尔店，也可以用于單機版本眨攘，也就是將總的數(shù)據(jù)根據(jù)值的范圍，劃分成多個不同的子文件嚣州，然后逐個處理鲫售。處理完畢之后再對這些單詞的及其出現(xiàn)頻率進(jìn)行一個歸并。實際上就可以利用一個外排序的歸并過程该肴。
另外還可以考慮近似計算情竹，也就是我們可以通過結(jié)合自然語言屬性，只將那些真正實際中出現(xiàn)最多的那些詞作為一個字典匀哄，使得這個規(guī)那匦В可以放入內(nèi)存。
