【什么是Bloom Filter】
Bloom Filter是一種空間效率很高的隨機數據結構，它利用位數組很簡潔地表示一個集合，并能判斷一個元素是否屬于這個集合。Bloom Filter的這種高效是有一定代價的：在判斷一個元素是否屬于某個集合時，有可能會把不屬于這個集合的元素誤認為屬于這個集合（false positive）。因此，Bloom Filter不適合那些“零錯誤”的應用場合。而在能容忍低錯誤率的應用場合下，采用Bloom Filter的數據結構，可以通過極少的錯誤換取了存儲空間的極大節省。 這里有一篇關于Bloom Filter的詳細介紹，不太懂的博友可以看看。
【適用范圍】
可以用來實現數據字典，進行數據的判重，或者集合求交集
【基本原理及要點】
對于原理來說很簡單，位數組外加k個獨立hash函數。Bloom filter提供兩種基本的操作，將元素加入集合和判斷某一元素是否屬于該集合，一下說明如何操作：
將一個元素加入集合：首先將要加入集合的元素用k個hash函數進行hash，得到k個hash index，然后在集合的位數組中將這k個hash index的位置置1，下面用兩幅圖來描述這個過程。
bloom filter位數組（集合）的初始狀態
插入兩個個元素，X1，X2：
bloom-filter-插入元素
查找元素是否屬于該集合：首先同樣用定義的hash函數對該元素進行hash得到hash index，然后查位數組中對應的hash index是否都是1，如果是，則表明該元素屬于該集合，反之不屬于【當然不全是了，請繼續看后面】，如圖，判斷元素Y1，Y2是否屬于該集合。
bloom-filter-判斷元素是否屬于集合
如上圖，由于y1的三個hash index有一個不為1，因此不屬于該集合，而y2所有的hash index的位置上都為1，因此屬于該集合。
【Bloom Filter的不足】
很明顯上面這個查找過程并不保證查找的結果是100%正確的。同時也不支持刪除一個已經插入的關鍵字，因為該關鍵字對應的位會牽動到其他的關鍵字。所以一個簡單的改進就是 counting Bloom filter，用一個counter數組代替位數組，就可以支持刪除了。
還有一個比較重要的問題，如何根據輸入元素個數n，確定位數組m的大小及hash函數個數。當hash函數個數k=(ln2)*(m/n)時錯誤率最小。在錯誤率不大于E的情況 下，m至少要等于n*lg(1/E)才能表示任意n個元素的集合。但m還應該更大些，因為還要保證bit數組里至少一半為0，則m應 該>=nlg(1/E)*lge 大概就是nlg(1/E)1.44倍(lg表示以2為底的對數)。
舉個例子我們假設錯誤率為0.01，則此時m應大概是n的13倍。這樣k大概是8個。
注意這里m與n的單位不同，m是bit為單位，而n則是以元素個數為單位(準確的說是不同元素的個數)。通常單個元素的長度都是有很多bit的。所以使用bloom filter內存上通常都是節省的。
【擴展】
Bloom filter將集合中的元素映射到位數組中，用k（k為哈希函數個數）個映射位是否全1表示元素在不在這個集合中。Counting bloom filter（CBF）將位數組中的每一位擴展為一個counter，從而支持了元素的刪除操作。Spectral Bloom Filter（SBF）將其與集合元素的出現次數關聯。SBF采用counter中的最小值來近似表示元素的出現頻率。
【問題實例】
給你A,B兩個文件，各存放50億條URL，每條URL占用64字節，內存限制是4G，讓你找出A,B文件共同的URL。如果是三個乃至n個文件呢？
根據這個問題我們來計算下內存的占用，4G=2^32大概是40億*8大概是340億，n=50億，如果按出錯率0.01算需要的大概是650億個bit。 現在可用的是340億，相差并不多，這樣可能會使出錯率上升些。另外如果這些urlip是一一對應的，就可以轉換成ip，則大大簡單了。