前言

在程序的世界中，布隆過(guò)濾器是程序員的一把利器，利用它可以快速地解決項(xiàng)目中一些比較棘手的問(wèn)題。如網(wǎng)頁(yè) URL 去重、垃圾郵件識(shí)別、大集合中重復(fù)元素的判斷和緩存穿透等問(wèn)題。

布隆過(guò)濾器（Bloom Filter）是 1970 年由布隆提出的。它實(shí)際上是一個(gè)很長(zhǎng)的二進(jìn)制向量和一系列隨機(jī)映射函數(shù)。布隆過(guò)濾器可以用于檢索一個(gè)元素是否在一個(gè)集合中。

它的優(yōu)點(diǎn)是空間效率和查詢時(shí)間都比一般的算法要好的多，缺點(diǎn)是有一定的誤識(shí)別率和刪除困難。

一、布隆過(guò)濾器簡(jiǎn)介

當(dāng)你往簡(jiǎn)單數(shù)組或列表中插入新數(shù)據(jù)時(shí)，將不會(huì)根據(jù)插入項(xiàng)的值來(lái)確定該插入項(xiàng)的索引值。這意味著新插入項(xiàng)的索引值與數(shù)據(jù)值之間沒(méi)有直接關(guān)系。這樣的話，當(dāng)你需要在數(shù)組或列表中搜索相應(yīng)值的時(shí)候，你必須遍歷已有的集合。若集合中存在大量的數(shù)據(jù)，就會(huì)影響數(shù)據(jù)查找的效率。

針對(duì)這個(gè)問(wèn)題，你可以考慮使用哈希表。利用哈希表你可以通過(guò)對(duì) “值” 進(jìn)行哈希處理來(lái)獲得該值對(duì)應(yīng)的鍵或索引值，然后把該值存放到列表中對(duì)應(yīng)的索引位置。這意味著索引值是由插入項(xiàng)的值所確定的，當(dāng)你需要判斷列表中是否存在該值時(shí)，只需要對(duì)值進(jìn)行哈希處理并在相應(yīng)的索引位置進(jìn)行搜索即可，這時(shí)的搜索速度是非常快的。

根據(jù)定義，布隆過(guò)濾器可以檢查值是 “可能在集合中” 還是 “絕對(duì)不在集合中”。“可能” 表示有一定的概率，也就是說(shuō)可能存在一定為誤判率。那為什么會(huì)存在誤判呢？下面我們來(lái)分析一下具體的原因。

布隆過(guò)濾器（Bloom Filter）本質(zhì)上是由長(zhǎng)度為 m 的位向量或位列表（僅包含 0 或 1 位值的列表）組成，最初所有的值均設(shè)置為 0，如下圖所示。

為了將數(shù)據(jù)項(xiàng)添加到布隆過(guò)濾器中，我們會(huì)提供 K 個(gè)不同的哈希函數(shù)，并將結(jié)果位置上對(duì)應(yīng)位的值置為 “1”。在前面所提到的哈希表中，我們使用的是單個(gè)哈希函數(shù)，因此只能輸出單個(gè)索引值。而對(duì)于布隆過(guò)濾器來(lái)說(shuō)，我們將使用多個(gè)哈希函數(shù)，這將會(huì)產(chǎn)生多個(gè)索引值。

如上圖所示，當(dāng)輸入 “semlinker” 時(shí)，預(yù)設(shè)的 3 個(gè)哈希函數(shù)將輸出 2、4、6，我們把相應(yīng)位置 1。假設(shè)另一個(gè)輸入 ”kakuqo“，哈希函數(shù)輸出 3、4 和 7。你可能已經(jīng)注意到，索引位 4 已經(jīng)被先前的 “semlinker” 標(biāo)記了。此時(shí)，我們已經(jīng)使用 “semlinker” 和 ”kakuqo“ 兩個(gè)輸入值，填充了位向量。當(dāng)前位向量的標(biāo)記狀態(tài)為：

