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

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

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

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

什么是布隆過濾器？

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

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

布隆過濾器如何工作？

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

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

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

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

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

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

例子

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

向過濾器添加元素

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

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

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

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

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

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

檢查元素是否在過濾器中

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

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

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

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

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

對“blue”執(zhí)行哈希函數(shù)和取模來獲得索引：

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

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

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

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

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

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

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

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

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

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

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

減少誤報

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

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

布隆過濾器的應用

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

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

結論

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