在上一篇 Java 多線程爬蟲及分佈式爬蟲架構探索 中，我們使用了 JDK 自帶的 Set 集合來進行 URL 去重，看上去效果不錯，但是這種做法有一個致命了缺陷，就是隨著採集的 URL 增多，你需要的內存越來越大，最終會導致你的內存崩潰。那我們在不使用數據庫的情況下有沒有解決辦法呢？還記得我們在上一篇文章中提到的布隆過濾器嗎？它就可以完美解決這個問題，布隆過濾器有什麼特殊的地方呢？接下來就一起來學習一下布隆過濾器。

什麼是布隆過濾器

布隆過濾器是一種數據結構，比較巧妙的概率型數據結構，它是在 1970 年由一個名叫布隆提出的，它實際上是由一個很長的二進制向量和一系列隨機映射函數組成，這點跟哈希表有些相同，但是相對哈希表來說布隆過濾器它更高效、佔用空間更少，布隆過濾器有一個缺點那就是有一定的誤識別率和刪除困難。布隆過濾器只能告訴你某個元素一定不存在或者可能存在在集合中， 所以布隆過濾器經常用來處理可以忍受判斷失誤的業務，比如爬蟲 URL 去重。

布隆過濾器原理

在說布隆過濾器原理之前，我們先來複習一下哈希表，在上一篇文章中，我們利用的是 Set 來進行 URL 去重，我們來看看 Set 的存儲模型

URL 經過一個哈希函數後，將 URL 存入了數組裡，這樣查詢時也是非常高效的，但是由於數組裡存入的是 URL，隨著 URL 的增多，需要的數組越來越大，意味著你需要更多的內存，比如我們採集了幾億的 URL，那麼可能就需要上百G 的內存，這是條件不允許的，因為內存特別的昂貴，所以這個在 url 去重中是不可取的，佔內存更小的布隆過濾器就是一種不錯的選擇。

布隆過濾器實質上由長度為 m 的位向量或位列表（僅包含 0 或 1 位值的列表）組成，最初所有值均設置為 0，如下所示。

因為底層是 bit 數組，所以意味著數組只有 0、1 兩個值，跟哈希表一樣，我們將 URL 通過 K 個函數映射 bit 數組裡，並且將指向的 Bit 數組對應的值改成 1 。我們以存 /nba/2492297.html 為例，如下圖所示：

/nba/2492297.html經過三個哈希函數分別映射到了 1、4、9 的位置，這三個 bit 數組的值就變成了 1，我們再存入一個 /nba/2492298.html，此時 bit 數組就變成下面這樣：

/nba/2492298.html被映射到了 0、4、11 的位置，所以此時 bit 數組上有 5 個位置的值為 1，本應該是有 6 個值為 1 的，但是因為在 4 這個位置重複了，所以會覆蓋。

布隆過濾器是如何判斷某個值一定不存在或者可能存在呢？通過判斷哈希函數映射到對應數組的值，如果都為 1，說明可能存在，如果有一個不為 1，說明一定不存在。對於一定不存在好理解，但是都為 1 時，為什麼說可能存在呢？這跟哈希表一樣，哈希函數會產生哈希衝突，也就是說兩個不同的值經過哈希函數都會得到同一個數組下標，布隆過濾器也是一樣的。我們以判斷 /nba/2492299.html 是否已經採集過為例，經過哈希函數映射的 bit 數組上的位置入下圖所示：

/nba/2492299.html 被哈希函數映射到了 4、9、11 的位置，而這幾個位置的值都為 1 ，所以布隆過濾器就認為 /nba/2492299.html 被採集過了，實際上是沒有采集過的，這就說明了布隆過濾器存在誤判，這也是我們業務允許的。布隆過濾器的誤判率跟 bit 數組的大小和哈希函數的個數有關係，如果 bit 數組過小，哈希函數過多，那麼 bit 數組的值很快都會變成 1，這樣誤判率就會越來越高，bit 數組過大，就會浪費更多的內存，所以就要平衡好 bit 數組的大小和哈希函數的個數，關於如何平衡這兩個的關係，不是我們這篇文章的重點。

布隆過濾器的原理我們已經瞭解了，為了加深對布隆過濾器的理解，我們用 Java 來實現一個簡易辦的布隆過濾器，代碼如下：

把上面這段代碼理解好對我們理解布隆過濾器非常有幫助，實際上在工作中並不需要我們自己實現布隆過濾器，谷歌已經幫我們實現了布隆過濾器，在 Guava 包中提供了 BloomFilter，這個布隆過濾器實現的非常棒，下面就看看谷歌辦的布隆過濾器。

布隆過濾器 Guava 版

要使用 Guava 包下提供的 BloomFilter ，就需要引入 Guava 包，我們在 pom.xml 中引入下面依賴：

Guava 中的布隆過濾器實現的非常複雜，關於細節我們就不去探究了，我們就來看看 Guava 中布隆過濾器的構造函數吧，Guava 中並沒有提供構造函數，而且提供了 create 方法來構造布隆過濾器：

funnel：你要過濾數據的類型

expectedInsertions：你要存放的數據量

fpp：誤判率

你只需要傳入這三個參數你就可以使用 Guava 包中的布隆過濾器了，下面這我寫的一段 Guava 布隆過濾器測試程序，可以改動 fpp 多運行幾次，體驗 Guava 的布隆過濾器。

布隆過濾器的應用

緩存擊穿

緩存擊穿是查詢數據庫中不存在的數據，如果有用戶惡意模擬請求很多緩存中不存在的數據，由於緩存中都沒有，導致這些請求短時間內直接落在了DB上，對DB產生壓力，導致數據庫異常。

最常見的解決辦法就是採用布隆過濾器，將所有可能存在的數據哈希到一個足夠大的bitmap中，一個一定不存在的數據會被這個bitmap攔截掉，從而避免了對底層存儲系統的查詢壓力。下面是一段偽代碼：

爬蟲 URL 去重

爬蟲是對 url 的去重，防止 url 重複採集，這也是我們這篇文章重點講解的內容

垃圾郵件識別

從數十億個垃圾郵件列表中判斷某郵箱是否垃圾郵箱，將垃圾郵箱添加到布隆過濾器中，然後判斷某個郵件是否是存在在布隆過濾器中，存在說明就是垃圾郵箱。

作者：平頭哥的技術博文
來源：掘金
商業用途請與原作者聯繫，本文只做展示分享，不妥侵刪！