布隆過濾器和布谷鳥過濾器是兩種概率型數(shù)據(jù)結(jié)構(gòu)，主要用于高效的檢査一個(gè)元素是否屬于一個(gè)集合，但是在實(shí)現(xiàn)實(shí)現(xiàn)、性能特性和使用場景上存在一定的差異，下面我們來聊聊這兩種過濾器。

1、布隆過濾器

    布隆過濾器的原理是對(duì)一個(gè)key進(jìn)行n個(gè)hash算法獲取n個(gè)值，然后通過這些值在比特?cái)?shù)組中將這n個(gè)值對(duì)應(yīng)的bit位設(shè)為1，如下圖所示的：

圖片

    我們?cè)獢?shù)據(jù)通過兩個(gè)哈希函數(shù)函數(shù)之后得到2和7兩個(gè)值，然后將2和7這個(gè)兩個(gè)值對(duì)應(yīng)的bit位上的值設(shè)置為1，這樣我們就將元數(shù)據(jù)存放到布隆過濾器上。

    查詢?cè)獢?shù)據(jù)是否在布隆過濾器上的時(shí)候，我們一樣對(duì)元數(shù)據(jù)進(jìn)行兩次哈希得到對(duì)應(yīng)的哈希值，然后通過哈希值在布隆過濾器上尋找對(duì)應(yīng)的bit位上的值是否都是1，可能有如下的情況：

（1）如果bit位上不都是1，說明當(dāng)前元數(shù)據(jù)不在布隆過濾器上，如下所示：

圖片

   （2）如果bit位上都是1，如下所示：

圖片

    那么此時(shí)只能說明當(dāng)前元數(shù)據(jù)可能在布隆過濾器上，因?yàn)椴悸∵^濾器存在一定的誤判，下面解釋為什么bit位上全是1但是元數(shù)據(jù)不一定在布隆過濾器上，如下圖所示：

圖片

    元數(shù)據(jù)“龍蝦”和元數(shù)據(jù)“編程”通過哈希函數(shù)添加到布隆過濾器上，但是元數(shù)據(jù)“龍蝦編程”沒有添加到布隆過濾器上。當(dāng)我們通過哈希函數(shù)計(jì)算元數(shù)據(jù)“龍蝦編程”的哈希值后，尋找對(duì)應(yīng)bit位上的發(fā)現(xiàn)其值都是1，這就出現(xiàn)了誤判的情況。為了減少布隆過濾器的誤判率我們可以增加哈希函數(shù)的個(gè)數(shù)（如原來兩個(gè)哈希函數(shù)，現(xiàn)在我們?cè)黾拥?個(gè)哈希函數(shù)）。

    布隆過濾器存在一定的弊端，如不支持刪除元素，一旦對(duì)位數(shù)組進(jìn)行了賦值后無法將其刪除，并且其空間利用率也是較低的。

2、布谷鳥過濾器

    布隆過濾器不支持刪除元素，而布谷鳥過濾器支持刪除元素、支持動(dòng)態(tài)添加元素并且效率比布隆過濾器效果更高。

    布谷鳥過濾器底層是桶數(shù)組構(gòu)成的，而且桶中可以通過參數(shù)來設(shè)置每個(gè)桶存儲(chǔ)多少個(gè)元素，如下如所示的布谷鳥過濾器：

   每個(gè)桶中有四個(gè)指紋位置，意味著一次哈希計(jì)算后布谷鳥有四個(gè)“巢“可用，而且四個(gè)巢是連續(xù)位置。桶中的元素不是我們的元數(shù)據(jù)，而是通過哈希函數(shù)生成bit位，這個(gè)bit位我們稱之為指紋。

2.1 布谷鳥過濾器的桶位置計(jì)算函數(shù)

    布谷鳥過濾器的插入是通過兩個(gè)不獨(dú)立的哈希函數(shù)計(jì)算出當(dāng)前元素需要存儲(chǔ)到哪兩個(gè)桶中，函數(shù)如下所示：

圖片

    h1是直接通過hash函數(shù)得到一個(gè)下標(biāo)，這就是第一個(gè)桶的位置；h2通過h1下標(biāo)與前面的指紋值的哈希結(jié)果進(jìn)行異或，這樣就得到第二桶的位置。h1和h2是通過異或的關(guān)系得到，這樣也是布谷鳥過濾器設(shè)計(jì)的精妙之處，我們通過一個(gè)桶的位置就可以計(jì)算出另一個(gè)桶的位置。

