大數(shù)據(jù)常見(jiàn)處理方法總結(jié)

1、海量數(shù)據(jù)處理常用思路和方法大數(shù)據(jù)量，海量數(shù)據(jù)處理方法總結(jié)最近有點(diǎn)忙，稍微空閑下來(lái)，發(fā)篇總結(jié)貼。大數(shù)據(jù)量的問(wèn)題是很多面試筆試中經(jīng)常出現(xiàn)的問(wèn)題，比如baidu google騰訊這樣的一些涉及到海量數(shù)據(jù)的公司經(jīng)常會(huì)問(wèn)到。下面的方法是我對(duì)海量數(shù)據(jù)的處理方法進(jìn)行了一個(gè)一般性的總結(jié)，當(dāng)然這些方法可能并不能完全覆蓋所有的問(wèn)題，但是這樣的一些方法也基本可以處理絕大多數(shù)遇到的問(wèn)題。下面的一些問(wèn)題基本直接來(lái)源于公司的面試筆試題目，方法不一定最優(yōu)，如果你有更好的處理方法，歡迎與我討論。1.Bloom filter適用范圍：可以用來(lái)實(shí)現(xiàn)數(shù)據(jù)字典，進(jìn)行數(shù)據(jù)的判重，或者集合求交集基本原理及要點(diǎn)：對(duì)于原理來(lái)說(shuō)很簡(jiǎn)單，位數(shù)組

2、+k 個(gè)獨(dú)立 hash 函數(shù)。將 hash 函數(shù)對(duì)應(yīng)的值的位數(shù)組置1，查找時(shí)如果發(fā)現(xiàn)所有 hash 函數(shù)對(duì)應(yīng)位都是1 說(shuō)明存在， 很明顯這個(gè)過(guò)程并不保證查找的結(jié)果是100%正確的。同時(shí)也不支持刪除一個(gè)已經(jīng)插入的關(guān)鍵字，因?yàn)樵撽P(guān)鍵字對(duì)應(yīng)的位會(huì)牽動(dòng)到其他的關(guān)鍵字。所以一個(gè)簡(jiǎn)單的改進(jìn)就是counting Bloom filter ，用一個(gè) counter 數(shù)組代替位數(shù)組，就可以支持刪除了。還有一個(gè)比較重要的問(wèn)題，如何根據(jù)輸入元素個(gè)數(shù)n ，確定位數(shù)組 m 的大小及 hash 函數(shù)個(gè)數(shù)。當(dāng) hash 函數(shù)個(gè)數(shù) k=(ln2)*(m/n) 時(shí)錯(cuò)誤率最小。在錯(cuò)誤率不大于E 的情況下， m 至少要等于 n*l

3、g(1/E) 才能表示任意n 個(gè)元素的集合。 但 m 還應(yīng)該更大些， 因?yàn)檫€要保證bit 數(shù)組里至少一半為 0，則 m 應(yīng)該 =nlg(1/E)*lge大概就是 nlg(1/E)1.44 倍(lg 表示以 2 為底的對(duì)數(shù) ) 。舉個(gè)例子我們假設(shè)錯(cuò)誤率為0.01 ，則此時(shí)m 應(yīng)大概是n 的 13 倍。這樣k 大概是 8 個(gè)。注意這里 m 與 n 的單位不同， m 是 bit 為單位，而 n 則是以元素個(gè)數(shù)為單位( 準(zhǔn)確的說(shuō)是不同元素的個(gè)數(shù)) 。通常單個(gè)元素的長(zhǎng)度都是有很多bit 的。所以使用bloom filter內(nèi)存上通常都是節(jié)省的。擴(kuò)展：Bloom filter 將集合中的元素映射到位數(shù)組中

4、，用k（ k 為哈希函數(shù)個(gè)數(shù)）個(gè)映射位是否全1表示元素在不在這個(gè)集合中。 Counting bloom filter （ CBF）將位數(shù)組中的每一位擴(kuò)展為一個(gè)counter ，從而支持了元素的刪除操作。 Spectral Bloom Filter （SBF）將其與集合元素的出現(xiàn)次數(shù)關(guān)聯(lián)。SBF 采用 counter中的最小值來(lái)近似表示元素的出現(xiàn)頻率。問(wèn)題實(shí)例：給你 A,B 兩個(gè)文件，各存放50 億條 URL，每條 URL 占用 64 字節(jié)，內(nèi)存限制是4G，讓你找出A,B 文件共同的 URL。如果是三個(gè)乃至n 個(gè)文件呢？根據(jù)這個(gè)問(wèn)題我們來(lái)計(jì)算下內(nèi)存的占用，4G=232大概是 40 億*8 大概是

