在程序的世界中，布隆過濾器是程序員的一把利器，利用它可以快速地解決項目中一些比較棘手的問題。如網頁 URL 去重、垃圾郵件識別、大集合中重複元素的判斷和緩存穿透等問題。
布隆過濾器（Bloom Filter）是 1970 年由布隆提出的。它實際上是一個很長的二進制向量和一系列隨機映射函數。布隆過濾器可以用於檢索一個元素是否在一個集合中。它的優點是空間效率和查詢時間都比一般的算法要好的多，缺點是有一定的誤識別率和刪除困難。
一、布隆過濾器簡介
當你往簡單數組或列表中插入新數據時，將不會根據插入項的值來確定該插入項的索引值。這意味著新插入項的索引值與數據值之間沒有直接關係。這樣的話，當你需要在數組或列表中搜索相應值的時候，你必須遍歷已有的集合。若集合中存在大量的數據，就會影響數據查找的效率。
針對這個問題，你可以考慮使用哈希表。利用哈希表你可以通過對 “值” 進行哈希處理來獲得該值對應的鍵或索引值，然後把該值存放到列表中對應的索引位置。這意味著索引值是由插入項的值所確定的，當你需要判斷列表中是否存在該值時，只需要對值進行哈希處理並在相應的索引位置進行搜索即可，這時的搜索速度是非常快的。
根據定義，布隆過濾器可以檢查值是 “可能在集合中” 還是 “絕對不在集合中”。“可能” 表示有一定的概率，也就是說可能存在一定為誤判率。那為什麼會存在誤判呢？下面我們來分析一下具體的原因。
布隆過濾器（Bloom Filter）本質上是由長度為 m 的位向量或位列表（僅包含 0 或 1 位值的列表）組成，最初所有的值均設置為 0，如下圖所示。
為了將數據項添加到布隆過濾器中，我們會提供 K 個不同的哈希函數，並將結果位置上對應位的值置為 “1”。在前面所提到的哈希表中，我們使用的是單個哈希函數，因此只能輸出單個索引值。而對於布隆過濾器來說，我們將使用多個哈希函數，這將會產生多個索引值。
如上圖所示，當輸入 “semlinker” 時，預設的 3 個哈希函數將輸出 2、4、6，我們把相應位置 1。假設另一個輸入 ”kakuqo“，哈希函數輸出 3、4 和 7。你可能已經注意到，索引位 4 已經被先前的 “semlinker” 標記了。此時，我們已經使用 “semlinker” 和 ”kakuqo“ 兩個輸入值，填充了位向量。當前位向量的標記狀態為：
當對值進行搜索時，與哈希表類似，我們將使用 3 個哈希函數對 ”搜索的值“ 進行哈希運算，並查看其生成的索引值。假設，當我們搜索 ”fullstack“ 時，3 個哈希函數輸出的 3 個索引值分別是 2、3 和 7：
從上圖可以看出，相應的索引位都被置為 1，這意味著我們可以說 ”fullstack“ 可能已經插入到集合中。事實上這是誤報的情形，產生的原因是由於哈希碰撞導致的巧合而將不同的元素存儲在相同的比特位上。幸運的是，布隆過濾器有一個可預測的誤判率（FPP）：
- n 是已經添加元素的數量；
- k 哈希的次數；
- m 布隆過濾器的長度（如比特數組的大小）；
極端情況下，當布隆過濾器沒有空閒空間時（滿），每一次查詢都會返回 true 。這也就意味著 m 的選擇取決於期望預計添加元素的數量 n ，並且 m 需要遠遠大於 n 。
實際情況中，布隆過濾器的長度 m 可以根據給定的誤判率（FFP）的和期望添加的元素個數 n 的通過如下公式計算：
瞭解完上述的內容之後，我們可以得出一個結論，當我們搜索一個值的時候，若該值經過 K 個哈希函數運算後的任何一個索引位為 ”0“，那麼該值肯定不在集合中。但如果所有哈希索引值均為 ”1“，則只能說該搜索的值可能存在集合中。
二、布隆過濾器應用
在實際工作中，布隆過濾器常見的應用場景如下：
- 網頁爬蟲對 URL 去重，避免爬取相同的 URL 地址；
- 反垃圾郵件，從數十億個垃圾郵件列表中判斷某郵箱是否垃圾郵箱；
- Google Chrome 使用布隆過濾器識別惡意 URL；
- Medium 使用布隆過濾器避免推薦給用戶已經讀過的文章；
- Google BigTable，Apache HBbase 和 Apache Cassandra 使用布隆過濾器減少對不存在的行和列的查找。 除了上述的應用場景之外，布隆過濾器還有一個應用場景就是解決緩存穿透的問題。所謂的緩存穿透就是服務調用方每次都是查詢不在緩存中的數據，這樣每次服務調用都會到數據庫中進行查詢，如果這類請求比較多的話，就會導致數據庫壓力增大，這樣緩存就失去了意義。
利用布隆過濾器我們可以預先把數據查詢的主鍵，比如用戶 ID 或文章 ID 緩存到過濾器中。當根據 ID 進行數據查詢的時候，我們先判斷該 ID 是否存在，若存在的話，則進行下一步處理。若不存在的話，直接返回，這樣就不會觸發後續的數據庫查詢。需要注意的是緩存穿透不能完全解決，我們只能將其控制在一個可以容忍的範圍內。
三、布隆過濾器實戰
布隆過濾器有很多實現和優化，由 Google 開發著名的 Guava 庫就提供了布隆過濾器（Bloom Filter）的實現。在基於 Maven 的 Java 項目中要使用 Guava 提供的布隆過濾器，只需要引入以下座標：
在導入 Guava 庫後，我們新建一個 BloomFilterDemo 類，在 main 方法中我們通過 BloomFilter.create 方法來創建一個布隆過濾器，接著我們初始化 1 百萬條數據到過濾器中，然後在原有的基礎上增加 10000 條數據並判斷這些數據是否存在布隆過濾器中：
當以上代碼運行後，控制檯會輸出以下結果：
已匹配數量 1000309
很明顯以上的輸出結果已經出現了誤報，因為相比預期的結果多了 309 個元素，誤判率為：
309/(1000000 + 10000) * 100 ≈ 0.030594059405940593
如果要提高匹配精度的話，我們可以在創建布隆過濾器的時候設置誤判率 fpp：
在 BloomFilter 內部，誤判率 fpp 的默認值是 0.03：
在重新設置誤判率為 0.0002 之後，我們重新運行程序，這時控制檯會輸出以下結果：
已匹配數量 1000003
通過觀察以上的結果，可知誤判率 fpp 的值越小，匹配的精度越高。當減少誤判率 fpp 的值，需要的存儲空間也越大，所以在實際使用過程中需要在誤判率和存儲空間之間做個權衡。
四、總結
本文主要介紹的布隆過濾器的概念和常見的應用場合，在實戰部分我們演示了 Google 著名的 Guava 庫所提供布隆過濾器（Bloom Filter）的基本使用，同時我們也介紹了布隆過濾器出現誤報的原因及如何提高判斷準確性。最後為了便於大家理解布隆過濾器，我們介紹了一個簡易版的布隆過濾器 SimpleBloomFilter。
原文：https://juejin.im/post/5de1e37c5188256e8e43adfc
閱讀更多 Java識堂 的文章
