摘 要：Bloom Filter是一種空間和時(shí)間效率很高的二進(jìn)制項(xiàng)量數(shù)據(jù)結(jié)構(gòu)，它利用位數(shù)組很簡(jiǎn)單地表示一個(gè)集合，并能檢索一個(gè)元素是否屬于這個(gè)集合。Bloom Filter的高效檢索是由有一定誤報(bào)率換來(lái)的。因此，Bloom Filter只適合那些允許一定誤報(bào)率的應(yīng)用場(chǎng)合。

關(guān)鍵詞：Bloom Filter 哈希函數(shù) 漏報(bào) 誤報(bào)

中圖分類(lèi)號(hào)：TP311.12 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-3791（2013）04（a）-0011-01

1 Bloom Filter

Bloom Filter（布隆過(guò)濾器）是1970年由Howard Bloom提出的一個(gè)很長(zhǎng)的二進(jìn)制向量數(shù)據(jù)結(jié)構(gòu)。布隆過(guò)濾器可以用于查詢(xún)一個(gè)元素是否在某集合中。由于Bloom Filter在空間效率、查詢(xún)效率以及安全性上的優(yōu)勢(shì)明顯，因此被廣泛的應(yīng)用于各種需要查詢(xún)的場(chǎng)合中，如Oracle的數(shù)據(jù)庫(kù)，Google的Bit Table，web cache共享，拼寫(xiě)檢查等都用了此技術(shù)。

2 Bloom Filter原理

假如要想判斷一個(gè)元素是不是在某一個(gè)集合中，一般情況想到的是將所有元素保存起來(lái)，然后通過(guò)比較來(lái)確定。鏈表，樹(shù)等數(shù)據(jù)結(jié)構(gòu)就是這種思路。但是隨著集合中元素的增加，我們需要的存儲(chǔ)空間越來(lái)越大，利用這種思路去檢索查找，效率也會(huì)越來(lái)越低。

工作效率低下讓人難以容忍，這時(shí)候我們可以考慮利用哈希表哈希函數(shù)這個(gè)數(shù)據(jù)結(jié)構(gòu)。哈希函數(shù)在計(jì)算機(jī)領(lǐng)域，尤其是數(shù)據(jù)快速查找領(lǐng)域，加密領(lǐng)域用的極廣。其作用是將一個(gè)大的數(shù)據(jù)集映射到一個(gè)小的數(shù)據(jù)集上面。哈希表是根據(jù)哈希值（Key value）而直接進(jìn)行訪(fǎng)問(wèn)的數(shù)據(jù)結(jié)構(gòu)。也就是說(shuō)，它通過(guò)把哈希值映射到表中一個(gè)位置來(lái)訪(fǎng)問(wèn)記錄，以加快查找的速度。或者也可以認(rèn)為哈希表是通過(guò)一個(gè)Hash函數(shù)將一個(gè)元素映射到一個(gè)位陣列（Bit array）中的一個(gè)點(diǎn)。這樣就簡(jiǎn)單了，只要看陣列中這個(gè)點(diǎn)是不是1就知道判斷出他在不在集合中了。這實(shí)際上就是Bloom Filter的基本思路。

雖然了解了Bloom Filter的基本思路但是其中要用到哈希函數(shù)，哈希函數(shù)有個(gè)很大的問(wèn)題就是沖突，那么在Bloom Filter算法是怎么解決的呢？那就是在其中用多個(gè)哈希函數(shù)來(lái)解決判斷一個(gè)元素，只要有一個(gè)函數(shù)判斷說(shuō)該元素不在此集合中那么它肯定就不在此集合中。但也有一種可能就是其中的所有函數(shù)都說(shuō)該元素在此集合中，但實(shí)際上它并不在其中，這種情況是從在的，但是概率非常低。那就是它的效率很高了。我們把這種有多個(gè)哈希函數(shù)組成的數(shù)據(jù)結(jié)構(gòu)稱(chēng)為Bloom Filter。

下面我們舉一簡(jiǎn)單的例子來(lái)看Bloom Filter是如何工作的。