5、 340 億， n=50 億，如果按出錯(cuò)率 0.01 算需要的大概是 650 億個(gè) bit ?，F(xiàn)在可用的是 340 億，相差并不多，這樣可能會(huì)使出錯(cuò)率上升些。另外如果這些 urlip 是一一對(duì)應(yīng)的，就可以轉(zhuǎn)換成 ip，則大大簡(jiǎn)單了。2.Hashing適用范圍：快速查找，刪除的基本數(shù)據(jù)結(jié)構(gòu)，通常需要總數(shù)據(jù)量可以放入內(nèi)存基本原理及要點(diǎn)：hash 函數(shù)選擇，針對(duì)字符串，整數(shù)，排列，具體相應(yīng)的hash 方法。碰撞處理，一種是 open hashing ，也稱為拉鏈法；另一種就是closed hashing ，也稱開(kāi)地址法， openedaddressing 。擴(kuò)展：d-left hashing 中的

6、d 是多個(gè)的意思，我們先簡(jiǎn)化這個(gè)問(wèn)題，看一看2-left hashing。2-left hashing 指的是將一個(gè)哈希表分成長(zhǎng)度相等的兩半，分別叫做T1 和 T2，給 T1和 T2分別配備一個(gè)哈希函數(shù)， h1 和 h2 。在存儲(chǔ)一個(gè)新的 key 時(shí)，同時(shí)用兩個(gè)哈希函數(shù)進(jìn)行計(jì)算，得出兩個(gè)地址h1key 和 h2key 。這時(shí)需要檢查T1 中的 h1key 位置和 T2 中的 h2key 位置，哪一個(gè)位置已經(jīng)存儲(chǔ)的（有碰撞的）key 比較多，然后將新key 存儲(chǔ)在負(fù)載少的位置。如果兩邊一樣多，比如兩個(gè)位置都為空或者都存儲(chǔ)了一個(gè)key ，就把新 key 存儲(chǔ)在左邊的T1 子表中， 2-left 也

7、由此而來(lái)。 在查找一個(gè)key 時(shí)，必須進(jìn)行兩次hash ，同時(shí)查找兩個(gè)位置。問(wèn)題實(shí)例：1). 海量日志數(shù)據(jù)，提取出某日訪問(wèn)百度次數(shù)最多的那個(gè)IP 。IP 的數(shù)目還是有限的，最多232個(gè)，所以可以考慮使用hash 將 ip 直接存入內(nèi)存，然后進(jìn)行統(tǒng)計(jì)。3.bit-map適用范圍：可進(jìn)行數(shù)據(jù)的快速查找，判重，刪除，一般來(lái)說(shuō)數(shù)據(jù)范圍是int 的 10 倍以下基本原理及要點(diǎn)：使用bit 數(shù)組來(lái)表示某些元素是否存在，比如8 位電話號(hào)碼擴(kuò)展： bloom filter可以看做是對(duì)bit-map 的擴(kuò)展問(wèn)題實(shí)例：1) 已知某個(gè)文件內(nèi)包含一些電話號(hào)碼，每個(gè)號(hào)碼為8 位數(shù)字，統(tǒng)計(jì)不同號(hào)碼的個(gè)數(shù)。8 位最多 99

8、 999 999 ，大概需要99m 個(gè) bit ，大概 10 幾 m 字節(jié)的內(nèi)存即可。2)2.5億個(gè)整數(shù)中找出不重復(fù)的整數(shù)的個(gè)數(shù)，內(nèi)存空間不足以容納這2.5 億個(gè)整數(shù)。將 bit-map 擴(kuò)展一下，用2bit 表示一個(gè)數(shù)即可，0 表示未出現(xiàn)， 1 表示出現(xiàn)一次，或者我們不用2bit 來(lái)進(jìn)行表示，我們用兩個(gè)bit-map 即可模擬實(shí)現(xiàn)這個(gè)2bit-map2 表示出現(xiàn)。2 次及以上。4. 堆適用范圍：海量數(shù)據(jù)前n 大，并且 n 比較小，堆可以放入內(nèi)存基本原理及要點(diǎn)：最大堆求前n 小，最小堆求前n 大。方法，比如求前n 小，我們比較當(dāng)前元素與最大堆里的最大元素，如果它小于最大元素，則應(yīng)該替換那個(gè)最大

