什麼是Java布隆過濾器?如何使用你知道嗎

2022-02-09 19:00:24

確實可以將值對映到 HashMap 的 Key，然後可以在 O(1) 的時間複雜度內返回結果，效率奇高。但是 HashMap 的實現也有缺點，例如儲存容量佔比高，考慮到負載因子的存在，通常空間是不能被用滿的，而一旦你的值很多例如上億的時候，那 HashMap 佔據的記憶體大小就變得很可觀了。

一、布隆過濾器簡介

布隆過濾器（英語：Bloom Filter）是1970年由布隆提出的。它實際上是一個很長的二進位制向量和一系列隨機對映函數。布隆過濾器可以用於檢索一個元素是否在一個集合中

如果想判斷一個元素是不是在一個集合裡，一般想到的是將集合中所有元素儲存起來，然後通過比較確定。連結串列、樹、雜湊表（又叫雜湊表，Hash table）等等資料結構都是這種思路。但是隨著集合中元素的增加，我們需要的儲存空間越來越大。同時檢索速度也越來越慢，上述三種結構的檢索時間複雜度分別為O(n),O(log n),O(1)。

布隆過濾器的原理是，當一個元素被加入集合時，通過K個雜湊函數將這個元素對映成一個位陣列中的K個點，把它們置為1。檢索時，我們只要看看這些點是不是都是1就（大約）知道集合中有沒有它了：如果這些點有任何一個0，則被檢元素一定不在；如果都是1，則被檢元素很可能在。這就是布隆過濾器的基本思想。 –引自《維基百科，自由的百科全書》

本質上布隆過濾器是一種資料結構，比較巧妙的概率型資料結構（probabilistic data structure）高效地插入和查詢，可以用來告訴你 “某樣東西一定不存在或者可能存在”。相比於傳統的 List、Set、Map 等資料結構，它更高效、佔用空間更少，但是缺點是其返回的結果是概率性的，而不是確切的。

當你往簡單陣列或列表中插入新資料時，將不會根據插入項的值來確定該插入項的索引值。這意味著新插入項的索引值與資料值之間沒有直接關係。這樣的話，當你需要在陣列或列表中搜尋相應值的時候，你必須遍歷已有的集合。若集合中存在大量的資料，就會影響資料查詢的效率。

針對這個問題，你可以考慮使用雜湊表。利用雜湊表你可以通過對 “值” 進行雜湊處理來獲得該值對應的鍵或索引值，然後把該值存放到列表中對應的索引位置。這意味著索引值是由插入項的值所確定的，當你需要判斷列表中是否存在該值時，只需要對值進行雜湊處理並在相應的索引位置進行搜尋即可，這時的搜尋速度是非常快的。

二、布隆過濾器的結構

根據定義，布隆過濾器可以檢查值是 “可能在集合中” 還是 “絕對不在集合中”。“可能” 表示有一定的概率，也就是說可能存在一定為誤判率。那為什麼會存在誤判呢？下面我們來分析一下具體的原因。

布隆過濾器（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“ 可能已經插入到集合中。事實上這是誤報的情形，產生的原因是由於雜湊碰撞導致的巧合而將不同的元素儲存在相同的位元位上。

那麼我們如何選擇雜湊函數個數和布隆過濾器長度很顯然，過小的布隆過濾器很快所有的bit位均為1，那麼查詢任何值都會返回“可能存在”，起不到過濾的目的了。布隆過濾器的長度會直接影響誤報率，布隆過濾器越長其誤報率越小。

另外，雜湊函數的個數也需要權衡，個數越多則布隆過濾器 bit 位置位 1 的速度越快，且布隆過濾器的效率越低；但是如果太少的話，那我們的誤報率會變高。

如何選擇適合業務的 k 和 m 值呢，幸運的是，布隆過濾器有一個可預測的誤判率（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 是否存在，若存在的話，則進行下一步處理。若不存在的話，直接返回，這樣就不會觸發後續的資料庫查詢。需要注意的是快取穿透不能完全解決，我們只能將其控制在一個可以容忍的範圍內。

四、布隆過濾器的優缺點

優點

