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

1、布隆過濾器

    布隆過濾器的原理是對一個key進行n個hash算法獲取n個值，然后通過這些值在比特數(shù)組中將這n個值對應的bit位設為1，如下圖所示的：

圖片

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

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

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

圖片

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

圖片

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

圖片

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

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

2、布谷鳥過濾器

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

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

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

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

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

圖片

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

2.2 布谷鳥過濾器添加元素

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

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

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

圖片

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

圖片

（3）兩個桶都存滿了指紋值

    如果兩個桶都存滿了指紋值，這個時候布谷鳥過濾器就會隨機挑選一個桶并將桶中的隨機的一個指紋值踢掉，把當前的指紋值存放進去，如下所示：

圖片

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

圖片

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

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

2.3 布谷鳥過濾器查詢元素

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

圖片

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

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

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

圖片

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

圖片

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

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

    因為我們存放的是元數(shù)據(jù)的指紋，因此我們通過查詢邏輯找到對應桶中的所有指紋，然后找到元數(shù)據(jù)的指紋，直接刪除這個指紋，如下所示：

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

總結：

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

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

（2）如果需要支持刪除操作并且對誤報率有更嚴格的要求，布谷鳥過濾器可能是更好的選擇。在選擇數(shù)據(jù)結構時，需要考慮實際應用的需求和性能要求。