9、元素。這樣最后得到的n 個(gè)元素就是最小的n個(gè)。適合大數(shù)據(jù)量，求前n 小， n 的大小比較小的情況，這樣可以掃描一遍即可得到所有的前n 元素，效率很高。擴(kuò)展：雙堆，一個(gè)最大堆與一個(gè)最小堆結(jié)合，可以用來(lái)維護(hù)中位數(shù)。問(wèn)題實(shí)例：1)100w 個(gè)數(shù)中找最大的前100 個(gè)數(shù)。用一個(gè) 100 個(gè)元素大小的最小堆即可。5. 雙層桶劃分 - 其實(shí)本質(zhì)上就是【 分而治之 】的思想，重在 “分 ”的技巧上！適用范圍：第 k 大，中位數(shù)，不重復(fù)或重復(fù)的數(shù)字基本原理及要點(diǎn)：因?yàn)樵胤秶艽?，不能利用直接尋址表，所以通過(guò)多次劃分，逐步確定范圍，然后最后在一個(gè)可以接受的范圍內(nèi)進(jìn)行。可以通過(guò)多次縮小，雙層只是一個(gè)例子。擴(kuò)展：

10、問(wèn)題實(shí)例：1).2.5 億個(gè)整數(shù)中找出不重復(fù)的整數(shù)的個(gè)數(shù)，內(nèi)存空間不足以容納這2.5 億個(gè)整數(shù)。有點(diǎn)像鴿巢原理，整數(shù)個(gè)數(shù)為232, 也就是，我們可以將這232 個(gè)數(shù)，劃分為28 個(gè)區(qū)域 ( 比如用單個(gè)文件代表一個(gè)區(qū)域 ) ，然后將數(shù)據(jù)分離到不同的區(qū)域，然后不同的區(qū)域在利用 bitmap 就可以直接解決了。也就是說(shuō)只要有足夠的磁盤空間，就可以很方便的解決。2).5 億個(gè) int 找它們的中位數(shù)。這個(gè)例子比上面那個(gè)更明顯。 首先我們將 int 劃分為 216 個(gè)區(qū)域，然后讀取數(shù)據(jù)統(tǒng)計(jì)落到各個(gè)區(qū)域里的數(shù)的個(gè)數(shù)，之后我們根據(jù)統(tǒng)計(jì)結(jié)果就可以判斷中位數(shù)落到那個(gè)區(qū)域，同時(shí)知道這個(gè)區(qū)域中的第幾大數(shù)剛好是中位數(shù)

11、。然后第二次掃描我們只統(tǒng)計(jì)落在這個(gè)區(qū)域中的那些數(shù)就可以了。實(shí)際上，如果不是 int 是 int64 ，我們可以經(jīng)過(guò)3 次這樣的劃分即可降低到可以接受的程度。即可以先將int64分成 224 個(gè)區(qū)域，然后確定區(qū)域的第幾大數(shù)，在將該區(qū)域分成220個(gè)子區(qū)域，然后確定是子區(qū)域的第幾大數(shù)，然后子區(qū)域里的數(shù)的個(gè)數(shù)只有220 ，就可以直接利用direct addr table進(jìn)行統(tǒng)計(jì)了。6. 數(shù)據(jù)庫(kù)索引適用范圍：大數(shù)據(jù)量的增刪改查基本原理及要點(diǎn)：利用數(shù)據(jù)的設(shè)計(jì)實(shí)現(xiàn)方法，對(duì)海量數(shù)據(jù)的增刪改查進(jìn)行處理。擴(kuò)展：?jiǎn)栴}實(shí)例：7. 倒排索引 (Inverted index)適用范圍：搜索引擎，關(guān)鍵字查詢基本原理及要點(diǎn)：

12、為何叫倒排索引？一種索引方法，被用來(lái)存儲(chǔ)在全文搜索下某個(gè)單詞在一個(gè)文檔或者一組文檔中的存儲(chǔ)位置的映射。以英文為例，下面是要被索引的文本：T0 = it is what it isT1 = what is itT2 = it is a banana我們就能得到下面的反向文件索引：a:2banana: 2is:0, 1, 2it:0, 1, 2what:0, 1檢索的條件 what, is和 it將對(duì)應(yīng)集合的交集。正向索引開(kāi)發(fā)出來(lái)用來(lái)存儲(chǔ)每個(gè)文檔的單詞的列表。正向索引的查詢往往滿足每個(gè)文檔有序頻繁的全文查詢和每個(gè)單詞在校驗(yàn)文檔中的驗(yàn)證這樣的查詢。在正向索引中，文檔占據(jù)了中心的位置，每個(gè)文檔指向了一