Bloom Filter是一個(gè)包含n位的位數(shù)組，初始化時(shí)每一位都置為0。存在一個(gè)具有m個(gè)元素的集合W={x1，x2，…，xm}和k個(gè)最優(yōu)的相互獨(dú)立的哈希函數(shù)。我們利用k{h1，h2，…h(huán)k}個(gè)哈希函數(shù)把它們分別將W集合中的每個(gè)元素映射到位數(shù)組{1，…，n}的范圍中。對(duì)任意一個(gè)W集合中的元素x，第i（1≤i≤k）個(gè)哈希函數(shù)映射的位置hi（x）就會(huì)被置為1。注意，如果同一個(gè)位置多次被置為1，那么只有第一次是起作用的，后面幾次置位將沒(méi)有任何效果。

如果n=20，k=3，W=（1，2），要判斷3是否在W集合中的示意圖（如圖1）。

首先需要把位數(shù)組通過(guò)集合元素和哈希函數(shù)的運(yùn)算來(lái)置位為1，如圖1。

然后，我們開(kāi)始判斷3是否在w集合中。3與所有的k中的哈希函數(shù)進(jìn)行運(yùn)算，去看運(yùn)算結(jié)果對(duì)應(yīng)的位數(shù)組中的值是否為1，如果都為1則它在w中，如果有一個(gè)結(jié)果不為1，則它不在w中。圖2所示是3不在集合w中，但如果碰巧3是一個(gè)誤報(bào)那么就如圖3所示了。

從上面的例子可以看出Bloom Filter存在誤報(bào)的可能性還是比較大的，那么怎樣能使這種誤報(bào)率降到最低呢？從原理上可以看出Bloom Filter要靠多個(gè)哈希函數(shù)將集合映射到位數(shù)組中，那么哈希函數(shù)的個(gè)數(shù)和位數(shù)組的位數(shù)都會(huì)影響到誤報(bào)率。在哈希函數(shù)方面存在一下兩種情況：一是如果哈希函數(shù)的個(gè)數(shù)多，那么在對(duì)一個(gè)不屬于集合的元素進(jìn)行查詢(xún)時(shí)得到0的概率就大，也就是誤報(bào)率低；另外，如果哈希函數(shù)的個(gè)數(shù)少，那么位數(shù)組中的0就多。

3 Bloom Filter特點(diǎn)

優(yōu)點(diǎn)：由于它的插入時(shí)間和查詢(xún)時(shí)間都是常數(shù)因此具有很高的空間效率和查詢(xún)效率；在查詢(xún)過(guò)程中查詢(xún)?cè)夭槐槐４婢哂辛己玫陌踩?；不存在漏?bào)（False Negative），即某個(gè)元素在某個(gè)集合中，肯定能報(bào)出來(lái)。

缺點(diǎn)：誤識(shí)別率隨著插入元素的增加而遞增；任意元素都不能隨意刪除，刪除將影響多個(gè)元素檢測(cè)；可能存在誤報(bào)（False Positive），即某個(gè)元素不在某個(gè)集合中，可能也被報(bào)出來(lái)。

4 結(jié)語(yǔ)

在計(jì)算機(jī)科學(xué)中，我們常常為了提高效率會(huì)碰到拿時(shí)間換空間或者空間換時(shí)間的情況。而B(niǎo)loom Filter在時(shí)間和空間之外又引入了誤識(shí)別率。在使用Bloom Filter判斷一個(gè)元素是否屬于某個(gè)集合時(shí)，會(huì)有一定的誤識(shí)別率。Bloom Filter用少量的無(wú)識(shí)別率換來(lái)了時(shí)間和空間上的效率。自從70年代問(wèn)世Bloom Filter之后，Bloom Filter就被廣泛用于拼寫(xiě)檢查和數(shù)據(jù)庫(kù)系統(tǒng)中。隨著網(wǎng)絡(luò)的普及和發(fā)展，Bloom Filter在網(wǎng)絡(luò)領(lǐng)域獲得了更為廣泛的應(yīng)用，各種Bloom Filter的優(yōu)化變種和新的應(yīng)用不斷涌現(xiàn)，在將來(lái)，Bloom Filter必將獲得更大的發(fā)展。

參考文獻(xiàn)

[1]肖明忠，代亞非.Bloom Filter及應(yīng)用綜述[J].計(jì)算機(jī)科學(xué)，2004，31（4）.

[2]謝鯤，文吉?jiǎng)?，張大方，?布魯姆過(guò)濾器查詢(xún)算法[J].軟件學(xué)報(bào)，2009，20（1）.