場景

在項目開發中，我們經常會遇到去重問題。比如：判斷一個人有沒有瀏覽過一篇文章，判斷一個人當天是否登錄過某個系統，判斷一個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(“xy的技術圈”) = 3;

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

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

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

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

h1(“xy的技術圈”) = 3, h2(“xy的技術圈”) = 6, h3(“xy的技術圈”) = 9;

最開始，集合里沒有元素，所有位都是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

這個時候，如果想要判斷“xy”是否在集合中，只需要使用同樣的3個hash算法，來計算出下標是3, 5, 7，發現這3個下標都為1，那么就認為“xy”這個字符串在集合中。而“xy的技術圈”計算出來的下標是3， 6， 9。發現這三個下標有不是1的地方，比如下標為9的地方是0，那就說明“xy的技術圈”這個字符串還不在集合中。

誤差

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

所以布隆過濾器不能刪除，因為一旦刪除（即將相應的位置為0），就很大可能會影響其他元素。

如果使用布隆過濾器判斷一個函數是否存在于一個集合，如果它返回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 xy
bf.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…