13、個(gè)它所包含的索引項(xiàng)的序列。也就是說(shuō)文檔指向了它包含的那些單詞，而反向索引則是單詞指向了包含它的文檔，很容易看到這個(gè)反向的關(guān)系。擴(kuò)展：?jiǎn)栴}實(shí)例：文檔檢索系統(tǒng)，查詢那些文件包含了某單詞，比如常見(jiàn)的學(xué)術(shù)論文的關(guān)鍵字搜索。8. 外排序適用范圍：大數(shù)據(jù)的排序，去重基本原理及要點(diǎn)：外排序的歸并方法，置換選擇 敗者樹(shù)原理，最優(yōu)歸并樹(shù)擴(kuò)展：?jiǎn)栴}實(shí)例：1). 有一個(gè) 1G 大小的一個(gè)文件，里面每一行是一個(gè)詞，詞的大小不超過(guò)16 個(gè)字節(jié)，內(nèi)存限制大小是1M 。返回頻數(shù)最高的100 個(gè)詞。這個(gè)數(shù)據(jù)具有很明顯的特點(diǎn)，詞的大小為16 個(gè)字節(jié)，但是內(nèi)存只有1m做hash 有些不夠，所以可以用來(lái)排序。內(nèi)存可以當(dāng)輸入緩沖區(qū)使

14、用。9.trie樹(shù)適用范圍：數(shù)據(jù)量大，重復(fù)多，但是數(shù)據(jù)種類小可以放入內(nèi)存基本原理及要點(diǎn)：實(shí)現(xiàn)方式，節(jié)點(diǎn)孩子的表示方式擴(kuò)展：壓縮實(shí)現(xiàn)。問(wèn)題實(shí)例：1). 有 10 個(gè)文件， 每個(gè)文件1G， 每個(gè)文件的每一行都存放的是用戶的query ，每個(gè)文件的query都可能重復(fù)。要你按照query的頻度排序。2).1000 萬(wàn)字符串，其中有些是相同的 (重復(fù) ), 需要把重復(fù)的全部去掉，保留沒(méi)有重復(fù)的字符串。請(qǐng)問(wèn)怎么設(shè)計(jì)和實(shí)現(xiàn)？3). 尋找熱門查詢：查詢串的重復(fù)度比較高，雖然總數(shù)是1 千萬(wàn)，但如果除去重復(fù)后，不超過(guò)3 百萬(wàn)個(gè)，每個(gè)不超過(guò) 255 字節(jié)。10. 分布式處理mapreduce適用范圍：數(shù)據(jù)量大，但

15、是數(shù)據(jù)種類小可以放入內(nèi)存基本原理及要點(diǎn)：將數(shù)據(jù)交給不同的機(jī)器去處理，數(shù)據(jù)劃分，結(jié)果歸約。1. Bloom-Filter算法簡(jiǎn)介Bloom-Filter ，即布隆過(guò)濾器，1970 年由 Bloom 中提出。它可以用于檢索一個(gè)元素是否在一個(gè)集合中。Bloom Filter（BF ）是一種空間效率很高的隨機(jī)數(shù)據(jù)結(jié)構(gòu)，它利用位數(shù)組很簡(jiǎn)潔地表示一個(gè)集合，并能判斷一個(gè)元素是否屬于這個(gè)集合。它是一個(gè)判斷元素是否存在集合的快速的概率算法。Bloom Filter有可能會(huì)出現(xiàn)錯(cuò)誤判斷，但不會(huì)漏掉判斷。也就是Bloom Filter判斷元素不再集合，那肯定不在。如果判斷元素存在集合中，有一定的概率判斷錯(cuò)誤。因此，

16、Bloom Filter不適合那些“零錯(cuò)誤”的應(yīng)用場(chǎng)合。而在能容忍低錯(cuò)誤率的應(yīng)用場(chǎng)合下，Bloom Filter比其他常見(jiàn)的算法（如hash ，折半查找） 極大節(jié)省了空間。它的優(yōu)點(diǎn)是空間效率和查詢時(shí)間都遠(yuǎn)遠(yuǎn)超過(guò)一般的算法，缺點(diǎn)是有一定的誤識(shí)別率和刪除困難。Bloom Filter的詳細(xì)介紹： Bloom Filter2、 Bloom-Filter的基本思想Bloom-Filter算法的核心思想就是利用多個(gè)不同的Hash函數(shù)來(lái)解決“沖突” 。計(jì)算某元素x 是否在一個(gè)集合中， 首先能想到的方法就是將所有的已知元素保存起來(lái)構(gòu)成一個(gè)集合R，然后用元素x 跟這些 R 中的元素一一比較來(lái)判斷是否存在于集合

