1、什么是布隆過濾器

以下定義來自百度百科：

布隆過濾器（Bloom Filter）是1970年由布隆提出的。它實(shí)際上是一個很長的二進(jìn)制向量和一系列隨機(jī)映射函數(shù)。布隆過濾器可以用于檢索一個元素是否在一個集合中。它的優(yōu)點(diǎn)是空間效率和查詢時間都比一般的算法要好的多，缺點(diǎn)是有一定的誤識別率和刪除困難。

從上述定義我們可以得到以下關(guān)鍵信息：

• 布隆過濾器是由很長的二進(jìn)制向量（即可以理解成很長的0、1數(shù)組）與一系列隨機(jī)映射函數(shù)（Hash函數(shù)）構(gòu)成。
• 布隆過濾器的作用是檢索一個元素是否存在我們的集合之中。
• 優(yōu)點(diǎn)是空間效率和查詢時間都比一般的算法要好的多；缺點(diǎn)是有一定的誤識別率和刪除困難。

注意！接下來的原理我們都會基于定義來逐句解釋和講解布隆過濾器，請大家記住上述三點(diǎn)關(guān)鍵信息。

2、布隆過濾器的原理

2.1 布隆過濾器的數(shù)據(jù)結(jié)構(gòu)

我們從定義總結(jié)的關(guān)鍵信息可知：布隆過濾器是由很長的二進(jìn)制向量（即可以理解成很長的0、1數(shù)組）與一系列隨機(jī)映射函數(shù)（Hash函數(shù)）構(gòu)成。因此我們可以將布隆過濾器理解成下圖這種很長的一個二進(jìn)制數(shù)組：

正是由于布隆過濾器的數(shù)據(jù)結(jié)構(gòu)僅需要存儲“0”或“1”，因此所占用內(nèi)存極少，這也是布隆過濾器的一大優(yōu)點(diǎn)。 

2.2 布隆過濾器的檢索和插入原理

從上圖布隆過濾器的數(shù)據(jù)結(jié)構(gòu)圖和定義的關(guān)鍵信息我們可以知道：布隆過濾器實(shí)際上是個很長的二進(jìn)制數(shù)組，作用是檢索一個元素是否存在我們的集合之中。那么布隆過濾器是如何通過上述數(shù)據(jù)結(jié)構(gòu)判斷一個元素是否存在我們的集合之中的呢？

這里就需要用到我們定義中提到的“一系列隨機(jī)映射函數(shù)（Hash函數(shù)）”了。

首先我們需要知道什么是Hash函數(shù)？這里我們給出Hash函數(shù)的一個簡要的說明：

簡單來說Hash函數(shù)就是把輸入值通過特定方式（hash函數(shù)） 處理后 生成一個值，這個值等同于存放數(shù)據(jù)的地址。

 比如我們當(dāng)前的Hash函數(shù)是 y=x²&（len-1），這里y是指最終在布隆過濾器的數(shù)據(jù)結(jié)構(gòu)（二進(jìn)制數(shù)組）中存放的下標(biāo)位置，x指我們傳入的值，len指數(shù)組的長度。那么如果當(dāng)數(shù)組長度為100（舉個例子，實(shí)際上數(shù)組長度是很長的），傳入的值為5，則我們通過Hash函數(shù)得到的下標(biāo)為25。那么此時我們便將下標(biāo)25的值從0標(biāo)為1。這就是插入（增加）數(shù)據(jù)的原理。

插入（增加）數(shù)據(jù)流程圖如下：

那么，當(dāng)我們下次再輸入這個值的時候，我們會得到當(dāng)前數(shù)組對應(yīng)下標(biāo)的值為1，說明我們有這個數(shù)字！這是不是就是檢索的原理了！

檢索流程圖如下：

當(dāng)然，這里有基礎(chǔ)的同學(xué)肯定會發(fā)現(xiàn)我們上述說的過程雖然很簡單，但是存在很大的問題：

①存在Hash沖突導(dǎo)致誤判：

首先我們先對Hash沖突作一個簡要說明：

根據(jù)key（鍵值）即經(jīng)過一個Hash函數(shù)F(key)得到的結(jié)果的作為地址去存放當(dāng)前的value值，但是卻發(fā)現(xiàn)算出來的地址上已經(jīng)被占用了，這就是所謂的hash沖突。

我們基于上述例子繼續(xù)講，在經(jīng)過上述流程后，我們數(shù)組下標(biāo)為25的值是1。此時我們傳入一個值25，那么通過我們上述舉例的Hash算法計(jì)算后得到的數(shù)組下標(biāo)值也為25，那么此時布隆過濾器是不是就會認(rèn)為值25是存在的！但是實(shí)際上是因?yàn)?和25經(jīng)過Hash映射后得到同一個地址，導(dǎo)致了誤判！

當(dāng)然，這么簡單的問題偉大的“布隆先生”肯定不會犯如此“低級”的錯誤，因此解決方法就和我們上述定義中的關(guān)鍵字“一系列Hash函數(shù)”有關(guān)了。

我們通過“一系列的Hash函數(shù)”，比如Hash函數(shù)①y=x²&（len-1）②y=(2*x)&(len-1) ③y=(x+x²)&(len-1) 這三個Hash函數(shù)一起來決定某個元素是否存在我們的集合中。

也就是檢索流程變?yōu)椋簩ey值傳入一系列Hash函數(shù)得到對應(yīng)的一系列數(shù)組地址（索引下標(biāo)），注意這里一般來說有幾個Hash函數(shù)就會得到幾個地址，然后去判斷這幾個索引下標(biāo)對應(yīng)的值是否均為1，是的話則說明存在，否則不存在。

