正文

場景

在項目開發(fā)中，我們經(jīng)常會遇到去重問題。比如：判斷一個人有沒有瀏覽過一篇文章，判斷一個人當(dāng)天是否登錄過某個系統(tǒng)，判斷一個ip是否發(fā)過一個請求，等等。

比較容易想到的是使用set來實(shí)現(xiàn)這個功能。但如果數(shù)據(jù)量較大，使用set會非常消耗內(nèi)存，性能也不高。在前面的文章中，我們介紹了一種數(shù)據(jù)結(jié)構(gòu)：BitMap來提高性能。但BitMap仍然比較消耗內(nèi)存，尤其是在數(shù)據(jù)比較稀疏的情況下，使用BitMap并不劃算。

實(shí)際上，對于“去重”問題，業(yè)界有另外一個更優(yōu)秀的數(shù)據(jù)結(jié)構(gòu)來解決這類問題，那就是——布隆過濾器(BloomFilter)。

原理

布隆過濾器與BitMap類似，底層也是一個位數(shù)組。1表示有，0表示無。但布隆過濾器比BitMap需要更少的內(nèi)存，它是怎么辦到的呢？答案是多個hash。

我們知道hash算法，是把一個數(shù)從較大范圍的值，映射到較小范圍值。比如我們有一個10位的數(shù)組，使用某個hash算法及其數(shù)組上的表示：

hash(“xy”) = 3;

hash(“技術(shù)圈”) = 5;

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

這樣，我們使用這個hash算法就能快速的判斷一個字符串是不是存在一個集合里面了。但眾所周知，hash算法是有可能發(fā)生hash沖突的。比如可能有兩個不同的字符串映射到同一個數(shù)：

hash(“xy”) = 3;

hash(“xy的技術(shù)圈”) = 3;

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

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

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

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

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

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

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

然后，插入“xy”，利用多次hash，把每次hash的結(jié)果下標(biāo)3, 5, 7都插入到相應(yīng)的地方：

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

然后，插入“技術(shù)圈”，利用多次hash，把每次hash的結(jié)果下標(biāo)5, 6, 7都插入到相應(yīng)的地方，已經(jīng)是1的下標(biāo)不變：

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

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

誤差

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

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

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

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

• 判斷一個用戶訪問了一篇文章

• 判斷一個ip訪問了本網(wǎng)站

• 判斷一個key是否被訪問過

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

• 判斷一個用戶是否收藏了一篇文章

• 判斷一個用戶是否訂購了一個課程

使用技巧

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

這里有一個測試數(shù)據(jù)：

后面4列中的數(shù)據(jù)就是發(fā)生誤差的數(shù)量。可見，空間大小和集合大小不變的情況下，增加hash函數(shù)可以顯著減小誤差。但一旦集合大小達(dá)到空間大小的25%左右后，增加hash函數(shù)帶來的提神效果并不明顯。這個時候應(yīng)該增加空間大小。

Redis中的布隆過濾器

Redis的布隆過濾器不是原生自帶的，而是要通過module加載進(jìn)去。Redis在4.0的版本中加入了module功能。具體使用可以直接看RedisBloom?github的README：https://github.com/RedisBloom/RedisBloom。上面有docker一鍵啟動命令，可以很方便地實(shí)驗。也有幾種主流語言的客戶端庫的鏈接，比如Java語言的JReBloom。有興趣的朋友可以自行了解。

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

• bf.add?添加元素到布隆過濾器中：bf.add strs xy

• bf.exists?判斷某個元素是否在過濾器中：bf.exists strs xy

Redis中有一個命令可以來設(shè)置布隆過濾器的準(zhǔn)確率：

bf.reserve strs 0.01 100

三個參數(shù)的含義：

• 第一個值是過濾器的名字。

• 第二個值為error_rate的值：允許布隆過濾器的錯誤率。

• 第三個值為initial_size的值：初始化位數(shù)組的大小。

擴(kuò)展學(xué)習(xí)

Java實(shí)現(xiàn)的布隆過濾器

如果你的項目沒有使用Redis，那可以使用一些開源庫，基于代碼實(shí)現(xiàn)，直接存放在內(nèi)存。比如Google的guava包中提供了BloomFilter類，有興趣的讀者可以去了解一下，研究研究源碼和使用。

布谷鳥過濾器

RedisBloom模塊還實(shí)現(xiàn)了布谷鳥過濾器，它算是對布隆過濾器的增強(qiáng)版。解決了布隆過濾器的一些比較明顯的缺點(diǎn)，比如：不能刪除元素，不能計數(shù)等。除此之外，布谷鳥過濾器不用使用多個hash函數(shù)，所以查詢性能更高。除此之外，在相同的誤判率下，布谷鳥過濾器的空間利用率要明顯高于布隆，空間上大概能節(jié)省40%多。

筆者個人覺得，對于大多數(shù)場景來說，布隆過濾器足以解決我們的問題。

掘金上有一篇深度分析布谷鳥過濾器的文章，有興趣的讀者可以去了解一下：https://juejin.im/post/5cfb9c74e51d455d6d5357db。

總結(jié)

以上是生活随笔為你收集整理的Redis布隆过滤器的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。