1埠褪、什么是布隆過濾器
可以把布隆過濾器理解為一個不怎么精確的set結(jié)構(gòu)凉逛，當(dāng)你使用它的contains方法判斷某個對象是否存在時，它可能會誤判捆姜。但是布隆過濾器也不是特別不精確妆够，只要參數(shù)設(shè)置得合理识啦，它的精確度也可以控制得相對足夠精確负蚊，只會有小小的誤判概率。
當(dāng)布隆過濾器說某個值存在時颓哮，這個值可能不存在家妆；當(dāng)它說某個值不存在時，那就肯定不存在冕茅。打個比方伤极，當(dāng)它說不認(rèn)識你時，肯定就是真的不認(rèn)識嵌赠；而當(dāng)他說認(rèn)識你時塑荒，卻有可能根本沒有見過你，只是因為你的臉跟它認(rèn)識的某人的臉比較相似姜挺，所以誤判以前認(rèn)識你齿税。
2、布隆過濾器的基本用法
redis官方提供的布隆過濾器到了redis 4.0提供了插件功能之后才正式登場炊豪。布隆過濾器作為一個插件加載到redis server中凌箕，給redis提供了強(qiáng)大的布隆去重功能。
布隆過濾器有兩個基本指令词渤，bf.add和bf.exists牵舱。bf.add添加元素，bf.exists查詢元素是否存在缺虐，它們的用法和set集合的sadd和sismember差不多芜壁。注意bf.add只能一次添加一個元素，如果想要一次添加多個高氮，就需要用到bf.madd指令慧妄。同樣如果需要一次查詢多個元素是否存在，就需要用到bf.mexists指令剪芍。
我們上面使用的布隆過濾器只是默認(rèn)參數(shù)的布隆過濾器塞淹，它在我們第一次add的時候自動創(chuàng)建。Redis其實還提供了自定義參數(shù)的布隆過濾器罪裹，需要我們在add之前使用bf.reserve指令顯示創(chuàng)建饱普。如果對于的key已經(jīng)存在，bf.reserve會報錯状共。bf.reserve有三個參數(shù)套耕，分別是key、error_rate（錯誤率）和initial_size口芍。error_rate越低箍铲，需要的空間越大。initial_size表示預(yù)計放入的元素數(shù)量鬓椭，當(dāng)實際數(shù)量超過這個數(shù)值時颠猴，誤判率會上升，所以需要提前設(shè)置一個較大的數(shù)值避免超出導(dǎo)致誤判率升高小染。如果不使用bf.reserve翘瓮，默認(rèn)的error_rate是0.01，默認(rèn)的initial_size是100裤翩。
3资盅、布隆過濾器的原理
學(xué)會了布隆過濾器的使用，下面有必須要把它的原理解釋一下踊赠，不然有些讀者還會繼續(xù)蒙在鼓里呵扛。
每個布隆過濾器對應(yīng)到redis的數(shù)據(jù)結(jié)構(gòu)里面就是一個大型的位數(shù)組和幾個不一樣的無偏hash函數(shù)。如下圖的f筐带、g今穿、h就是這樣的hash函數(shù)。所謂無偏就是能夠把元素的hash值算得比較均勻伦籍，讓元素被hash映射到位數(shù)組中的位置比較隨機(jī)蓝晒。
向布隆過濾器中添加key時，會使用多個hash函數(shù)對key進(jìn)行hash帖鸦，算得一個整數(shù)索引值芝薇，然后對位數(shù)組漲肚進(jìn)行取模運算得到一個位置，每個hash函數(shù)都會算得一個不同的位置作儿。在把位數(shù)組的這幾個位置都置為1洛二，就完成了add操作。
向布隆過濾器詢問key是否存在時攻锰，跟add一樣晾嘶，也會把hash的幾個位置都算出來，看看位數(shù)組中這幾個位置是否都為1口注，只要有一個位為0变擒，那么說明布隆過濾器中這個key不存在。如果這幾個位置都是1寝志，并不能說明這個key就一定存在娇斑，只是極有可能存在，因為這些位被置為1可能是因為其他的key存在所致材部。如果這個位數(shù)組比較稀疏毫缆，判斷正確的概率就會很大，如果這個位數(shù)組比較擁擠乐导，判斷正確的概率就會降低苦丁。具體的概率計算公式比較復(fù)雜，感興趣可以閱讀相關(guān)的更深入研究的資料物臂，不過非常燒腦旺拉，不建議讀者細(xì)讀产上。
使用時不要讓實際元素數(shù)量遠(yuǎn)大于初始化數(shù)量，當(dāng)實際元素數(shù)量開始超出初始化數(shù)量時蛾狗，應(yīng)該對布隆過濾器進(jìn)行重建晋涣，重新分配一個size更大的過濾器，在將所有的歷史元素批量add進(jìn)去沉桌。因為error_rate不會因為數(shù)量剛一超出就急劇增加谢鹊，這就給我們重建過濾器提供了較為寬松的時間。