相比於其它的資料結構，布隆過濾器在空間和時間方面都有巨大的優勢。布隆過濾器儲存空間和插入/查詢時間都是常數（O(k)）。另外，雜湊函數相互之間沒有關係，方便由硬體並行實現。布隆過濾器不需要儲存元素本身，在某些對保密要求非常嚴格的場合有優勢。

布隆過濾器可以表示全集，其它任何資料結構都不能；

k和m相同，使用同一組雜湊函數的兩個布隆過濾器的交併運算可以使用位元運算進行。

缺點

但是布隆過濾器的缺點和優點一樣明顯。誤算率是其中之一。隨著存入的元素數量增加，誤算率隨之增加。但是如果元素數量太少，則使用雜湊表足矣。

另外，一般情況下不能從布隆過濾器中刪除元素。我們很容易想到把位陣列變成整數陣列，每插入一個元素相應的計數器加1, 這樣刪除元素時將計數器減掉就可以了。然而要保證安全地刪除元素並非如此簡單。首先我們必須保證刪除的元素的確在布隆過濾器裡面。這一點單憑這個過濾器是無法保證的。另外計數器迴繞也會造成問題。

在降低誤算率方面，有不少工作，使得出現了很多布隆過濾器的變種。

五、布隆過濾器實戰

布隆過濾器有很多實現和優化，由 Google 開發著名的 Guava 庫就提供了布隆過濾器（Bloom Filter）的實現。在基於 Maven 的 Java 專案中要使用 Guava 提供的布隆過濾器，只需要引入以下座標：

<dependency>
   <groupId>com.google.guava</groupId>
   <artifactId>guava</artifactId>
   <version>28.0-jre</version>
</dependency>

複製程式碼在匯入 Guava 庫後，我們新建一個 BloomFilterDemo 類，在 main 方法中我們通過 BloomFilter.create 方法來建立一個布隆過濾器，接著我們初始化 1 百萬條資料到過濾器中，然後在原有的基礎上增加 10000 條資料並判斷這些資料是否存在布隆過濾器中：

import com.google.common.base.Charsets;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;

public class BloomFilterDemo {
    public static void main(String[] args) {
        int total = 1000000; // 總數量
        BloomFilter<CharSequence> bf = 
          BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), total);
        // 初始化 1000000 條資料到過濾器中
        for (int i = 0; i < total; i++) {
            bf.put("" + i);
        }
        // 判斷值是否存在過濾器中
        int count = 0;
        for (int i = 0; i < total + 10000; i++) {
            if (bf.mightContain("" + i)) {
                count++;
            }
        }
        System.out.println("已匹配數量 " + count);
    }
}

當以上程式碼執行後，控制檯會輸出以下結果：

已匹配數量 1000309

很明顯以上的輸出結果已經出現了誤報，因為相比預期的結果多了 309 個元素，誤判率為：

309/(1000000 + 10000) * 100 ≈ 0.030594059405940593

如果要提高匹配精度的話，我們可以在建立布隆過濾器的時候設定誤判率 fpp：

BloomFilter<CharSequence> bf = BloomFilter.create(
Funnels.stringFunnel(Charsets.UTF_8), total, 0.0002
);

在 BloomFilter 內部，誤判率 fpp 的預設值是 0.03：

// com/google/common/hash/BloomFilter.classpublic static &lt;T&gt; BloomFilter&lt;T&gt; create(Funnel&lt;? super T&gt; funnel, long expectedInsertions) {  return create(funnel, expectedInsertions, 0.03D);}

在重新設定誤判率為 0.0002 之後，我們重新執行程式，這時控制檯會輸出以下結果：

已匹配數量 1000003

複製程式碼通過觀察以上的結果，可知誤判率 fpp 的值越小，匹配的精度越高。當減少誤判率 fpp 的值，需要的儲存空間也越大，所以在實際使用過程中需要在誤判率和儲存空間之間做個權衡。

六、總結

本文主要介紹的布隆過濾器的概念和常見的應用場合，在實戰部分我們演示了 Google 著名的 Guava 庫所提供布隆過濾器（Bloom Filter）的基本使用，同時我們也介紹了布隆過濾器出現誤報的原因及如何提高判斷準確性。最後為了便於大家理解布隆過濾器，我們介紹了一個簡易版的布隆過濾器 SimpleBloomFilter。

本篇文章就到這裡了，希望能夠給你帶來幫助，也希望您能夠多多關注it145.com的更多內容!