2.2 布谷鳥過濾器添加元素

    第一步通過指紋哈希函數(shù)得到對(duì)應(yīng)的指紋（如指紋值為5），隨后通過哈希元數(shù)據(jù)得到第一個(gè)桶的位置（如桶1的位置是2），然后拿第一個(gè)桶的位置與指紋的哈希值異或得到第二個(gè)桶的位置（如桶2的位置是4）。

    假設(shè)每個(gè)桶中可以存放兩個(gè)元素，通過計(jì)算得到桶的位置之后就需要判斷兩個(gè)桶中是否還有位置存放當(dāng)前元素的指紋值，可能的情況如下所示：

（1）如果兩個(gè)桶中都有位置存放指紋值，那么會(huì)隨機(jī)挑選一個(gè)桶來存放指紋值，如下所示：

圖片

（2）一個(gè)桶中已經(jīng)存滿了，另一個(gè)桶還有位置，此時(shí)會(huì)選擇另外的桶存放指紋，如下所示：

圖片

（3）兩個(gè)桶都存滿了指紋值

    如果兩個(gè)桶都存滿了指紋值，這個(gè)時(shí)候布谷鳥過濾器就會(huì)隨機(jī)挑選一個(gè)桶并將桶中的隨機(jī)的一個(gè)指紋值踢掉，把當(dāng)前的指紋值存放進(jìn)去，如下所示：

圖片

    此時(shí)被踢掉的元素會(huì)去尋找它的另一個(gè)桶（因?yàn)槊總€(gè)元數(shù)據(jù)有兩個(gè)桶），那么尋找桶的過程就是通過異或的哈希函數(shù)實(shí)現(xiàn)的，如下所示：

圖片

    極端的情況下，指紋3存在的另一個(gè)桶中也滿了，此時(shí)就會(huì)在桶中隨機(jī)剔除一個(gè)指紋（假設(shè)為指紋x），指紋x也就重復(fù)指紋值3的過程，這樣就會(huì)一直遞歸直到找到桶將所有的指紋存放下去。當(dāng)然我們也是可以設(shè)置遞歸的次數(shù)，不會(huì)讓其無限制的遞歸下去。

    隨著插入的元素增多，布谷鳥過濾器的插入復(fù)雜度也就逐漸上升，因?yàn)橥暗臄?shù)據(jù)越滿，那么它的踢出數(shù)據(jù)的頻率就越高，所以需要重新計(jì)算的次數(shù)也會(huì)變多。

2.3 布谷鳥過濾器查詢?cè)?/h4>

    由于每個(gè)元素都是通過兩個(gè)并不獨(dú)立的哈希函數(shù)計(jì)算之后只會(huì)存在特定的桶中，所以查找的時(shí)候只會(huì)在特定的桶位置拿到桶中所有的指紋值，然后將桶中的指紋值與當(dāng)前的元數(shù)據(jù)指紋值做對(duì)比，如下所示：

圖片

    我們此時(shí)只需要判斷是否有元數(shù)據(jù)的指紋值，如果比對(duì)成功那么就證明元數(shù)據(jù)存在布谷鳥過濾器中（存在也不一定是真存在），反之就就不在布谷鳥過濾器中。

2.4 布谷鳥過濾器的元素分布

    布谷鳥過濾器在插入的時(shí)候并不會(huì)先去判斷這個(gè)桶中是否存在相同的指紋，而是直接插入元數(shù)據(jù)的指紋，這也就代表同一個(gè)桶中存在多個(gè)相同的指紋，如下圖所示：

圖片

也可能出現(xiàn)在布谷鳥過濾器中多個(gè)桶中存在同樣的指紋，如下圖所示：

圖片

    這樣就出現(xiàn)了同樣的指紋出現(xiàn)在不同的桶中這也就給查詢帶來一定的假陽性。

2.5 布谷鳥過濾器的刪除元素

    因?yàn)槲覀兇娣诺氖窃獢?shù)據(jù)的指紋，因此我們通過查詢邏輯找到對(duì)應(yīng)桶中的所有指紋，然后找到元數(shù)據(jù)的指紋，直接刪除這個(gè)指紋，如下所示：

    但是我們這里需要注意的是，同一個(gè)桶中可能會(huì)存在多個(gè)指紋的相同的副本，此時(shí)也就被刪除了。

總結(jié)：

    布隆過濾器和布谷鳥過濾器都有各自的特點(diǎn)，所以也就有各自的使用場景。

（1）如果需要一個(gè)成熟、簡單且不需要?jiǎng)h除元素的概率型數(shù)據(jù)結(jié)構(gòu)，布隆過濾器是一個(gè)很好的選擇。

（2）如果需要支持刪除操作并且對(duì)誤報(bào)率有更嚴(yán)格的要求，布谷鳥過濾器可能是更好的選擇。在選擇數(shù)據(jù)結(jié)構(gòu)時(shí)，需要考慮實(shí)際應(yīng)用的需求和性能要求。