Bloom filter是 由 Howard Bloom在 1970 年提出的一種多哈希函數映射的快速查找算法，該算法能夠在非常快速的判定某個元素是否在一個集合之外。這種檢測只會對在集合內的數據錯判，而不會對不是集 合內的數據進行錯判，這樣每個檢測請求返回有“在集合內（可能錯誤）”和“不在集合內（絕對不在集合內）”兩種情況。目前Bloom filter在分布式系統中有著廣泛的使用，比如說GFS/HDFS/Cassandra/Bigtable/Squid。

實例

為了說明Bloom filter存在的重要意義，舉一個實例：

假設要你寫一個網絡蜘蛛（web crawler）。由于網絡間的鏈接錯綜復雜，蜘蛛在網絡間爬行很可能會形成“環”。為了避免形成“環”，就需要知道蜘蛛已經訪問過那些URL。給一個URL，怎樣知道蜘蛛是否已經訪問過呢？稍微想想，就會有如下幾種方案：

1. 將訪問過的URL保存到數據庫。
2. 用HashSet將訪問過的URL保存起來。那只需接近O(1)的代價就可以查到一個URL是否被訪問過了。
3. URL經過MD5或SHA-1等單向哈希后再保存到HashSet或數據庫。
4. Bit-Map方法。建立一個BitSet，將每個URL經過一個哈希函數映射到某一位。

方法1~3都是將訪問過的URL完整保存，方法4則只標記URL的一個映射位。

以上方法在數據量較小的情況下都能完美解決問題，但是當數據量變得非常龐大時問題就來了。

方法1的缺點：數據量變得非常龐大后關系型數據庫查詢的效率會變得很低。而且每來一個URL就啟動一次數據庫查詢是不是太小題大做了？

方法2的缺點：太消耗內存。隨著URL的增多，占用的內存會越來越多。就算只有1億個URL，每個URL只算50個字符，就需要5GB內存。

方法3：由于字符串經過MD5處理后的信息摘要長度只有128Bit，SHA-1處理后也只有160Bit，因此方法3比方法2節省了好幾倍的內存。

方法4消耗內存是相對較少的，但缺點是單一哈希函數發生沖突的概率太高。還記得數據結構課上學過的Hash表沖突的各種解決方法么？若要降低沖突發生的概率到1%，就要將BitSet的長度設置為URL個數的100倍。

實質上上面的算法都忽略了一個重要的隱含條件：允許小概率的出錯，不一定要100%準確！也就是說少量url實際上沒有沒網絡蜘蛛訪問，而將它們錯判為已訪問的代價是很小的——大不了少抓幾個網頁唄。

Bloom Filter的算法

下面引入本篇的主角——Bloom filter。其實上面方法4的思想已經很接近Bloom filter了。方法四的致命缺點是沖突概率高，為了降低沖突的概念，Bloom filter使用了多個哈希函數，而不是一個。

Bloom filter采 用的是哈希函數的方法，將一個元素映射到一個 m 長度的陣列上的一個點，當這個點是 1 時，那么這個元素在集合內，反之則不在集合內。這個方法的缺點就是當檢測的元素量很多時候可能有沖突，解決方法就是使用 k 個哈希 函數對應 k 個點，如果所有點都是 1 的話，那么元素在集合內，如果有 0 的話，元素則不再集合內。

Bloom filter 特點

Bloom filter優點就是它的插入和查詢時間都是常數，另外它查詢元素卻不保存元素本身，具有良好的安全性。它的缺點也是顯而易見的，當插入的元素越多，錯判“在集合內”的概率就越大了，另外 Bloom filter也不能刪除一個元素，因為多個元素哈希的結果可能在 Bloom filter 結構中占用的是同一個位，如果刪除了一個比特位，可能會影響多個元素的檢測。

其實要做到能夠刪除一個元素，就需要修改下算法，把bitmap修改成計數，這會帶來另外一個缺點：內存浪費。