1、什么是布隆過濾器

可以把布隆過濾器理解為一個不怎么精確的set結構，當你使用它的contains方法判斷某個對象是否存在時，它可能會誤判。但是布隆過濾器也不是特別不精確，只要參數(shù)設置得合理，它的精確度也可以控制得相對足夠精確，只會有小小的誤判概率。

當布隆過濾器說某個值存在時，這個值可能不存在；當它說某個值不存在時，那就肯定不存在。打個比方，當它說不認識你時，肯定就是真的不認識；而當他說認識你時，卻有可能根本沒有見過你，只是因為你的臉跟它認識的某人的臉比較相似，所以誤判以前認識你。

2、布隆過濾器的基本用法

redis官方提供的布隆過濾器到了redis 4.0提供了插件功能之后才正式登場。布隆過濾器作為一個插件加載到redis server中，給redis提供了強大的布隆去重功能。

布隆過濾器有兩個基本指令，bf.add和bf.exists。bf.add添加元素，bf.exists查詢元素是否存在，它們的用法和set集合的sadd和sismember差不多。注意bf.add只能一次添加一個元素，如果想要一次添加多個，就需要用到bf.madd指令。同樣如果需要一次查詢多個元素是否存在，就需要用到bf.mexists指令。

我們上面使用的布隆過濾器只是默認參數(shù)的布隆過濾器，它在我們第一次add的時候自動創(chuàng)建。Redis其實還提供了自定義參數(shù)的布隆過濾器，需要我們在add之前使用bf.reserve指令顯示創(chuàng)建。如果對于的key已經存在，bf.reserve會報錯。bf.reserve有三個參數(shù)，分別是key、error_rate（錯誤率）和initial_size。error_rate越低，需要的空間越大。initial_size表示預計放入的元素數(shù)量，當實際數(shù)量超過這個數(shù)值時，誤判率會上升，所以需要提前設置一個較大的數(shù)值避免超出導致誤判率升高。如果不使用bf.reserve，默認的error_rate是0.01，默認的initial_size是100。

3、布隆過濾器的原理

學會了布隆過濾器的使用，下面有必須要把它的原理解釋一下，不然有些讀者還會繼續(xù)蒙在鼓里。

每個布隆過濾器對應到redis的數(shù)據(jù)結構里面就是一個大型的位數(shù)組和幾個不一樣的無偏hash函數(shù)。如下圖的f、g、h就是這樣的hash函數(shù)。所謂無偏就是能夠把元素的hash值算得比較均勻，讓元素被hash映射到位數(shù)組中的位置比較隨機。

向布隆過濾器中添加key時，會使用多個hash函數(shù)對key進行hash，算得一個整數(shù)索引值，然后對位數(shù)組漲肚進行取模運算得到一個位置，每個hash函數(shù)都會算得一個不同的位置。在把位數(shù)組的這幾個位置都置為1，就完成了add操作。

向布隆過濾器詢問key是否存在時，跟add一樣，也會把hash的幾個位置都算出來，看看位數(shù)組中這幾個位置是否都為1，只要有一個位為0，那么說明布隆過濾器中這個key不存在。如果這幾個位置都是1，并不能說明這個key就一定存在，只是極有可能存在，因為這些位被置為1可能是因為其他的key存在所致。如果這個位數(shù)組比較稀疏，判斷正確的概率就會很大，如果這個位數(shù)組比較擁擠，判斷正確的概率就會降低。具體的概率計算公式比較復雜，感興趣可以閱讀相關的更深入研究的資料，不過非常燒腦，不建議讀者細讀。

使用時不要讓實際元素數(shù)量遠大于初始化數(shù)量，當實際元素數(shù)量開始超出初始化數(shù)量時，應該對布隆過濾器進行重建，重新分配一個size更大的過濾器，在將所有的歷史元素批量add進去。因為error_rate不會因為數(shù)量剛一超出就急劇增加，這就給我們重建過濾器提供了較為寬松的時間。