背景：

如果在平時(shí)我們要判斷一個(gè)元素是否在一個(gè)集合中，通常會(huì)采用查找比較的方法，下面分析不同的數(shù)據(jù)結(jié)構(gòu)查找效率：

• 采用線性表存儲(chǔ)，查找時(shí)間復(fù)雜度為O(N)
• 采用平衡二叉排序樹（AVL、紅黑樹）存儲(chǔ)，查找時(shí)間復(fù)雜度為O(logN)
• 采用哈希表存儲(chǔ)，考慮到哈希碰撞，整體時(shí)間復(fù)雜度也要O[log(n/m)]

當(dāng)需要判斷一個(gè)元素是否存在于海量數(shù)據(jù)集合中，不僅查找時(shí)間慢，還會(huì)占用大量存儲(chǔ)空間，接下來看一下布隆過濾器如何解決這個(gè)問題

?

1、什么是布隆過濾器：

布隆過濾器是一種空間效率很高的隨機(jī)數(shù)據(jù)結(jié)構(gòu)，專門用來檢測(cè)集合中是否存在特定的元素。布隆過濾器由一個(gè)長(zhǎng)度為m比特的位數(shù)組與k個(gè)獨(dú)立的哈希函數(shù)組成的數(shù)據(jù)結(jié)構(gòu)。位數(shù)組初始化均為0，所有的哈希函數(shù)都可以分別把輸入數(shù)據(jù)盡量均勻地散列。當(dāng)要向布隆過濾器中插入一個(gè)元素時(shí)，該元素經(jīng)過k個(gè)哈希函數(shù)計(jì)算產(chǎn)生k個(gè)哈希值，以哈希值作為位數(shù)組中的下標(biāo)，將所有k個(gè)對(duì)應(yīng)的比特值由0置為1。當(dāng)要查詢一個(gè)元素時(shí)，同樣將其經(jīng)過哈希函數(shù)計(jì)算產(chǎn)生哈希值，然后檢查對(duì)應(yīng)的k個(gè)比特值：如果有任意一個(gè)比特為0，表明該元素一定不在集合中；如果所有比特均為1，表明該元素有可能性在集合中。

由于可能出現(xiàn)哈希碰撞，不同元素計(jì)算的哈希值有可能一樣，導(dǎo)致一個(gè)不存在的元素有可能對(duì)應(yīng)的比特位為1，這就是所謂“假陽性”（false positive）。相對(duì)地，“假陰性”（false negative）在BF中是絕不會(huì)出現(xiàn)的。因此，Bloom Filter不適合那些“零錯(cuò)誤”的應(yīng)用場(chǎng)合。而在能容忍低錯(cuò)誤率的應(yīng)用場(chǎng)合下，Bloom Filter通過極少的錯(cuò)誤換取了存儲(chǔ)空間的極大節(jié)省。

所以，布隆過濾器認(rèn)為不在的，一定不會(huì)在集合中；布隆過濾器認(rèn)為在的，不一定存在集合中。

2、算法實(shí)現(xiàn)步驟：

• （1）選取k個(gè)哈希函數(shù)，記為 {h1,h2,…,hk}，至于參數(shù)k的選擇問題，我后面再說。
• （2）假設(shè)現(xiàn)在有n個(gè)元素需要被映射到bit數(shù)組中，bit數(shù)組的長(zhǎng)度是m。初始時(shí)，將m位的bit數(shù)組的每個(gè)位置的元素都置為0。一樣地，關(guān)于參數(shù)m的選擇我之后說。
• （3）現(xiàn)在，把這個(gè)n個(gè)元素依次用第1步選取的k個(gè)哈希函數(shù)映射到bit數(shù)組的位置上，bit數(shù)組被映射到的位置的元素變?yōu)?。顯然，一個(gè)元素能被映射到k個(gè)位置上。過程如圖所示，現(xiàn)在把元素集合{x,y,z}通過3個(gè)哈希函數(shù)映射到一個(gè)二進(jìn)制數(shù)組中。
• （4）最后，需要檢查一個(gè)元素是否在已有的集合中時(shí)，同樣用這k個(gè)哈希函數(shù)把要判斷的元素映射到bit數(shù)組的位置上，只要bit數(shù)組被映射到的位中有一個(gè)位不是1，那一定說明了這個(gè)元素不在已有的集合內(nèi)。如圖所示，檢查w是否在集合中時(shí)，有一個(gè)哈希函數(shù)將ww映射到了bit數(shù)組的元素為0的位置。

