一文讀懂BloomFilter
Bloom Filter是由Bloom在1970年提出的一種多哈希函數(shù)映射的快速查找算法。通常應(yīng)用在一些需要快速判斷某個(gè)元素是否屬于集合，但是并不嚴(yán)格要求100%正確的場合。
?
一.?實(shí)例?
為了說明Bloom Filter存在的重要意義，舉一個(gè)實(shí)例：
假設(shè)要你寫一個(gè)網(wǎng)絡(luò)蜘蛛（web crawler）。由于網(wǎng)絡(luò)間的鏈接錯(cuò)綜復(fù)雜，蜘蛛在網(wǎng)絡(luò)間爬行很可能會(huì)形成“環(huán)”。為了避免形成“環(huán)”，就需要知道蜘蛛已經(jīng)訪問過那些URL。給一個(gè)URL，怎樣知道蜘蛛是否已經(jīng)訪問過呢？稍微想想，就會(huì)有如下幾種方案：
1. 將訪問過的URL保存到數(shù)據(jù)庫。
2. 用HashSet將訪問過的URL保存起來。那只需接近O(1)的代價(jià)就可以查到一個(gè)URL是否被訪問過了。
3. URL經(jīng)過MD5或SHA-1等單向哈希后再保存到HashSet或數(shù)據(jù)庫。
4. Bit-Map方法。建立一個(gè)BitSet，將每個(gè)URL經(jīng)過一個(gè)哈希函數(shù)映射到某一位。
方法1~3都是將訪問過的URL完整保存，方法4則只標(biāo)記URL的一個(gè)映射位。
?
以上方法在數(shù)據(jù)量較小的情況下都能完美解決問題，但是當(dāng)數(shù)據(jù)量變得非常龐大時(shí)問題就來了。
方法1的缺點(diǎn)：數(shù)據(jù)量變得非常龐大后關(guān)系型數(shù)據(jù)庫查詢的效率會(huì)變得很低。而且每來一個(gè)URL就啟動(dòng)一次數(shù)據(jù)庫查詢是不是太小題大做了？
方法2的缺點(diǎn)：太消耗內(nèi)存。隨著URL的增多，占用的內(nèi)存會(huì)越來越多。就算只有1億個(gè)URL，每個(gè)URL只算50個(gè)字符，就需要5GB內(nèi)存。
方法3：由于字符串經(jīng)過MD5處理后的信息摘要長度只有128Bit，SHA-1處理后也只有160Bit，因此方法3比方法2節(jié)省了好幾倍的內(nèi)存。
方法4消耗內(nèi)存是相對(duì)較少的，但缺點(diǎn)是單一哈希函數(shù)發(fā)生沖突的概率太高。還記得數(shù)據(jù)結(jié)構(gòu)課上學(xué)過的Hash表沖突的各種解決方法么？若要降低沖突發(fā)生的概率到1%，就要將BitSet的長度設(shè)置為URL個(gè)數(shù)的100倍。
?
實(shí)質(zhì)上上面的算法都忽略了一個(gè)重要的隱含條件：允許小概率的出錯(cuò)，不一定要100%準(zhǔn)確！也就是說少量url實(shí)際上沒有沒網(wǎng)絡(luò)蜘蛛訪問，而將它們錯(cuò)判為已訪問的代價(jià)是很小的——大不了少抓幾個(gè)網(wǎng)頁唄。?
?
二. Bloom Filter的算法?
?
廢話說到這里，下面引入本篇的主角——Bloom Filter。其實(shí)上面方法4的思想已經(jīng)很接近Bloom Filter了。方法四的致命缺點(diǎn)是沖突概率高，為了降低沖突的概念，Bloom Filter使用了多個(gè)哈希函數(shù)，而不是一個(gè)。
?? Bloom Filter算法如下：
?? ?創(chuàng)建一個(gè)m位BitSet，先將所有位初始化為0，然后選擇k個(gè)不同的哈希函數(shù)。第i個(gè)哈希函數(shù)對(duì)字符串str哈希的結(jié)果記為h（i，str），且h（i，str）的范圍是0到m-1 。
?
(1)?加入字符串過程?
?
下面是每個(gè)字符串處理的過程，首先是將字符串str“記錄”到BitSet中的過程：
對(duì)于字符串str，分別計(jì)算h（1，str），h（2，str）…… h（k，str）。然后將BitSet的第h（1，str）、h（2，str）…… h（k，str）位設(shè)為1。
?
圖1.Bloom Filter加入字符串過程
很簡單吧？這樣就將字符串str映射到BitSet中的k個(gè)二進(jìn)制位了。
?
(2)?檢查字符串是否存在的過程?
?
下面是檢查字符串str是否被BitSet記錄過的過程：
對(duì)于字符串str，分別計(jì)算h（1，str），h（2，str）…… h（k，str）。然后檢查BitSet的第h（1，str）、h（2，str）…… h（k，str）位是否為1，若其中任何一位不為1則可以判定str一定沒有被記錄過。若全部位都是1，則“認(rèn)為”字符串str存在。
?
若一個(gè)字符串對(duì)應(yīng)的Bit不全為1，則可以肯定該字符串一定沒有被Bloom Filter記錄過。（這是顯然的，因?yàn)樽址挥涗涍^，其對(duì)應(yīng)的二進(jìn)制位肯定全部被設(shè)為1了）
但是若一個(gè)字符串對(duì)應(yīng)的Bit全為1，實(shí)際上是不能100%的肯定該字符串被Bloom Filter記錄過的。（因?yàn)橛锌赡茉撟址乃形欢紕偤檬潜黄渌址鶎?duì)應(yīng)）這種將該字符串劃分錯(cuò)的情況，稱為false positive 。
?
(3)?刪除字符串過程?
?? 字符串加入了就被不能刪除了，因?yàn)閯h除會(huì)影響到其他字符串。實(shí)在需要?jiǎng)h除字符串的可以使用Counting bloomfilter(CBF)，這是一種基本Bloom Filter的變體，CBF將基本Bloom Filter每一個(gè)Bit改為一個(gè)計(jì)數(shù)器，這樣就可以實(shí)現(xiàn)刪除字符串的功能了。
?
Bloom Filter跟單哈希函數(shù)Bit-Map不同之處在于：Bloom Filter使用了k個(gè)哈希函數(shù)，每個(gè)字符串跟k個(gè)bit對(duì)應(yīng)。從而降低了沖突的概率。
?
三. Bloom Filter參數(shù)選擇?
?
?? (1)哈希函數(shù)選擇
?? 哈希函數(shù)的選擇對(duì)性能的影響應(yīng)該是很大的，一個(gè)好的哈希函數(shù)要能近似等概率的將字符串映射到各個(gè)Bit。選擇k個(gè)不同的哈希函數(shù)比較麻煩，一種簡單的方法是選擇一個(gè)哈希函數(shù)，然后送入k個(gè)不同的參數(shù)。
???(2)Bit數(shù)組大小選擇?
?? 哈希函數(shù)個(gè)數(shù)k、位數(shù)組大小m、加入的字符串?dāng)?shù)量n的關(guān)系可以參考參考文獻(xiàn)1。該文獻(xiàn)證明了對(duì)于給定的m、n，當(dāng) k = ln(2)* m/n 時(shí)出錯(cuò)的概率是最小的。
?? 同時(shí)該文獻(xiàn)還給出特定的k，m，n的出錯(cuò)概率。例如：根據(jù)參考文獻(xiàn)1，哈希函數(shù)個(gè)數(shù)k取10，位數(shù)組大小m設(shè)為字符串個(gè)數(shù)n的20倍時(shí)，false positive發(fā)生的概率是0.0000889 ，這個(gè)概率基本能滿足網(wǎng)絡(luò)爬蟲的需求了。 ?
?
四. Bloom Filter實(shí)現(xiàn)代碼?
?? ?下面給出一個(gè)簡單的Bloom Filter的Java實(shí)現(xiàn)代碼：
import?java.util.BitSet;
publicclass?BloomFilter?
{
/*?BitSet初始分配2^24個(gè)bit?*/?
privatestaticfinalint?DEFAULT_SIZE?=1<<25;?
/*?不同哈希函數(shù)的種子，一般應(yīng)取質(zhì)數(shù)?*/
privatestaticfinalint[]?seeds?=newint[]?{?5,?7,?11,?13,?31,?37,?61?};
private?BitSet?bits?=new?BitSet(DEFAULT_SIZE);
/*?哈希函數(shù)對(duì)象?*/?
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]);
}
}
//?將字符串標(biāo)記到bits中
publicvoid?add(String?value)?
{
for?(SimpleHash?f?:?func)?
{
bits.set(f.hash(value),?true);
}
}
//判斷字符串是否已經(jīng)被bits標(biāo)記
publicboolean?contains(String?value)?
{
if?(value?==null)?
{
returnfalse;
}
boolean?ret?=true;
for?(SimpleHash?f?:?func)?
{
ret?=?ret?&&?bits.get(f.hash(value));
}
return?ret;
}
/*?哈希函數(shù)類?*/
publicstaticclass?SimpleHash?
{
privateint?cap;
privateint?seed;
public?SimpleHash(int?cap,?int?seed)?
{
this.cap?=?cap;
this.seed?=?seed;
}
//hash函數(shù)，采用簡單的加權(quán)和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;
}
}
}
原文鏈接：http://www.cnblogs.com/heaad/archive/2011/01/02/1924195.html
下載文檔
