圖解布隆過濾器和布穀鳥過濾器實現原理

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

1、布隆過濾器

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

    我們元數據（龍蝦編程）通過兩個哈希函數函數之後得到 2 和 7 兩個值，然後將 2 和 7 這個兩個值對應的 bit 位上的值設置爲 1，這樣我們就將元數據存放到布隆過濾器上。

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

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

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

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

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

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

2、布穀鳥過濾器

    布隆過濾器不支持刪除元素，而布穀鳥過濾器支持刪除元素、支持動態添加元素並且效率比布隆過濾器效果更高。

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

   每個桶中有四個指紋位置，意味着一次哈希計算後布穀鳥有四個 “巢 “可用，而且四個巢是連續位置。桶中的元素不是我們的元數據，而是通過哈希函數生成 bit 位，這個 bit 位我們稱之爲指紋。

2.1 布穀鳥過濾器的桶位置計算函數

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

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

2.2 布穀鳥過濾器添加元素

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

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

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

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

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

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

    此時被踢掉的元素會去尋找它的另一個桶（因爲每個元數據有兩個桶），那麼尋找桶的過程就是通過異或的哈希函數實現的，如下所示：

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

    隨着插入的元素增多，布穀鳥過濾器的插入複雜度也就逐漸上升，因爲桶的數據越滿，那麼它的踢出數據的頻率就越高，所以需要重新計算的次數也會變多。

2.3 布穀鳥過濾器查詢元素

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

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

2.4 布穀鳥過濾器的元素分佈

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

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

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

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

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

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

總結：

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

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

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

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/y-KbXXmoUTSM2Fg2fOibdw