上述才是布隆過濾器檢索元素是否存在的真正流程，檢索元素流程圖因此對應(yīng)變化如下：

插入元素流程變?yōu)椋焊鶕?jù)一系列Hash函數(shù)得到一系列地址，將對應(yīng)地址下標(biāo)值改為1，流程圖如下：

當(dāng)然，我們從布隆過濾器定義中提到的缺點(diǎn)可以知道：布隆過濾器會有一定誤判率。說明即使是在一系列Hash函數(shù)下，依然會有巧合：“一個不存在的元素，對應(yīng)的一系列映射后的地址的值為1，即出現(xiàn)誤判”。這也是無法避免的事情，畢竟如果數(shù)據(jù)量很大的話，很難防止有一定量的、不存在的“幸運(yùn)兒”能通過布隆過濾器的篩選。

當(dāng)然，我們在使用布隆過濾器的時候能通過設(shè)置兩個參數(shù)：①預(yù)期數(shù)據(jù)量 ②誤判率期望值。我們可以通過設(shè)置“誤判率期望值”來達(dá)到我們能接受的誤判率。

當(dāng)然！大家別異想天開：“哎呀，那我設(shè)置0不就行了嗎？”這肯定是不可能的，而且設(shè)置的誤判率越低，數(shù)據(jù)量越大，占用內(nèi)存則越大，運(yùn)行時間則越慢！這也很好理解：數(shù)據(jù)量越大肯定占用越多內(nèi)存空間，誤判率越低則說明要越多的Hash函數(shù)來進(jìn)行運(yùn)算，則運(yùn)行時間越慢，一個key對應(yīng)的地址也多了，肯定占用越多內(nèi)存空間。

2.3 布隆過濾器元素的修改和刪除

我們從定義可以知道：我們想要修改或刪除一個元素時，同時去保證布隆過濾器不受影響是幾乎不可能的。

為什么這樣說呢，由于我們在插入元素時，不同的值可能經(jīng)過一系列Hash函數(shù)后得到的一系列地址，總有可能兩個或多個值經(jīng)過某個Hash函數(shù)映射后得到其中一個地址會一樣，此時數(shù)組中對應(yīng)的下標(biāo)肯定為1，當(dāng)我們刪除或修改某個元素后，我們?nèi)绻雽⑵湓瓉韺?yīng)地址的值從1改為0后，無法確定這個地址是否也對應(yīng)其他值，如果貿(mào)然修改，可能會導(dǎo)致其他原本存在的值在檢索時返回不存在的情況！這種情況是極其危險的，可能會導(dǎo)致數(shù)據(jù)的“邏輯丟失”。

因此我們這里不討論修改和刪除的情況。因?yàn)椴悸∵^濾器對元素的刪除不太支持，目前有一些變形的特定布隆過濾器支持元素的刪除。

3、布隆過濾器的使用場景

3.1 Redis通過布隆過濾器防止緩存穿透

首先我們需要知道什么是緩存穿透，這里我們給出緩存穿透的定義。

Redis緩存穿透指訪問一個緩存和數(shù)據(jù)庫中都不存在的key，由于這個key在緩存中不存在，則會到數(shù)據(jù)庫中查詢，數(shù)據(jù)庫中也不存在該key，無法將數(shù)據(jù)添加到緩存中，所以每次都會訪問數(shù)據(jù)庫導(dǎo)致數(shù)據(jù)庫壓力增大。

 我們可以在訪問Redis之前使用布隆過濾器來對請求的key進(jìn)行過濾， 可以大大減少那些惡意攻擊。當(dāng)然，會存在一定誤判率，但是使用布隆過濾器后，“不法分子”肯定對我們服務(wù)器就沒那么容易進(jìn)行惡意攻擊了。

3.2 RocketMQ通過布隆過濾器防止消息重復(fù)消費(fèi)

為了防止RocketMQ消息重復(fù)消費(fèi)，我們發(fā)送消息時可以對每個消息設(shè)置唯一的key，然后在消費(fèi)者處利用布隆過濾器對消息的key檢索，如果存在則說明消息已經(jīng)消費(fèi)過，不消費(fèi)。不存在則進(jìn)行消費(fèi)，然后插入布隆過濾器。

當(dāng)然，上面兩個例子僅僅是舉的例子，布隆過濾器能使用的地方很多，只要但凡涉及“數(shù)據(jù)過濾”均可以考慮使用“布隆過濾器”來實(shí)現(xiàn)。

4、布隆過濾器優(yōu)缺點(diǎn)

4.1 優(yōu)點(diǎn)：

• 時間復(fù)雜度低，增加和查詢元素的時間復(fù)雜為O(N)，（N為哈希函數(shù)的個數(shù)，通常情況比較小）
• 保密性強(qiáng)，布隆過濾器不存儲元素本身
• 存儲空間小，如果允許存在一定的誤判，布隆過濾器是非常節(jié)省空間的（相比其他數(shù)據(jù)結(jié)構(gòu)如Set、Map集合）

4.2 缺點(diǎn)：

• 有點(diǎn)一定的誤判率，但是可以通過調(diào)整參數(shù)來降低
• 無法獲取元素本身
• 很難刪除元素

以上就是詳解Java中布隆過濾器(Bloom Filter)原理及其使用場景的詳細(xì)內(nèi)容，更多關(guān)于Java布隆過濾器的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論