Bloom Filter是一個占用空間很小、效率很高的隨機數(shù)據(jù)結(jié)構(gòu)，它由一個bit數(shù)組和一組Hash算法構(gòu)成。可用于判斷一個元素是否在一個集合中，查詢效率很高（1-N，最優(yōu)能逼近于1）。

在很多場景下，我們都需要一個能迅速判斷一個元素是否在一個集合中。譬如：

網(wǎng)頁爬蟲對URL的去重，避免爬取相同的URL地址；

反垃圾郵件，從數(shù)十億個垃圾郵件列表中判斷某郵箱是否垃圾郵箱（同理，垃圾短信）；

緩存擊穿，將已存在的緩存放到布隆中，當(dāng)黑客訪問不存在的緩存時迅速返回避免緩存及DB掛掉。

可能有人會問，我們直接把這些數(shù)據(jù)都放到數(shù)據(jù)庫或者redis之類的緩存中不就行了，查詢時直接匹配不就OK了？

是的，當(dāng)這個集合量比較小，你內(nèi)存又夠大時，是可以這樣做，你可以直接弄個HashSet、HashMap就OK了。但是當(dāng)這個量以數(shù)十億計，內(nèi)存裝不下，數(shù)據(jù)庫檢索極慢時該怎么辦。

以垃圾郵箱為例

方案比較

1.將所有垃圾郵箱地址存到數(shù)據(jù)庫，匹配時遍歷 2.用HashSet存儲所有地址，匹配時接近O（1）的效率查出來 3.將地址用MD5算法或其他單向映射算法計算后存入HashSet，無論地址多大，保存的只有MD5后的固定位數(shù) 4.布隆過濾器，將所有地址經(jīng)過多個Hash算法，映射到一個bit數(shù)組

優(yōu)缺點

方案1和2都是保存完整的地址，占用空間大。一個地址16字節(jié)，10億即可達到上百G的內(nèi)存。HashSet效率逼近O(1)，數(shù)據(jù)庫就不談效率了，不在一個數(shù)量級。 方案3保存部分信息，占用空間小于存儲完整信息，存在沖突的可能（非垃圾郵箱可能MD5后和某垃圾郵箱一樣，概率低） 方案4將所有地址經(jīng)過Hash后映射到同一個bit數(shù)組，看清了，只有一個超大的bit數(shù)組，保存所有的映射，占用空間極小，沖突概率高。
大家知道，java中的HashMap有個擴容參數(shù)默認(rèn)是0.75，也就是你想存75個數(shù)，至少需要一個100的數(shù)組，而且還會有不少的沖突。實際上，Hash的存儲效率是0.5左右，存5個數(shù)需要10個的空間。算起來占用空間還是挺大的。 而布隆過濾器就不用為每個數(shù)都分配空間了，而是直接把所有的數(shù)通過算法映射到同一個數(shù)組，帶來的問題就是沖突上升，只要概率在可以接受的范圍，用時間換空間，在很多時候是好方案。布隆過濾器需要的空間僅為HashMap的1/8-1/4之間，而且它不會漏掉任何一個在黑名單的可疑對象，問題只是會誤傷一些非黑名單對象。

原理

初始化狀態(tài)是一個全為0的bit數(shù)組
為了表達存儲N個元素的集合，使用K個獨立的函數(shù)來進行哈希運算。x1，x2……xk為k個哈希算法。 如果集合元素有N1，N2……NN，N1經(jīng)過x1運算后得到的結(jié)果映射的位置標(biāo)1，經(jīng)過x2運算后結(jié)果映射也標(biāo)1，已經(jīng)為1的報錯1不變。經(jīng)過k次散列后，對N1的散列完成。 依次對N2，NN等所有數(shù)據(jù)進行散列，最終得到一個部分為1，部分位為0的字節(jié)數(shù)組。當(dāng)然了，這個字節(jié)數(shù)組會比較長，不然散列效果不好。 那么怎么判斷一個外來的元素是否已經(jīng)在集合里呢，譬如已經(jīng)散列了10億個垃圾郵箱，現(xiàn)在來了一個郵箱，怎么判斷它是否在這10億里面呢？ 很簡單，就拿這個新來的也依次經(jīng)歷x1，x2……xk個哈希算法即可。 在任何一個哈希算法譬如到x2時，得到的映射值有0，那就說明這個郵箱肯定不在這10億內(nèi)。 如果是一個黑名單對象，那么可以肯定的是所有映射都為1，肯定跑不了它。也就是說是壞人，一定會被抓。 那么誤傷是為什么呢，就是指一些非黑名單對象的值經(jīng)過k次哈希后，也全部為1，但它確實不是黑名單里的值，這種概率是存在的，但是是可控的。




上面的幾個圖看起來很高深，但那不是我們關(guān)心的問題，歸根到底意思其實就是你想讓錯誤率降低，就得增大數(shù)組的長度，就是這樣。 我們使用BloomFilter的目的就是想省空間，所以我們需要做的就是在錯誤率上做個權(quán)衡就OK。 很多時候這個錯誤率我們是能接受的，譬如垃圾郵箱問題，是壞人一定會被抓，這個能保證。無非是一些好人也被抓，這個可以通過給這些可伶的被誤傷的設(shè)置個白名單就OK。至于爬蟲Url重復(fù)這個就更沒問題了，會缺掉一些網(wǎng)頁而已。 至于在緩存穿透上的應(yīng)用，是為了避免惡意用戶頻繁請求緩存中不存在DB也不存在的值，會導(dǎo)致緩存失效、DB負(fù)載過大，可以使用BloomFilter把所有數(shù)據(jù)放到bit數(shù)組中，當(dāng)用戶請求時存在的值肯定能放行，部分不存在的值也會被放行，絕大部分會被攔截，這些少量漏網(wǎng)之魚對于DB的影響就會比大量穿透好的多了。
講了這么多，可以看到，原理很簡單，但要實際做一個BloomFilter可就麻煩了，已經(jīng)屬于科學(xué)家的范疇了，好在早早有人已經(jīng)搞定了java版的實現(xiàn)，用法很簡單，下一篇看看。

總結(jié)

以上是生活随笔為你收集整理的使用BloomFilter布隆过滤器解决缓存击穿、垃圾邮件识别、集合判重的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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