在設計應用程序時，我們經常會遇到這樣的場景：檢查某個元素是否存在于集合中。例如，當創建一個新的電子郵件帳戶時，你需要輸入一個電子郵件地址。系統會告訴你電子郵件地址是否已被占用。如果已經參加，你將測試不同的，直到找到可用的。

在后端，系統會根據數百萬個現有電子郵件地址檢查你的電子郵件地址，以檢查是否存在匹配項。并且系統會在幾分之一秒內回答你。傳統的索引線性搜索無法快速給出結果。哈希映射可以完成這項工作，但它會占用大量內存空間。

布隆過濾器是上述用例的最佳解決方案。它的最佳場景實踐如下：

• 需要快速檢查某個項目是否在列表中。
• 列表很大，內存空間有限。

什么是布隆過濾器？

布隆過濾器（Bloom filter）是一種概率數據結構，由 Burton Howard Bloom 于 1970 年設計，用于檢查元素是否是集合的成員。

布隆過濾器提供的快速查找有一個陷阱——誤報。誤報是指集合中不存在某個元素，但系統告訴你它存在的情況。不過誤報的概率通常比較低。

布隆過濾器如何工作？

布隆過濾器是m位的位向量，最初全部設置為 0。

例如，下面是一個 12 位布隆過濾器。所有位最初都是 0。位下方的數字表示該位的索引。索引從 0 開始到m-1（在本例中為 11）。

要將元素添加到布隆過濾器，我們需要k個哈希函數。每個要加入布隆過濾器的元素都會經過k個哈希函數，得到k個固定大小的哈希值。

接下來，我們對每個哈希值（在我們的例子中是哈希值 % 12 ）取m的模，以獲得小于或等于 m-1 的索引。通過操作獲得的索引中存在的位在位向量中設置為 1。使用相同的方法繼續將每個元素添加到布隆過濾器。

除了向過濾器添加元素外，我們還可以檢查它們是否存在與過濾器中。為了檢查元素是否存在，我們使用與上述相同的過程對元素執行哈希和取模。獲得索引后，檢查這些索引中存在的位的值，以推斷該元素是否存在。通過下面的示例，來更好地理解這個概念。

請注意，你只能將元素添加到布隆過濾器或檢查元素是否存在與過濾器中。添加后，無法從過濾器中刪除元素。

例子

假設我們有一個 12 位布隆過濾器和 3 個哈希函數 h1(x)、h2(x)、h3(x)。首先，我們將向布隆過濾器添加元素。接下來，我們將檢查過濾器中是否存在元素。

向過濾器添加元素

把字符串“white”添加到空的布隆過濾器中。

將它提供給我們示例中的三個哈希函數，并取 12 的模作為結果，如下：

將索引 2、10 和 7 處的位設置為 1。布隆過濾器將變成這樣：

接下來，添加另一個元素“blue”。

將字符串提供給三個散列函數并取模，我們得到另外 3 個要設置的索引：

索引 4、1 和 11 處的位也將設置為 1。現在布隆過濾器如下所示：

檢查元素是否在過濾器中

現在我們的布隆過濾器有一些元素（本例中為“white”和“blue”）。讓我們檢查集合中是否存在元素“purple”。

對“purple”執行相同的操作，找到它的哈希值并取模：

檢查上面計算的索引處的位值。如果所有三個索引的位都是 1，我們可以說過濾器中可能存在“purple”。如果這些索引處的至少一位為 0，我們可以說過濾器中不存在“purple”。

由于上圖中索引 6 和 9 的位為 0，我們知道“purple”不在過濾器中。

接下來，我們檢查過濾器中是否有“blue”。

對“blue”執行哈希函數和取模來獲得索引：

接下來，檢查上述索引處的位值：

所有三個位置的位都已設置，那么元素“blue”可能出現在過濾器中。

布隆過濾器為什么會出誤報？

我們之前提到布隆過濾器有時會給出誤報結果。這就是為什么如果布隆過濾器在檢查元素是否存在時給出肯定結果，我們只能說元素“可能”存在于集合中。為什么這樣？為什么結果不是 100% 準確？

讓我們用一個例子來證明一下。

布隆過濾器中有“white”和“blue”兩個元素時，狀態如下：

讓我們檢查一下過濾器中是否存在“black”。對“black”進行哈希和取模，如下：

接下來，檢查布隆過濾器中索引 11、7 和 1 處的內容。

可以看到，所有三個索引處的位均是1。所以布隆過濾器告訴我們集合中可能存在“black”。

但是，由于我們只向過濾器添加了“white”和“blue”，我們一開始就知道“black”不存在！因此布隆過濾器在這種情況下給出了“誤報”。

產生誤報的過程是這樣的：當“white”被添加到過濾器時，索引 7 的位被設置，而當“blue”被添加到過濾器時，索引 1 和 11 的位被設置。現在，當算法看到 11、7 和 1 的位已設置時，它判斷“black”可能在過濾器中。

減少誤報

如果應用程序需要較低的誤報概率，可以通過一些方法來控制它。增加位數組的大小和散列函數的數量可以提高結果的效率并降低誤報的概率。

然而，增加哈希函數的數量也會增加布隆過濾器的插入和查找操作的延遲。布隆過濾器的時間復雜度為 O(k)，其中 k 是涉及的哈希函數的數量。

布隆過濾器的應用

作為一種可以快速檢查元素成員關系且節省空間的數據結構，布隆過濾器具有眾多應用。這里有些例子：

• 緩存系統：在緩存系統中，布隆過濾器可以用來快速判斷某個對象是否存在于緩存中，從而避免查詢數據庫或外部服務。
• 網絡爬蟲：在網絡爬蟲中，布隆過濾器可以用來過濾已經抓取過的URL，從而避免重復抓取。
• 反垃圾郵件：在反垃圾郵件系統中，布隆過濾器可以用來過濾已知的垃圾郵件地址，從而避免將郵件發送到這些地址。
• 分布式系統：在分布式系統中，布隆過濾器可以用來維護分布式哈希表的鍵值對，從而避免向所有節點廣播查詢請求。
• 數據庫優化：在數據庫中，布隆過濾器可以用來加速模糊查詢，例如在大型電話號碼列表中查找以特定數字開頭的號碼。

結論

到現在為止，希望你能更好地理解什么是簡單的布隆過濾器、它是如何工作的，以及關于如何將其應用于現實生活用例的一些想法。基本設計可能會有所不同，具體取決于應用程序的要求。例如，計數布隆過濾器可以在需要刪除元素的應用程序中實現。