17、R 中；我們可以采用鏈表等數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)。但是，隨著集合R 中元素的增加，其占用的內(nèi)存將越來(lái)越大。試想，如果有幾千萬(wàn)個(gè)不同網(wǎng)頁(yè)需要下載，所需的內(nèi)存將足以占用掉整個(gè)進(jìn)程的內(nèi)存地址空間。即使用MD5 ， UUID 這些方法將URL 轉(zhuǎn)成固定的短小的字符串，內(nèi)存占用也是相當(dāng)巨大的。于是，我們會(huì)想到用Hash table的數(shù)據(jù)結(jié)構(gòu)，運(yùn)用一個(gè)足夠好的Hash 函數(shù)將一個(gè)URL 映射到二進(jìn)制位數(shù)組（位圖數(shù)組）中的某一位。如果該位已經(jīng)被置為1，那么表示該URL 已經(jīng)存在。Hash 存在一個(gè)沖突（碰撞）的問(wèn)題，用同一個(gè)Hash 得到的兩個(gè)URL 的值有可能相同。為了減少?zèng)_突，我們可以多引入幾個(gè)Hash ，如果

18、通過(guò)其中的一個(gè)Hash 值我們得出某元素不在集合中，那么該元素肯定不在集合中。只有在所有的Hash 函數(shù)告訴我們?cè)撛卦诩现袝r(shí)，才能確定該元素存在于集合中。這便是 Bloom-Filter的基本思想。原理要點(diǎn)：一是位數(shù)組，而是k 個(gè)獨(dú)立hash函數(shù)。1）位數(shù)組：假設(shè)Bloom Filter使用一個(gè)m 比特的數(shù)組來(lái)保存信息，初始狀態(tài)時(shí)，Bloom Filter是一個(gè)包含m 位的位數(shù)組 ，每一位都置為0 ， 即 BF 整個(gè)數(shù)組的元素都設(shè)置為0 。2）添加元素，k 個(gè)獨(dú)立hash 函數(shù)為了表達(dá)S=x 1, x2 , ,xn這樣一個(gè)n 個(gè)元素的集合，Bloom Filter使用k 個(gè)相互獨(dú)立的哈希函

19、數(shù) （ HashFunction），它們分別將集合中的每個(gè)元素映射到1, ,m的范圍中。當(dāng)我們往 Bloom Filter 中增加 任意一個(gè)元素 x 時(shí)候， 我們使用 k 個(gè)哈希函數(shù)得到 k 個(gè)哈希值，然后將數(shù)組中對(duì)應(yīng)的比特位設(shè)置為 1。即第 i 個(gè)哈希函數(shù)映射的位置 hashi(x) 就會(huì)被置為 1（ 1 i k）。注意，如果一個(gè)位置多次被置為1 ，那么只有第一次會(huì)起作用，后面幾次將沒(méi)有任何效果。在下圖中， k=3 ，且有兩個(gè)哈希函數(shù)選中同一個(gè)位置（從左邊數(shù)第五位，即第二個(gè)“1處“）。3）判斷元素是否存在集合在判斷 y 是否屬于這個(gè)集合時(shí)，我們只需要對(duì)y 使用 k 個(gè)哈希函數(shù)得到k 個(gè)哈希值

20、，如果所有hashi(y)的位置都是1（ 1ik），即 k 個(gè)位置都被設(shè)置為1 了，那么我們就認(rèn)為y 是集合中的元素，否則就認(rèn)為y不是集合中的元素。 下圖中 y 1 就不是集合中的元素 （因?yàn)?y1 有一處指向了 “0位”）。y2 或者屬于這個(gè)集合，或者剛好是一個(gè) false positive 。顯然這個(gè)判斷并不保證查找的結(jié)果是100%正確的。Bloom Filter的缺點(diǎn)：1）Bloom Filter無(wú)法從Bloom Filter集合中刪除一個(gè)元素。因?yàn)樵撛貙?duì)應(yīng)的位會(huì)牽動(dòng)到其他的元素。所以一個(gè)簡(jiǎn)單的改進(jìn)就是counting Bloom filter，用一個(gè)counter數(shù)組代替位數(shù)組，就可

21、以支持刪除了。此外，Bloom Filter的 hash函數(shù)選擇會(huì)影響算法的效果。2）還有一個(gè)比較重要的問(wèn)題，如何根據(jù)輸入元素個(gè)數(shù)即 hash 函數(shù)選擇會(huì)影響算法的效果。當(dāng) hash 函數(shù)個(gè)數(shù)n ，確定位數(shù)組m 的大小及hash 函數(shù)個(gè)數(shù) ，k=(ln2)*(m/n)時(shí)錯(cuò)誤率最小。在錯(cuò)誤率不大于E的情況下， m至少要等于n*lg(1/E) 才能表示任意n 個(gè)元素的集合。但m 還應(yīng)該更大些，因?yàn)檫€要保證bit 數(shù)組里至少一半為0 ，則m應(yīng) 該 =nlg(1/E)*lge，大概就是nlg(1/E)1.44倍(lg表示以2 為底的對(duì)數(shù)) 。舉個(gè)例子我們假設(shè)錯(cuò)誤率為0.01 ，則此時(shí)m 應(yīng)大概是n 的

