前言

布隆過濾器作為一個精巧且實用的數(shù)據(jù)結(jié)構(gòu)，對于后端程序員來講，學(xué)習(xí)和理解布隆過濾器有很大的必要性。希望通過這篇文章讓更多人了解布隆過濾器的原理，并且會實際去使用它！

什么是布隆過濾器？

布隆過濾器 (Bloom Filter)是由 Burton Howard Bloom 于 1970 年提出，我們可以把它看作由二進制向量（或者說位數(shù)組）和一系列隨機映射函數(shù)（哈希函數(shù)）兩部分組成的數(shù)據(jù)結(jié)構(gòu)。相比于我們平時常用的的 List、Map、Set 等數(shù)據(jù)結(jié)構(gòu)，它占用空間更少并且效率更高，但是缺點是其返回的結(jié)果是概率性的，而不是非常準(zhǔn)確的。理論情況下添加到集合中的元素越多，誤報的可能性就越大。而且，存放在布隆過濾器的數(shù)據(jù)不容易刪除。

Bloom Filter 會使用一個較大的 bit 數(shù)組來保存所有的數(shù)據(jù)，數(shù)組中的每個元素都只占用 1 bit ，并且每個元素只能是 0 或者 1（代表 false 或者 true），這也是 Bloom Filter 節(jié)省內(nèi)存的核心所在。這樣來算的話，申請一個 100w 個元素的位數(shù)組只占用 1000000Bit / 8 = 125000 Byte = 125000/1024 kb ≈ 122kb 的空間。

位數(shù)組

總結(jié)：一個名叫 Bloom 的人提出了一種來檢索元素是否在給定大集合中的數(shù)據(jù)結(jié)構(gòu)，這種數(shù)據(jù)結(jié)構(gòu)是高效且性能很好的，但缺點是具有一定的錯誤識別率和刪除難度。并且，理論情況下，添加到集合中的元素越多，誤報的可能性就越大。

布隆過濾器使用場景

判斷給定數(shù)據(jù)是否存在：比如判斷一個數(shù)字是否存在于包含大量數(shù)字的數(shù)字集中（數(shù)字集很大，上億）、 防止緩存穿透（判斷請求的數(shù)據(jù)是否有效避免直接繞過緩存請求數(shù)據(jù)庫）等等、郵箱的垃圾郵件過濾（判斷一個郵件地址是否在垃圾郵件列表中）、黑名單功能（判斷一個IP地址或手機號碼是否在黑名單中）等等。

網(wǎng)頁爬蟲對URL去重，避免爬取相同的 URL 地址。

比如用戶日常刷新聞，每次推薦給該用戶的內(nèi)容不能重復(fù)，過濾已經(jīng)看過的內(nèi)容。

以上場景都需要判斷給定數(shù)據(jù)是否存在，因此布隆過濾器主要是為了解決海量數(shù)據(jù)的存在性問題。

布隆過濾器的原理介紹

當(dāng)一個元素加入布隆過濾器中的時候，會進行如下操作：

使用布隆過濾器中的哈希函數(shù)對元素值進行計算，得到哈希值（有幾個哈希函數(shù)得到幾個哈希值）。

根據(jù)得到的哈希值，在位數(shù)組中把對應(yīng)下標(biāo)的值置為 1。

當(dāng)我們需要判斷一個元素是否存在于布隆過濾器的時候，會進行如下操作：

對給定元素再次進行相同的哈希計算；

得到值之后判斷位數(shù)組中的每個元素是否都為 1，如果值都為 1，那么說明這個值在布隆過濾器中，如果存在一個值不為 1，說明該元素不在布隆過濾器中。

Bloom Filter 的簡單原理圖如下：

Bloom Filter 的簡單原理示意圖

如圖所示，當(dāng)字符串存儲要加入到布隆過濾器中時，該字符串首先由多個哈希函數(shù)生成不同的哈希值，然后將對應(yīng)的位數(shù)組的下標(biāo)設(shè)置為 1（當(dāng)位數(shù)組初始化時，所有位置均為 0）。當(dāng)?shù)诙未鎯ο嗤址畷r，因為先前的對應(yīng)位置已設(shè)置為 1，所以很容易知道此值已經(jīng)存在（去重非常方便）。

如果我們需要判斷某個字符串是否在布隆過濾器中時，只需要對給定字符串再次進行相同的哈希計算，得到值之后判斷位數(shù)組中的每個元素是否都為 1，如果值都為 1，那么說明這個值在布隆過濾器中，如果存在一個值不為 1，說明該元素不在布隆過濾器中。

不同的字符串可能哈希出來的位置相同，這種情況我們可以適當(dāng)增加位數(shù)組大小或者調(diào)整我們的哈希函數(shù)。

綜上，我們可以得出：布隆過濾器說某個元素存在，小概率會誤判。布隆過濾器說某個元素不在，那么這個元素一定不在。

如何實現(xiàn)布隆過濾器

Guava 實現(xiàn)

Guava 中布隆過濾器的實現(xiàn)算是比較權(quán)威的，所以實際項目中我們不需要自己去實現(xiàn)一個布隆過濾器。

首先我們需要在項目中引入 Guava 的依賴：

com.google.guava
guava
28.0-jre

實際使用如下：

我們創(chuàng)建了一個最多存放 最多 1500 個整數(shù)的布隆過濾器，并且我們可以容忍誤判的概率為百分之（0.01）

//創(chuàng)建布隆過濾器對象
BloomFilterfilter=BloomFilter.create(
Funnels.integerFunnel(),
1500,
0.01);
//判斷指定元素是否存在
System.out.println(filter.mightContain(1));
System.out.println(filter.mightContain(2));
//將元素添加進布隆過濾器
filter.put(1);
filter.put(2);
System.out.println(filter.mightContain(1));
System.out.println(filter.mightContain(2));

在我們的示例中，當(dāng)mightContain()方法返回true時，我們可以 99％確定該元素在過濾器中，當(dāng)過濾器返回false時，我們可以 100％確定該元素不存在于過濾器中。

Guava 提供的布隆過濾器的實現(xiàn)還是很不錯的（想要詳細(xì)了解的可以看一下它的源碼實現(xiàn)），但是它有一個重大的缺陷就是只能單機使用（另外，容量擴展也不容易），而現(xiàn)在互聯(lián)網(wǎng)一般都是分布式的場景。為了解決這個問題，我們就需要用到 Redis 中的布隆過濾器了。

Redis 中的布隆過濾器

Redis v4.0 之后有了 Module（模塊/插件）功能，Redis Modules 讓 Redis 可以使用外部模塊擴展其功能 ，使用戶可以根據(jù)需要額外集成一些實用功能。

審核編輯：劉清