當(dāng)對(duì)值進(jìn)行搜索時(shí)，與哈希表類(lèi)似，我們將使用 3 個(gè)哈希函數(shù)對(duì) ”搜索的值“ 進(jìn)行哈希運(yùn)算，并查看其生成的索引值。假設(shè)，當(dāng)我們搜索 ”fullstack“ 時(shí)，3 個(gè)哈希函數(shù)輸出的 3 個(gè)索引值分別是 2、3 和 7：

從上圖可以看出，相應(yīng)的索引位都被置為 1，這意味著我們可以說(shuō) ”fullstack“ 可能已經(jīng)插入到集合中。事實(shí)上這是誤報(bào)的情形，產(chǎn)生的原因是由于哈希碰撞導(dǎo)致的巧合而將不同的元素存儲(chǔ)在相同的比特位上。幸運(yùn)的是，布隆過(guò)濾器有一個(gè)可預(yù)測(cè)的誤判率（FPP）：

• n 是已經(jīng)添加元素的數(shù)量；
• k 哈希的次數(shù)；
• m 布隆過(guò)濾器的長(zhǎng)度（如比特?cái)?shù)組的大?。?；

極端情況下，當(dāng)布隆過(guò)濾器沒(méi)有空閑空間時(shí)（滿），每一次查詢都會(huì)返回 true 。這也就意味著 m 的選擇取決于期望預(yù)計(jì)添加元素的數(shù)量 n ，并且 m 需要遠(yuǎn)遠(yuǎn)大于 n 。

實(shí)際情況中，布隆過(guò)濾器的長(zhǎng)度 m 可以根據(jù)給定的誤判率（FFP）的和期望添加的元素個(gè)數(shù) n 的通過(guò)如下公式計(jì)算：

了解完上述的內(nèi)容之后，我們可以得出一個(gè)結(jié)論，當(dāng)我們搜索一個(gè)值的時(shí)候，若該值經(jīng)過(guò) K 個(gè)哈希函數(shù)運(yùn)算后的任何一個(gè)索引位為 ”0“，那么該值肯定不在集合中。但如果所有哈希索引值均為 ”1“，則只能說(shuō)該搜索的值可能存在集合中。

二、布隆過(guò)濾器應(yīng)用

在實(shí)際工作中，布隆過(guò)濾器常見(jiàn)的應(yīng)用場(chǎng)景如下：

• 網(wǎng)頁(yè)爬蟲(chóng)對(duì) URL 去重，避免爬取相同的 URL 地址；
• 反垃圾郵件，從數(shù)十億個(gè)垃圾郵件列表中判斷某郵箱是否垃圾郵箱；
• Google Chrome 使用布隆過(guò)濾器識(shí)別惡意 URL；
• Medium 使用布隆過(guò)濾器避免推薦給用戶已經(jīng)讀過(guò)的文章；
• Google BigTable，Apache HBbase 和 Apache Cassandra 使用布隆過(guò)濾器減少對(duì)不存在的行和列的查找。 除了上述的應(yīng)用場(chǎng)景之外，布隆過(guò)濾器還有一個(gè)應(yīng)用場(chǎng)景就是解決緩存穿透的問(wèn)題。所謂的緩存穿透就是服務(wù)調(diào)用方每次都是查詢不在緩存中的數(shù)據(jù)，這樣每次服務(wù)調(diào)用都會(huì)到數(shù)據(jù)庫(kù)中進(jìn)行查詢，如果這類(lèi)請(qǐng)求比較多的話，就會(huì)導(dǎo)致數(shù)據(jù)庫(kù)壓力增大，這樣緩存就失去了意義。

利用布隆過(guò)濾器我們可以預(yù)先把數(shù)據(jù)查詢的主鍵，比如用戶 ID 或文章 ID 緩存到過(guò)濾器中。當(dāng)根據(jù) ID 進(jìn)行數(shù)據(jù)查詢的時(shí)候，我們先判斷該 ID 是否存在，若存在的話，則進(jìn)行下一步處理。若不存在的話，直接返回，這樣就不會(huì)觸發(fā)后續(xù)的數(shù)據(jù)庫(kù)查詢。需要注意的是緩存穿透不能完全解決，我們只能將其控制在一個(gè)可以容忍的范圍內(nèi)。