22、 13倍。這樣k 大概是8 個(gè)。注意：這里 m 與 n 的單位不同， m 是 bit 為單位， 而 n 則是以元素個(gè)數(shù)為單位(準(zhǔn)確的說(shuō)是不同元素的個(gè)數(shù)) 。通常單個(gè)元素的長(zhǎng)度都是有很多bit 的。所以使用bloom filter內(nèi)存上通常都是節(jié)省的。一般 BF 可以與一些key-value的數(shù)據(jù)庫(kù)一起使用，來(lái)加快查詢。由于BF 所用的空間非常小，所有BF 可以常駐內(nèi)存。這樣子的話，對(duì)于大部分不存在的元素，我們只需要訪問(wèn)內(nèi)存中的BF 就可以判斷出來(lái)了，只有一小部分，我們需要訪問(wèn)在硬盤上的key-value數(shù)據(jù)庫(kù)。從而大大地提高了效率。一個(gè) Bloom Filter有以下參數(shù)：m bit 數(shù)組的寬

23、度（ bit 數(shù)）n 加入其中的 key 的數(shù)量k 使用的 hash 函數(shù)的個(gè)數(shù)fFalse Positive的比率Bloom Filter的 f 滿足下列公式：在給定 m 和 n 時(shí)，能夠使f 最小化的 k 值為：此時(shí)給出的f 為：根據(jù)以上公式，對(duì)于任意給定的f ，我們有：n = m ln(0.6185) / ln(f)1同時(shí)，我們需要k 個(gè) hash 來(lái)達(dá)成這個(gè)目標(biāo)：k = - ln(f) / ln(2)2由于 k 必須取整數(shù)，我們?cè)贐loom Filter 的程序?qū)崿F(xiàn)中，還應(yīng)該使用上面的公式來(lái)求得實(shí)際的f ：-kn/m kf = (1 e)3以上 3 個(gè)公式是程序?qū)崿F(xiàn)Bloom Filt

24、er 的關(guān)鍵公式。3、 擴(kuò)展 CounterBloom FilterCounterBloom FilterBloomFilter有個(gè)缺點(diǎn)，就是不支持刪除操作， 因?yàn)樗恢滥骋粋€(gè)位從屬于哪些向量。那我們可以給BloomFilter 加上計(jì)數(shù)器，添加時(shí)增加計(jì)數(shù)器，刪除時(shí)減少計(jì)數(shù)器。但這樣的 Filter 需要考慮附加的計(jì)數(shù)器大小，假如同個(gè)元素多次插入的話，計(jì)數(shù)器位數(shù)較少的情況下，就會(huì)出現(xiàn)溢出問(wèn)題。如果對(duì)計(jì)數(shù)器設(shè)置上限值的話，會(huì)導(dǎo)致Cache Miss ，但對(duì)某些應(yīng)用來(lái)說(shuō)，這并不是什么問(wèn)題，如 Web Sharing 。Compressed Bloom Filter為了能在服務(wù)器之間更快地通過(guò)網(wǎng)絡(luò)

25、傳輸Bloom Filter ，我們有方法能在已完成Bloom Filter之后，得到一些實(shí)際參數(shù)的情況下進(jìn)行壓縮。將元素全部添加入Bloom Filter后，我們能得到真實(shí)的空間使用率，用這個(gè)值代入公式計(jì)算出一個(gè)比m 小的值，重新構(gòu)造Bloom Filter ，對(duì)原先的哈希值進(jìn)行求余處理，在誤判率不變的情況下，使得其內(nèi)存大小更合適。4、 Bloom-Filter的應(yīng)用Bloom-Filter一般用于在大數(shù)據(jù)量的集合中判定某元素是否存在。例如郵件服務(wù)器中的垃圾郵件過(guò)濾器。在搜索引擎領(lǐng)域，Bloom-Filter最常用于網(wǎng)絡(luò)蜘蛛(Spider) 的 URL 過(guò)濾，網(wǎng)絡(luò)蜘蛛通常有一個(gè) URL 列表

