場景

在專案開發中，我們經常會遇到去重問題。比如：判斷一個人有沒有瀏覽過一篇文章，判斷一個人當天是否登入過某個系統，判斷一個ip是否發過一個請求，等等。

比較容易想到的是使用set來實現這個功能。但如果資料量較大，使用set會非常消耗記憶體，效能也不高。在前面的文章中，我們介紹了一種資料結構：BitMap來提高效能。但BitMap仍然比較消耗記憶體，尤其是在資料比較稀疏的情況下，使用BitMap並不划算。

實際上，對於“去重”問題，業界有另外一個更優秀的資料結構來解決這類問題，那就是——布隆過濾器(BloomFilter)。

布隆過濾器與BitMap類似，底層也是一個位陣列。1表示有，0表示無。但布隆過濾器比BitMap需要更少的記憶體，它是怎麼辦到的呢？答案是多個hash。

我們知道hash演算法，是把一個數從較大範圍的值，對映到較小範圍值。比如我們有一個10位的陣列，使用某個hash演算法及其陣列上的表示：

hash(“xy”) = 3;

hash(“技術圈”) = 5;

0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0

這樣，我們使用這個hash演算法就能快速的判斷一個字串是不是存在一個集合裡面了。但眾所周知，hash演算法是有可能發生hash衝突的。比如可能有兩個不同的字串對映到同一個數：

hash(“xy”) = 3;

這種情況下，就不能準確得判斷出某個字串是不是存在於集合之中呢。

那怎麼解決這個問題呢？答案是使用多個不同的hash演算法。比如：

h1(“xy”) = 3, h2(“xy”) = 5, h3(“xy”) = 7;

h1(“技術圈”) = 5, h2(“技術圈”) = 6, h3(“技術圈”) = 7;

最開始，集合裡沒有元素，所有位都是0：

0, 0, 0, 0, 0, 0, 0, 0, 0, 0

然後，插入“xy”，利用多次hash，把每次hash的結果下標3, 5, 7都插入到相應的地方：

0, 0, 0, 1, 0, 1, 0, 1, 0, 0

然後，插入“技術圈”，利用多次hash，把每次hash的結果下標5, 6, 7都插入到相應的地方，已經是1的下標不變：

0, 0, 0, 1, 0, 1, 1, 1, 0, 0

誤差

從原理可以看得出來，布隆過濾器是有可能存在一定的誤差的。尤其是當hash函式比較少的時候。布隆過濾器是根據多次hash計算下標後，陣列的這些下標是否都為1來判斷這個元素是否存在的。所以是存在一定的機率，要檢查的元素實際上沒有插入，但被其它元素插入影響，導致所有下標都為1。

如果使用布隆過濾器判斷一個函式是否存在於一個集合，如果它返回true，則代表可能存在。如果它返回false，則代表一定不存在。

由此可見，布隆過濾器適合於一些需要去重，但不一定要完全精確的場景。比如：

判斷一個使用者訪問了一篇文章判斷一個ip訪問了本網站判斷一個key是否被訪問過

相應的，布隆過濾器不適合一些要求零誤差的場景，比如：

判斷一個使用者是否收藏了一篇文章判斷一個使用者是否訂購了一個課程使用技巧

這就是布隆過濾器的基本原理。由上面的例子可以看出來，如果空間越大，hash函式越多，結果就越精確，但空間效率和查詢效率就會越低。

這裡有一個測試資料：

後面4列中的資料就是發生誤差的數量。可見，空間大小和集合大小不變的情況下，增加hash函式可以顯著減小誤差。但一旦集合大小達到空間大小的25%左右後，增加hash函式帶來的提神效果並不明顯。這個時候應該增加空間大小。

Redis中的布隆過濾器

Redis的布隆過濾器不是原生自帶的，而是要通過module載入進去。Redis在4.0的版本中加入了module功能。具體使用可以直接看RedisBloom github的README：github.com/RedisBloom/…

Redis的布隆過濾器主要有兩個命令：

bf.add 新增元素到布隆過濾器中：bf.add strs xybf.exists 判斷某個元素是否在過濾器中：bf.exists strs xy

Redis中有一個命令可以來設定布隆過濾器的準確率：

bf.reserve strs 0.01 100複製程式碼

三個引數的含義：

第一個值是過濾器的名字。第二個值為error_rate的值：允許布隆過濾器的錯誤率。第三個值為initial_size的值：初始化位陣列的大小。擴充套件學習

Java實現的布隆過濾器

如果你的專案沒有使用Redis，那可以使用一些開源庫，基於程式碼實現，直接存放在記憶體。比如Google的guava包中提供了BloomFilter類，有興趣的讀者可以去了解一下，研究研究原始碼和使用。

布穀鳥過濾器

RedisBloom模組還實現了布穀鳥過濾器，它算是對布隆過濾器的增強版。解決了布隆過濾器的一些比較明顯的缺點，比如：不能刪除元素，不能計數等。除此之外，布穀鳥過濾器不用使用多個hash函式，所以查詢效能更高。除此之外，在相同的誤判率下，布穀鳥過濾器的空間利用率要明顯高於布隆，空間上大概能節省40%多。

筆者個人覺得，對於大多數場景來說，布隆過濾器足以解決我們的問題。掘金上有一篇深度分析布穀鳥過濾器的文章，有興趣的讀者可以去了解一下：juejin.im/post/5cfb9c…

認真寫文章，用心做分享。

個人網站：yasinshaw.com