1、什么是布隆過濾器

以下定義來自百度百科：

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

從上述定義我們可以得到以下關鍵信息：

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

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

2、布隆過濾器的原理

2.1 布隆過濾器的數(shù)據結構

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

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

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

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

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

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

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

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

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

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

檢索流程圖如下：

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

①存在Hash沖突導致誤判：

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

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

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

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

我們通過“一系列的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ù)得到對應的一系列數(shù)組地址（索引下標），注意這里一般來說有幾個Hash函數(shù)就會得到幾個地址，然后去判斷這幾個索引下標對應的值是否均為1，是的話則說明存在，否則不存在。

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

插入元素流程變?yōu)椋焊鶕幌盗蠬ash函數(shù)得到一系列地址，將對應地址下標值改為1，流程圖如下：

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

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

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

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

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

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

因此我們這里不討論修改和刪除的情況。因為布隆過濾器對元素的刪除不太支持，目前有一些變形的特定布隆過濾器支持元素的刪除。

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

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

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

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

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

3.2 RocketMQ通過布隆過濾器防止消息重復消費

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

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

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

4.1 優(yōu)點：

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

4.2 缺點：

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

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

最新評論