26、，保存著將要下載和已經(jīng)下載的網(wǎng)頁(yè)的URL ，網(wǎng)絡(luò)蜘蛛下載了一個(gè)網(wǎng)頁(yè)，從網(wǎng)頁(yè)中提取到新的URL 后，需要判斷該URL 是否已經(jīng)存在于列表中。此時(shí)，Bloom-Filter算法是最好的選擇。1.key-value加快查詢一般Bloom-Filter可以與一些key-value的數(shù)據(jù)庫(kù)一起使用，來(lái)加快查詢。一般key-value存儲(chǔ)系統(tǒng)的values存在硬盤，查詢就是件費(fèi)時(shí)的事。將 Storage的數(shù)據(jù)都插入Filter，在 Filter中查詢都不存在時(shí)，那就不需要去Storage查詢了。當(dāng)False Position出現(xiàn)時(shí)，只是會(huì)導(dǎo)致一次多余的Storage查詢。由于 Bloom-Filter所用

27、的空間非常小，所有BF 可以常駐內(nèi)存。這樣子的話，對(duì)于大部分不存在的元素，我們只需要訪問(wèn)內(nèi)存中的Bloom-Filter就可以判斷出來(lái)了，只有一小部分，我們需要訪問(wèn)在硬盤上的key-value數(shù)據(jù)庫(kù)。從而大大地提高了效率。如圖：2 . Google的 BigTableGoogle的 BigTable也使用了Bloom Filter，以減少不存在的行或列在磁盤上的查詢，大大提高了數(shù)據(jù)庫(kù)的查詢操作的性能。3. Proxy-Cache在 Internet Cache Protocol中的 Proxy-Cache很多都是使用Bloom Filter存儲(chǔ) URLs ，除了高效的查詢外，還能很方便得傳輸交

28、換Cache 信息。4. 網(wǎng)絡(luò)應(yīng)用1）P2P 網(wǎng)絡(luò)中查找資源操作， 可以對(duì)每條網(wǎng)絡(luò)通路保存Bloom Filter ，當(dāng)命中時(shí)，則選擇該通路訪問(wèn)。2）廣播消息時(shí)，可以檢測(cè)某個(gè)IP 是否已發(fā)包。3）檢測(cè)廣播消息包的環(huán)路，將Bloom Filter保存在包里，每個(gè)節(jié)點(diǎn)將自己添加入Bloom Filter 。4）信息隊(duì)列管理，使用 Counter Bloom Filter管理信息流量。5. 垃圾郵件地址過(guò)濾像網(wǎng)易， QQ這樣的公眾電子郵件 （ email ）提供商，總是需要過(guò)濾來(lái)自發(fā)送垃圾郵件的人（spamer）的垃圾郵件。一個(gè)辦法就是記錄下那些發(fā)垃圾郵件的 email 地址。由于那些發(fā)送者不停地在

29、注冊(cè)新的地址，全世界少說(shuō)也有幾十億個(gè)發(fā)垃圾郵件的地址，將他們都存起來(lái)則需要大量的網(wǎng)絡(luò)服務(wù)器。如果用哈希表，每存儲(chǔ)一億個(gè) email 地址，就需要 1.6GB 的內(nèi)存（用哈希表實(shí)現(xiàn)的具體辦法是將每一個(gè) email 地址對(duì)應(yīng)成一個(gè)八字節(jié)的信息指紋，然后將這些信息指紋存入哈希表，由于哈希表的存儲(chǔ)效率一般只有50% ，因此一個(gè)email 地址需要占用十六個(gè)字節(jié)。一億個(gè)地址大約要1.6GB ，即十六億字節(jié)的內(nèi)存） 。因此存貯幾十億個(gè)郵件地址可能需要上百GB 的內(nèi)存。而B(niǎo)loom Filter只需要哈希表1/8到1/4的大小就能解決同樣的問(wèn)題。BloomFilter 決不會(huì)漏掉任何一個(gè)在黑名單中的可疑地址

30、。而至于誤判問(wèn)題，常見(jiàn)的補(bǔ)救辦法是在建立一個(gè)小的白名單，存儲(chǔ)那些可能別誤判的郵件地址。5、 Bloom-Filter的具體實(shí)現(xiàn)c 語(yǔ)言實(shí)現(xiàn)：stdafx.h ：1. #pragma once2. #include 3. #include stdlib.h4. #include 5. #include 6. using namespace std;1. #include stdafx.h2.3.4. #define ARRAY_SIZE 256 /*we get the 256 chars of each line*/5. #define SIZE 48000000 /* size should

31、 be 1/8 of max*/6. #define MAX 384000000/*the max bit space*/7.8. #define SETBIT(ch,n) chn/8|=1(7-n%8)9. #define GETBIT(ch,n) (chn/8&1(7-n%8)10.11.unsignedintlen( char*ch);/* functions to calculate the length of the url*/12.13.unsignedintRSHash( char* str, unsignedintlen);/* functions to calculate t

