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

實(shí)例

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

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

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

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

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

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

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

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

方法4消耗內(nèi)存是相對較少的，但缺點(diǎn)是單一哈希函數(shù)發(fā)生沖突的概率太高。還記得數(shù)據(jù)結(jié)構(gòu)課上學(xué)過的Hash表沖突的各種解決方法么？若要降低沖突發(fā)生的概率到1%，就要將BitSet的長度設(shè)置為URL個數(shù)的100倍。

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

Bloom Filter的算法

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

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

Bloom filter 特點(diǎn)

Bloom filter優(yōu)點(diǎn)就是它的插入和查詢時間都是常數(shù)，另外它查詢元素卻不保存元素本身，具有良好的安全性。它的缺點(diǎn)也是顯而易見的，當(dāng)插入的元素越多，錯判“在集合內(nèi)”的概率就越大了，另外 Bloom filter也不能刪除一個元素，因?yàn)槎鄠€元素哈希的結(jié)果可能在 Bloom filter 結(jié)構(gòu)中占用的是同一個位，如果刪除了一個比特位，可能會影響多個元素的檢測。

其實(shí)要做到能夠刪除一個元素，就需要修改下算法，把bitmap修改成計(jì)數(shù)，這會帶來另外一個缺點(diǎn)：內(nèi)存浪費(fèi)。