【什么是Bloom Filter】

Bloom Filter是一種空間效率很高的隨機數(shù)據(jù)結(jié)構(gòu)，它利用位數(shù)組很簡潔地表示一個集合，并能判斷一個元素是否屬于這個集合。Bloom Filter的這種高效是有一定代價的：在判斷一個元素是否屬于某個集合時，有可能會把不屬于這個集合的元素誤認為屬于這個集合(false positive)。因此，Bloom Filter不適合那些“零錯誤”的應(yīng)用場合。而在能容忍低錯誤率的應(yīng)用場合下，Bloom Filter通過極少的錯誤換取了存儲空間的極大節(jié)省。 這里有一篇關(guān)于Bloom Filter的詳細介紹，不太懂的博友可以看看。

【適用范圍】

可以用來實現(xiàn)數(shù)據(jù)字典，進行數(shù)據(jù)的判重，或者集合求交集

【基本原理及要點】

對于原理來說很簡單，位數(shù)組+k個獨立hash函數(shù)。將hash函數(shù)對應(yīng)的值的位數(shù)組置1，查找時如果發(fā)現(xiàn)所有hash函數(shù)對應(yīng)位都是1說明存在，很明顯這 個過程并不保證查找的結(jié)果是100%正確的。同時也不支持刪除一個已經(jīng)插入的關(guān)鍵字，因為該關(guān)鍵字對應(yīng)的位會牽動到其他的關(guān)鍵字。所以一個簡單的改進就是 counting Bloom filter，用一個counter數(shù)組代替位數(shù)組，就可以支持刪除了。

還有一個比較重要的問題，如 何根據(jù)輸入元素個數(shù)n，確定位數(shù)組m的大小及hash函數(shù)個數(shù)。當hash函數(shù)個數(shù)k=(ln2)*(m/n)時錯誤率最小。在錯誤率不大于E的情況 下，m至少要等于n*lg(1/E)才能表示任意n個元素的集合。但m還應(yīng)該更大些，因為還要保證bit數(shù)組里至少一半為0，則m應(yīng) 該>=nlg(1/E)*lge 大概就是nlg(1/E)1.44倍(lg表示以2為底的對數(shù))。

舉個例子我們假設(shè)錯誤率為0.01，則此時m應(yīng)大概是n的13倍。這樣k大概是8個。

注意這里m與n的單位不同，m是bit為單位，而n則是以元素個數(shù)為單位(準確的說是不同元素的個數(shù))。通常單個元素的長度都是有很多bit的。所以使用bloom filter內(nèi)存上通常都是節(jié)省的。

【擴展】

Bloom filter將集合中的元素映射到位數(shù)組中，用k(k為哈希函數(shù)個數(shù))個映射位是否全1表示元素在不在這個集合中。Counting bloom filter(CBF)將位數(shù)組中的每一位擴展為一個counter，從而支持了元素的刪除操作。Spectral Bloom Filter(SBF)將其與集合元素的出現(xiàn)次數(shù)關(guān)聯(lián)。SBF采用counter中的最小值來近似表示元素的出現(xiàn)頻率。

【問題實例】

給你A,B兩個文件，各存放50億條URL，每條URL占用64字節(jié)，內(nèi)存限制是4G，讓你找出A,B文件共同的URL。如果是三個乃至n個文件呢?

根據(jù)這個問題我們來計算下內(nèi)存的占用，4G=2^32大概是40億*8大概是340億，n=50億，如果按出錯率0.01算需要的大概是650億個 bit。 現(xiàn)在可用的是340億，相差并不多，這樣可能會使出錯率上升些。另外如果這些urlip是一一對應(yīng)的，就可以轉(zhuǎn)換成ip，則大大簡單了。

原文鏈接：http://blog.redfox66.com/post/2010/09/24/mass-data-topic-2-bloom-filter.aspx

【編輯推薦】

1. 應(yīng)對海量數(shù)據(jù) Oracle數(shù)據(jù)庫機青睞至強
2. 淘寶海量數(shù)據(jù)庫之克服隨機IO難題
3. Oceanbase一個千億級海量數(shù)據(jù)庫