一、概念

Bloom Filter的中文翻譯叫做布隆過濾器，是1970年由布隆提出的。它實際上是一個很長的二進制向量和一系列隨機映射函數。布隆過濾器可以用于檢索一個元素是否在一個集合中。它的優點是空間效率和查詢時間都遠遠超過一般的算法，缺點是有一定的誤識別率和刪除困難。如文章標題所述，本文只是做簡單介紹，屬于科普文章。

二、應用場景

在正式介紹Bloom Filter算法之前，先來看看什么時候需要用到Bloom Filter算法。

1. HTTP緩存服務器、Web爬蟲等

主要工作是判斷一條URL是否在現有的URL集合之中（可以認為這里的數據量級上億）。

• 對于HTTP緩存服務器，當本地局域網中的PC發起一條HTTP請求時，緩存服務器會先查看一下這個URL是否已經存在于緩存之中，如果存在的話就沒有必要去原始的服務器拉取數據了（為了簡單起見，我們假設數據沒有發生變化），這樣既能節省流量，還能加快訪問速度，以提高用戶體驗。
• 對于Web爬蟲，要判斷當前正在處理的網頁是否已經處理過了，同樣需要當前URL是否存在于已經處理過的URL列表之中。

2. 垃圾郵件過濾

假設郵件服務器通過發送方的郵件域或者IP地址對垃圾郵件進行過濾，那么就需要判斷當前的郵件域或者IP地址是否處于黑名單之中。如果郵件服務器的通信郵件數量非常大（也可以認為數據量級上億），那么也可以使用Bloom Filter算法。

幾個專業術語

這里有必要介紹一下False Positive和False Negative的概念（更形象的描述可以閱讀第4條參考）。

• False Positive中文可以理解為“假陽性”，形象的一點說就是“誤報”，后面將會說道Bloom Filter存在誤報的情況，現實生活中也有誤報，比如說去體檢的時候，醫生告訴你XXX檢測是陽性，而實際上是陰性，也就是說誤報了，是假陽性，殺毒軟件誤報也是同樣的概念。
• False Negative，中文可以理解為“假陰性”，形象的一點說是“漏報”。醫生告訴你XXX檢測為陰性，實際上你是陽性，你是有病的（Sorry, it’s just a joke），那就是漏報了。同樣殺毒軟件也存在漏報的情況。

?

三、Bloom Filter算法

初始狀態下，Bloom Filter是一個m位的位數組，且數組被0所填充。同時，我們需要定義k個不同的hash函數，每一個hash函數都隨機的將每一個輸入元素映射到位數組中的一個位上。那么對于一個確定的輸入，我們會得到k個索引。

插入元素：經過k個hash函數的映射，我們會得到k個索引，我們把位數組中這k個位置全部置1（不管其中的位之前是0還是1）

查詢元素：輸入元素經過k個hash函數的映射會得到k個索引，如果位數組中這k個索引任意一處是0，那么就說明這個元素不在集合之中；如果元素處于集合之中，那么當插入元素的時候這k個位都是1。但如果這k個索引處的位都是1，被查詢的元素就一定在集合之中嗎？答案是不一定，也就是說出現了False Positive的情況（但Bloom Filter不會出現False Negative的情況)

在上圖中，當插入x、y、z這三個元素之后，再來查詢w，會發現w不在集合之中，而如果w經過三個hash函數計算得出的結果所得索引處的位全是1，那么Bloom Filter就會告訴你，w在集合之中，實際上這里是誤報，w并不在集合之中。

?

False Positive Rate

Bloom Filter的誤報率到底有多大？下面在數學上進行一番推敲。假設HASH函數輸出的索引值落在m位的數組上的每一位上都是等可能的。那么，對于一個給定的HASH函數，在進行某一個運算的時候，一個特定的位沒有被設置為1的概率是

那么，對于所有的k個HASH函數，都沒有把這個位設置為1的概率是

如果我們已經插入了n個元素，那么對于一個給定的位，這個位仍然是0的概率是

那么，如果插入n個元素之后，這個位是1的概率是

如果對一個特定的元素存在誤報，那么這個元素的經過HASH函數所得到的k個索引全部都是1，概率也就是

根據常數e的定義，可以近似的表示為：

?

關于誤報

有時候誤報對實際操作并不會帶來太大的影響，比如對于HTTP緩存服務器，如果一條URL被誤以為存在與緩存服務器之中，那么當取數據的時候自然會無法取到，最終還是要從原始服務器當中獲取，之后再把記錄插入緩存服務器，幾乎沒有什么不可以接受的。
對于安全軟件，有著“另可錯報，不可誤報”的說法，如果你把一個正常軟件誤判為病毒，對使用者來說不會有什么影響（如果用戶相信是病毒，那么就是刪除這個文件罷了，如果用戶執意要執行，那么后果也只能由用戶來承擔）；如果你把一個病毒漏判了，那么對用戶造成的后果是不可設想的……更有甚者，誤報在某種程度上能讓部分用戶覺得你很專業……

參考資料：

1.?Bloom Filter 算法簡介 (增加 Counting Bloom Filter 內容