1、什么是布隆過(guò)濾器

以下定義來(lái)自百度百科：

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

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

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

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

2、布隆過(guò)濾器的原理

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

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

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

2.2 布隆過(guò)濾器的檢索和插入原理

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

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

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

簡(jiǎn)單來(lái)說(shuō)Hash函數(shù)就是把輸入值通過(guò)特定方式（hash函數(shù)） 處理后 生成一個(gè)值，這個(gè)值等同于存放數(shù)據(jù)的地址。

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

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

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

檢索流程圖如下：

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

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

首先我們先對(duì)Hash沖突作一個(gè)簡(jiǎn)要說(shuō)明：

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

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

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

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

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

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

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

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

當(dāng)然，我們?cè)谑褂貌悸∵^(guò)濾器的時(shí)候能通過(guò)設(shè)置兩個(gè)參數(shù)：①預(yù)期數(shù)據(jù)量 ②誤判率期望值。我們可以通過(guò)設(shè)置“誤判率期望值”來(lái)達(dá)到我們能接受的誤判率。

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

2.3 布隆過(guò)濾器元素的修改和刪除

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

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

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

3、布隆過(guò)濾器的使用場(chǎng)景

3.1 Redis通過(guò)布隆過(guò)濾器防止緩存穿透

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

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

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

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

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

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

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

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

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

4.2 缺點(diǎn)：

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

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

最新評(píng)論