3、布隆過濾器優(yōu)缺點(diǎn)

（1）優(yōu)點(diǎn)：

• 節(jié)省空間：不需要存儲(chǔ)數(shù)據(jù)本身，只需要存儲(chǔ)數(shù)據(jù)對(duì)應(yīng)hash比特位
• 時(shí)間復(fù)雜度低：插入和查找的時(shí)間復(fù)雜度都為O(k)，k為哈希函數(shù)的個(gè)數(shù)

（2）缺點(diǎn)：

• 存在假陽性：布隆過濾器判斷存在，但可能出現(xiàn)元素實(shí)際上不在集合中的情況；誤判率取決于哈希函數(shù)的個(gè)數(shù)，對(duì)于哈希函數(shù)的個(gè)數(shù)選擇，我們第4部分會(huì)講
• 不支持刪除元素：如果一個(gè)元素被刪除，但是卻不能從布隆過濾器中刪除，這也是存在假陽性的原因之一

4、參數(shù)的選擇：

假設(shè)E表示錯(cuò)誤率，n表示要插入的元素個(gè)數(shù)，m表示bit數(shù)組的長(zhǎng)度，k表示hash函數(shù)的個(gè)數(shù)。

（1）當(dāng)hash函數(shù)個(gè)數(shù) k = (ln2) * (m/n)時(shí)，錯(cuò)誤率E最小（此時(shí)bit數(shù)組中有一半的值為0）

（2）在錯(cuò)誤率不大于E的情況下，bit數(shù)組的長(zhǎng)度m需要滿足的條件為：m ≥ n * lg(1/E)。

（3）結(jié)合上面兩個(gè)公式，在hash函數(shù)個(gè)數(shù)k取到最優(yōu)時(shí)，要求錯(cuò)誤率不大于E，這時(shí)我們對(duì)bit數(shù)組長(zhǎng)度m的要求是：m>=nlg(1/E) * lg(e) ，也就是 m ≥ 1.44n*lg(1/E)（lg表示以2為底的對(duì)數(shù)）

這里我給這幾個(gè)參數(shù)最終的結(jié)論，對(duì)這幾個(gè)參數(shù)的推導(dǎo)過程有興趣的讀者，可以閱讀這篇文章：https://blog.csdn.net/guoziqing506/article/details/52852515

5、布隆過濾器的應(yīng)用場(chǎng)景：

• 爬蟲系統(tǒng)url去重
• 垃圾郵件過濾
• 黑名單

問題實(shí)例：

給你A，B兩個(gè)文件，各存放50億條URL，每條URL占用64字節(jié)，內(nèi)存限制是4G，讓你找出A,B文件共同的URL。如果是三個(gè)乃至n個(gè)文件呢？?

如果允許找過的URL有一定的錯(cuò)誤率，那么我們可以使用布隆過濾器來實(shí)現(xiàn)。根據(jù)這個(gè)問題我們來計(jì)算下內(nèi)存占用，4G = 2^32大概是40億*8大概是340億的bit數(shù)組，n=50億，如果按出錯(cuò)率0.01算需要的大概是650億個(gè)bit。 現(xiàn)在可用的是340億，相差并不多，這樣可能會(huì)使出錯(cuò)率上升些。另外如果這些urlip是一一對(duì)應(yīng)的，就可以轉(zhuǎn)換成ip，則大大簡(jiǎn)單了。?

具體做法就是：將其中一個(gè)文件中的url使用Bloom filter映射為這340億bit，然后挨個(gè)讀取另外一個(gè)文件的url，檢查是否與Bloom filter，如果是，那么該url應(yīng)該是共同的url

5、如何解決布隆過濾器不支持刪除的問題：

（1）counting bloom filter：

Counting Bloom Filter將標(biāo)準(zhǔn) Bloom Filter位數(shù)組的每一位擴(kuò)展為一個(gè)小的計(jì)數(shù)器（counter），在插入元素時(shí)給對(duì)應(yīng)的k（k為哈希函數(shù)個(gè)數(shù)）個(gè)Counter的值分別加1，刪除元素時(shí)給對(duì)應(yīng)的k個(gè)Counter的值分別減1。Counting Bloom Filter通過多占用幾倍的存儲(chǔ)空間的代價(jià)，給Bloom Filter增加了刪除操作。

（2）布谷鳥過濾器:

對(duì)于這種方式有興趣的讀者可以閱讀這篇文章：https://juejin.cn/post/6924636027948630029#heading-1

?

總結(jié)

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

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