摘 要：Bloom Filter是一種空間和時間效率很高的二進制項量數(shù)據(jù)結構，它利用位數(shù)組很簡單地表示一個集合，并能檢索一個元素是否屬于這個集合。Bloom Filter的高效檢索是由有一定誤報率換來的。因此，Bloom Filter只適合那些允許一定誤報率的應用場合。

關鍵詞：Bloom Filter 哈希函數(shù) 漏報 誤報

中圖分類號：TP311.12 文獻標識碼：A 文章編號：1672-3791（2013）04（a）-0011-01

1 Bloom Filter

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

2 Bloom Filter原理

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

工作效率低下讓人難以容忍，這時候我們可以考慮利用哈希表哈希函數(shù)這個數(shù)據(jù)結構。哈希函數(shù)在計算機領域，尤其是數(shù)據(jù)快速查找領域，加密領域用的極廣。其作用是將一個大的數(shù)據(jù)集映射到一個小的數(shù)據(jù)集上面。哈希表是根據(jù)哈希值（Key value）而直接進行訪問的數(shù)據(jù)結構。也就是說，它通過把哈希值映射到表中一個位置來訪問記錄，以加快查找的速度?；蛘咭部梢哉J為哈希表是通過一個Hash函數(shù)將一個元素映射到一個位陣列（Bit array）中的一個點。這樣就簡單了，只要看陣列中這個點是不是1就知道判斷出他在不在集合中了。這實際上就是Bloom Filter的基本思路。

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

下面我們舉一簡單的例子來看Bloom Filter是如何工作的。

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

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

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

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

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

3 Bloom Filter特點

優(yōu)點：由于它的插入時間和查詢時間都是常數(shù)因此具有很高的空間效率和查詢效率；在查詢過程中查詢元素不被保存具有良好的安全性；不存在漏報（False Negative），即某個元素在某個集合中，肯定能報出來。

缺點：誤識別率隨著插入元素的增加而遞增；任意元素都不能隨意刪除，刪除將影響多個元素檢測；可能存在誤報（False Positive），即某個元素不在某個集合中，可能也被報出來。

4 結語

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

參考文獻

[1]肖明忠，代亞非.Bloom Filter及應用綜述[J].計算機科學，2004，31（4）.

[2]謝鯤，文吉剛，張大方，等.布魯姆過濾器查詢算法[J].軟件學報，2009，20（1）.