三、布隆過(guò)濾器實(shí)戰(zhàn)

布隆過(guò)濾器有很多實(shí)現(xiàn)和優(yōu)化，由 Google 開(kāi)發(fā)著名的 Guava 庫(kù)就提供了布隆過(guò)濾器（Bloom Filter）的實(shí)現(xiàn)。在基于 Maven 的 Java 項(xiàng)目中要使用 Guava 提供的布隆過(guò)濾器，只需要引入以下坐標(biāo)：

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

在導(dǎo)入 Guava 庫(kù)后，我們新建一個(gè) BloomFilterDemo 類(lèi)，在 main 方法中我們通過(guò) BloomFilter.create 方法來(lái)創(chuàng)建一個(gè)布隆過(guò)濾器，接著我們初始化 1 百萬(wàn)條數(shù)據(jù)到過(guò)濾器中，然后在原有的基礎(chǔ)上增加 10000 條數(shù)據(jù)并判斷這些數(shù)據(jù)是否存在布隆過(guò)濾器中：

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; // 總數(shù)量
        BloomFilter<CharSequence> bf = 
          BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), total);
        // 初始化 1000000 條數(shù)據(jù)到過(guò)濾器中
        for (int i = 0; i < total; i++) {
            bf.put("" + i);
        }
        // 判斷值是否存在過(guò)濾器中
        int count = 0;
        for (int i = 0; i < total + 10000; i++) {
            if (bf.mightContain("" + i)) {
                count++;
            }
        }
        System.out.println("已匹配數(shù)量 " + count);
    }
}

當(dāng)以上代碼運(yùn)行后，控制臺(tái)會(huì)輸出以下結(jié)果：

已匹配數(shù)量 1000309

很明顯以上的輸出結(jié)果已經(jīng)出現(xiàn)了誤報(bào)，因?yàn)橄啾阮A(yù)期的結(jié)果多了 309 個(gè)元素，誤判率為：

309/(1000000 + 10000) * 100 ≈ 0.030594059405940593

如果要提高匹配精度的話，我們可以在創(chuàng)建布隆過(guò)濾器的時(shí)候設(shè)置誤判率 fpp：

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

在 BloomFilter 內(nèi)部，誤判率 fpp 的默認(rèn)值是 0.03：

// com/google/common/hash/BloomFilter.class
public static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions) {
  return create(funnel, expectedInsertions, 0.03D);
}

在重新設(shè)置誤判率為 0.0002 之后，我們重新運(yùn)行程序，這時(shí)控制臺(tái)會(huì)輸出以下結(jié)果：

已匹配數(shù)量 1000003

通過(guò)觀察以上的結(jié)果，可知誤判率 fpp 的值越小，匹配的精度越高。當(dāng)減少誤判率 fpp 的值，需要的存儲(chǔ)空間也越大，所以在實(shí)際使用過(guò)程中需要在誤判率和存儲(chǔ)空間之間做個(gè)權(quán)衡。

四、總結(jié)

本文主要介紹的布隆過(guò)濾器的概念和常見(jiàn)的應(yīng)用場(chǎng)合，在實(shí)戰(zhàn)部分我們演示了 Google 著名的 Guava 庫(kù)所提供布隆過(guò)濾器（Bloom Filter）的基本使用，同時(shí)我們也介紹了布隆過(guò)濾器出現(xiàn)誤報(bào)的原因及如何提高判斷準(zhǔn)確性。最后為了便于大家理解布隆過(guò)濾器，我們介紹了一個(gè)簡(jiǎn)易版的布隆過(guò)濾器 SimpleBloomFilter。

到此這篇關(guān)于Java布隆過(guò)濾器的應(yīng)用實(shí)例的文章就介紹到這了,更多相關(guān)Java布隆過(guò)濾器內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論