淺析Bloom Filter

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

關鍵詞：Bloom Filter 哈希函數 漏報 誤報

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

1 Bloom Filter

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

2 Bloom Filter原理

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

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

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

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

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

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

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

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

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

3 Bloom Filter特點

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

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

4 結語

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

參考文獻

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

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