（轉載）BloomFilter——大規模資料處理利器

原文連結：http://www.cnblogs.com/heaad/archive/2011/01/02/1924195.html

延伸閱讀：https://my.oschina.net/kiwivip/blog/133498

Bloom Filter是由Bloom在1970年提出的一種多哈希函數映射的快速查找算法。通常應用在一些需要快速判斷某個元素是否屬于集合，但是并不嚴格要求100%正确的場合。

一 . 執行個體

為了說明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位BitSet，先将所有位初始化為0，然後選擇k個不同的哈希函數。第i個哈希函數對字元串str哈希的結果記為h（i，str），且h（i，str）的範圍是0到m-1 。

(1) 加入字元串過程

下面是每個字元串處理的過程，首先是将字元串str“記錄”到BitSet中的過程：

對于字元串str，分别計算h（1，str），h（2，str）…… h（k，str）。然後将BitSet的第h（1，str）、h（2，str）…… h（k，str）位設為1。

圖1.Bloom Filter加入字元串過程

很簡單吧？這樣就将字元串str映射到BitSet中的k個二進制位了。

(2) 檢查字元串是否存在的過程

下面是檢查字元串str是否被BitSet記錄過的過程：

對于字元串str，分别計算h（1，str），h（2，str）…… h（k，str）。然後檢查BitSet的第h（1，str）、h（2，str）…… h（k，str）位是否為1，若其中任何一位不為1則可以判定str一定沒有被記錄過。若全部位都是1，則“認為”字元串str存在。

若一個字元串對應的Bit不全為1，則可以肯定該字元串一定沒有被Bloom Filter記錄過。（這是顯然的，因為字元串被記錄過，其對應的二進制位肯定全部被設為1了）

但是若一個字元串對應的Bit全為1，實際上是不能100%的肯定該字元串被Bloom Filter記錄過的。（因為有可能該字元串的所有位都剛好是被其他字元串所對應）這種将該字元串劃分錯的情況，稱為false positive 。

(3) 删除字元串過程

字元串加入了就被不能删除了，因為删除會影響到其他字元串。實在需要删除字元串的可以使用Counting bloomfilter(CBF)，這是一種基本Bloom Filter的變體，CBF将基本Bloom Filter每一個Bit改為一個計數器，這樣就可以實作删除字元串的功能了。

Bloom Filter跟單哈希函數Bit-Map不同之處在于：Bloom Filter使用了k個哈希函數，每個字元串跟k個bit對應。進而降低了沖突的機率。

三 參數選擇 哈希函數選擇

哈希函數的選擇對性能的影響應該是很大的，一個好的哈希函數要能近似等機率的将字元串映射到各個Bit。選擇k個不同的哈希函數比較麻煩，一種簡單的方法是選擇一個哈希函數，然後送入k個不同的參數。

(2)Bit 數組大小選擇

哈希函數個數k、位數組大小m、加入的字元串數量n的關系可以參考

參考文獻1

。該文獻證明了對于給定的m、n，當 k = ln(2)* m/n 時出錯的機率是最小的。

同時該文獻還給出特定的k，m，n的出錯機率。例如：根據參考文獻1，哈希函數個數k取10，位數組大小m設為字元串個數n的20倍時，false positive發生的機率是0.0000889 ，這個機率基本能滿足網絡爬蟲的需求了。

四 實作代碼

下面給出一個簡單的Bloom Filter的Java實作代碼：

import java.util.BitSet;

publicclass BloomFilter

{

/* BitSet初始配置設定2^24個bit */

privatestaticfinalint DEFAULT_SIZE =1<<25;

/* 不同哈希函數的種子，一般應取質數 */

private static final int[] seeds =newint[] { 5, 7, 11, 13, 31, 37, 61 };

private BitSet bits =new BitSet(DEFAULT_SIZE);

/* 哈希函數對象 */

private SimpleHash[] func =new SimpleHash[seeds.length];

public BloomFilter()

for (int i =0; i < seeds.length; i++)

func[i] =new SimpleHash(DEFAULT_SIZE, seeds[i]);

}

// 将字元串标記到bits中

publicvoid add(String value)

for (SimpleHash f : func)

bits.set(f.hash(value), true);

//判斷字元串是否已經被bits标記

publicboolean contains(String value)

if (value ==null)

returnfalse;

boolean ret =true;

ret = ret && bits.get(f.hash(value));

return ret;

/* 哈希函數類 */

publicstaticclass SimpleHash

privateint cap;

privateint seed;

public SimpleHash(int cap, int seed)

this.cap = cap;

this.seed = seed;

//hash函數，采用簡單的權重和hash

publicint hash(String value)

int result =0;

int len = value.length();

for (int i =0; i < len; i++)

result = seed * result + value.charAt(i);

return (cap -1) & result;