引言

我們知道檢查一個元素是否在某一個集合中，使用HashSet是比較好的選擇，因為在不發(fā)生Hash碰撞的情況下它的時間復(fù)雜度為常數(shù)級別，但是在數(shù)據(jù)量比較大的情況下，使用HashSet將會占用大量的內(nèi)存空間。舉個例子，長城防火墻有100億個需要屏蔽的網(wǎng)址，來自計算機的每一次請求都要經(jīng)過防火墻的過濾判斷請求URL是否在黑名單中，如果我們使用HashSet來實現(xiàn)過濾的話，我們假設(shè)每個URL的大小為64B，那么100億個就至少需要大約640GB的內(nèi)存空間，這顯然是不符合實際情況的。另一種解決方案是我們可以將URL存入關(guān)系型數(shù)據(jù)庫，每次計算機發(fā)起請求我們對數(shù)據(jù)庫進行exits查詢，然而這種方案適用于并發(fā)量比較小的情況，若并發(fā)量較大，那么我們就需要對數(shù)據(jù)庫進行集群。

以上倆種方案都有一定的局限性，為了解決大數(shù)據(jù)量檢查問題，布隆過濾器就粉墨登場了。

原理

先來簡單了解一下布隆過濾器，我們可以把它看做一個會產(chǎn)生誤判并且占用空間極少的HashSet。它的結(jié)構(gòu)是一個Bit數(shù)組（數(shù)組中每個位置只占用一個bit，每個bit位有0和1兩種狀態(tài)）和一系列Hash函數(shù)的集合，我們將輸入域通過上述一系列Hash函數(shù)進行Hash運算得到n個key值，將這n個值對數(shù)組的長度進行取余，然后將bit數(shù)組中對應(yīng)的位置bit位設(shè)為1。在數(shù)組足夠大，hash碰撞足夠小的情況下，每個輸入域都會在數(shù)組中不同的位置將其bit位置為1，我們把集合中所有的元素都按照這個方式來一遍的話一個布隆過濾器就生成好了。

那么如何判斷一個元素是否在布隆過濾器中呢，原理和生成布隆過濾器的過程差不多，我們將要判斷的值通過布隆過濾器的n個Hash函數(shù)計算出n個值，對數(shù)組長度取余得到bit數(shù)組中n個位置，接下來判斷這n個位置的bit位是否都為1，若都為1，則說明該元素在集合中，若有一個為0，則該元素肯定不在集合中。

誤判

了解了布隆過濾器的生成過程，相信大家已經(jīng)看出來了，這樣會產(chǎn)生一定的誤判，假如輸入對象不再集合中，而由于元素過多并且bit數(shù)組過小導(dǎo)致數(shù)組中的大部分位置bit位都為1，那么有可能會誤判該元素在集合中。但是如果輸入對象本就在集合中，那么數(shù)組中的bit位肯定都為1，布隆過濾器是一定不會產(chǎn)生誤判的，這就是所謂的“寧可錯殺三千，絕不放過一個”。

對于已經(jīng)發(fā)現(xiàn)的誤判元素，我們可以把他放入HashSet中，在經(jīng)過布隆過濾器之前先行判斷一下，這部分元素較少不會占用多少內(nèi)存，也在一定程度解決了布隆過濾器的誤判問題。

空間占用估計

計算布隆過濾器的空間占用有一個現(xiàn)成的公式，,其中n為元素的個數(shù)，p為允許的誤差率大小。布隆過濾器中Hash函數(shù)個數(shù)的公式為,m為個公式的結(jié)果，n為元素的個數(shù)。

如果覺得公式計算起來太麻煩，也沒有關(guān)系，已經(jīng)有先人幫我們做好工作了，我們只要把參數(shù)輸進去，就可以直接看到結(jié)果，比如這個網(wǎng)站--?計算。

上面的例子通過公式計算，假如誤判率為0.01%，如果使用布隆過濾器的話我們的內(nèi)存占用空間將會比使用HashSet少占用大約99.5%，但是得到的效果卻基本相同。

在Redis中的應(yīng)用

經(jīng)過上面的介紹，已經(jīng)對布隆過濾器有了大致的了解了，接下來就是他的使用了。Redis的布隆過濾器作為一個插件，在Redis在4.0中的提供了插件功能后才可以使用。使用前需要先安裝插件。

這里主要介紹一下他的幾個命令。

bf.add: 添加元素；

bf.exists: 查詢元素是否存在

bf.madd: 添加多個

bf.mexists: 查詢多個元素是否存在

開發(fā)中我們可以使用官方提供的Java客戶端JReBloom，也可以使用Lettuce（前面的文章有介紹）。

其他應(yīng)用（摘自Redis深度歷險）

在爬蟲系統(tǒng)中，我們需要對 URL 進行去重，已經(jīng)爬過的網(wǎng)頁就可以不用爬了。但是 URL 太多了，幾千萬幾個億，如果用一個集合裝下這些 URL 地址那是非常浪費空間的。這時候就可以考慮使用布隆過濾器。它可以大幅降低去重存儲消耗，只不過也會使得爬蟲系統(tǒng)錯過少量的頁面。

布隆過濾器在 NoSQL 數(shù)據(jù)庫領(lǐng)域使用非常廣泛，我們平時用到的 HBase、Cassandra 還有 LevelDB、RocksDB 內(nèi)部都有布隆過濾器結(jié)構(gòu)，布隆過濾器可以顯著降低數(shù)據(jù)庫的 IO 請求數(shù)量。當用戶來查詢某個 row 時，可以先通過內(nèi)存中的布隆過濾器過濾掉大量不存在的 row 請求，然后再去磁盤進行查詢。

郵箱系統(tǒng)的垃圾郵件過濾功能也普遍用到了布隆過濾器，因為用了這個過濾器，所以平時也會遇到某些正常的郵件被放進了垃圾郵件目錄中，這個就是誤判所致，概率很低。