場(chǎng)景

在項(xiàng)目開(kāi)發(fā)中，我們經(jīng)常會(huì)遇到去重問(wèn)題。比如：判斷一個(gè)人有沒(méi)有瀏覽過(guò)一篇文章，判斷一個(gè)人當(dāng)天是否登錄過(guò)某個(gè)系統(tǒng)，判斷一個(gè)ip是否發(fā)過(guò)一個(gè)請(qǐng)求，等等。

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

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

原理

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

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

hash(“xy”) = 3;

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

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

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

hash(“xy”) = 3;

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

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

那怎么解決這個(gè)問(wèn)題呢？答案是使用多個(gè)不同的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;

最開(kāi)始，集合里沒(méi)有元素，所有位都是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

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

誤差

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

所以布隆過(guò)濾器不能刪除，因?yàn)橐坏﹦h除（即將相應(yīng)的位置為0），就很大可能會(huì)影響其他元素。

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

由此可見(jiàn)，布隆過(guò)濾器適合于一些需要去重，但不一定要完全精確的場(chǎng)景。比如：

判斷一個(gè)用戶(hù)訪問(wèn)了一篇文章
判斷一個(gè)ip訪問(wèn)了本網(wǎng)站
判斷一個(gè)key是否被訪問(wèn)過(guò)

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

判斷一個(gè)用戶(hù)是否收藏了一篇文章
判斷一個(gè)用戶(hù)是否訂購(gòu)了一個(gè)課程

使用技巧

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

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

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

redis中的布隆過(guò)濾器

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

Redis的布隆過(guò)濾器主要有兩個(gè)命令：

bf.add 添加元素到布隆過(guò)濾器中：bf.add strs xy
bf.exists 判斷某個(gè)元素是否在過(guò)濾器中：bf.exists strs xy

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

bf.reserve strs 0.01 100
復(fù)制代碼

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

第一個(gè)值是過(guò)濾器的名字。
第二個(gè)值為error_rate的值：允許布隆過(guò)濾器的錯(cuò)誤率。
第三個(gè)值為initial_size的值：初始化位數(shù)組的大小。

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

JAVA實(shí)現(xiàn)的布隆過(guò)濾器

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

布谷鳥(niǎo)過(guò)濾器

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

筆者個(gè)人覺(jué)得，對(duì)于大多數(shù)場(chǎng)景來(lái)說(shuō)，布隆過(guò)濾器足以解決我們的問(wèn)題。掘金上有一篇深度分析布谷鳥(niǎo)過(guò)濾器的文章，有興趣的讀者可以去了解一下：juejin.im/post/5cfb9c…