32、he hash value of the url*/14.unsignedintJSHash( char* str, unsignedintlen);/* functions to calculate the hash value of the url*/15.unsignedintPJWHash( char* str, unsignedintlen);/* functions to calculate the hash value of the url*/16.unsignedintELFHash(char* str, unsignedintlen);/* functions to calc

33、ulate the hash value of the url*/17.unsignedintBKDRHash( char * str, unsignedintlen);/* functions to calculate the hash value of the url*/18.unsignedintSDBMHash( char * str, unsignedintlen);/* functions to calculate the hash value of the url*/19.unsignedintDJBHash(char* str, unsignedintlen);/* funct

34、ions to calculate the hash value of the url*/20.unsignedintDEKHash( char* str, unsignedintlen);/* functions to calculate the hash value of the url*/21.unsignedintBPHash( char* str, unsignedintlen);/* functions to calculate the hash value of the url*/22.unsignedintFNVHash( char* str, unsignedintlen);

35、/* functions to calculate the hash value of the url*/23.unsignedintAPHash( char* str, unsignedintlen);/* functions to calculate the hash value of the url*/24.unsignedintHFLPHash( char * str,unsignedintlen);/* functions to calculate the hash value of the url*/25.unsignedintHFHash( char* str,unsignedi

36、nt len); /* functions to calculate the hash value of the url*/26.unsignedintStrHash(char * str,unsignedintlen);/* functions to calculate the hash value of the url*/27.unsignedintTianlHash(char * str,unsignedintlen);/* functions to calculate the hash value of the url*/28.29.30. int main()31. 32.inti,

37、num,num2=0;/* the number to record the repeated urls and the total of it*/33.unsignedint tt=0;34.intflag;/*it helps to check weather the url has already existed */35.charbuf257;/*it helps to print the start time of the program */36. time_t tmp = time(NULL);37.38. char file1100,file2100;39.FILE *fp1,

38、*fp2;/*pointer to the file */40. char chARRAY_SIZE;41.char *vector ;/* the bit space*/42.vector = (char*)calloc(SIZE,sizeof( char);43.44.printf(Please enter the file with repeated urls:n);45.scanf(%s ,&file1);46.if ( (fp1 = fopen(file1,rb) = NULL) /* open the goal file*/47.printf(Connot open the fil

39、e %s!n,file1);48. 49.50.printf(Please enter the file you want to save to:n);51.scanf(%s ,&file2);52.if ( (fp2 = fopen(file2,w ) = NULL) 53.printf(Connot open the file %sn,file2);54. 55.strftime(buf,32,%Y-%m-%d %H:%M:%S,localtime(&tmp);56.printf(%sn,buf);/*print the system time*/57.58. for (i=0;iSIZE

40、;i+) 59.vectori=0;/*set 0*/60. 61.62.while (!feof(fp1) /* the check process*/63.64. fgets(ch,ARRAY_SIZE,fp1);65. flag=0;66. tt+;67.if ( GETBIT(vector, HFLPHash(ch,len(ch)%MAX) ) 68. flag+;69.else70. SETBIT(vector,HFLPHash(ch,len(ch)%MAX );71. 72.73.if ( GETBIT(vector, StrHash(ch,len(ch)%MAX) ) 74. f

41、lag+;75.else76. SETBIT(vector,StrHash(ch,len(ch)%MAX );77. 78.79.if ( GETBIT(vector, HFHash(ch,len(ch)%MAX) )80. flag+;81.else82. SETBIT(vector,HFHash(ch,len(ch)%MAX );83. 84.85.if ( GETBIT(vector, DEKHash(ch,len(ch)%MAX) ) 86. flag+;87.else88. SETBIT(vector,DEKHash(ch,len(ch)%MAX );89. 90.91.if ( G

42、ETBIT(vector, TianlHash(ch,len(ch)%MAX) ) 92. flag+;93.else94. SETBIT(vector,TianlHash(ch,len(ch)%MAX );95. 96.97.if ( GETBIT(vector, SDBMHash(ch,len(ch)%MAX) ) 98. flag+;99.else100. SETBIT(vector,SDBMHash(ch,len(ch)%MAX );101. 102.103. if (flag6)104. num2+;105. else106. fputs(ch,fp2);107.108. /* pr

43、intf( %d,flag); */109. 110. /* the result*/111.printf(nThere are %d urls!n,tt);112.printf(nThere are %d not repeated urls!n,num2);113.printf(There are %d repeated urls!n,tt-num2);114. fclose(fp1);115. fclose(fp2);116. return 0;117. 118.119.120. /*functions may be used in the main */121. unsigned int len( char *ch)122. 123. int m=0;124. while (chm!= 0 )