詳解布隆過(guò)濾器的原理，使用場(chǎng)景和注意事項(xiàng)
概念理解
- 本質(zhì)上布隆過(guò)濾器是一種數(shù)據(jù)結(jié)構(gòu)，比較巧妙的概率型數(shù)據(jù)結(jié)構(gòu)（probabilistic data structure），特點(diǎn)是高效地插入和查詢，可以用來(lái)告訴你"某樣?xùn)|西一定不存在 或者 可能存在"。
- 相比于傳統(tǒng)的 List、Set、Map 等數(shù)據(jù)結(jié)構(gòu)，它更高效、占用空間更少，但是缺點(diǎn)是其返回的結(jié)果是概率性的，而不是確切的。
- 不支持刪除
實(shí)現(xiàn)原理
布隆過(guò)濾器是一個(gè) bit 向量或者說(shuō) bit 數(shù)組，長(zhǎng)這樣：
如果我們要映射一個(gè)值到布隆過(guò)濾器中，我們需要使用多個(gè)不同的哈希函數(shù)生成多個(gè)哈希值，并對(duì)每個(gè)生成的哈希值指向的 bit 位置 1，例如針對(duì)值 “baidu” 和三個(gè)不同的哈希函數(shù)分別生成了哈希值 1、4、7，則上圖轉(zhuǎn)變?yōu)椋?/p>
Ok，我們現(xiàn)在再存一個(gè)值 “tencent”，如果哈希函數(shù)返回 3、4、8 的話，圖繼續(xù)變?yōu)椋?/p>
值得注意的是，4 這個(gè) bit 位由于兩個(gè)值的哈希函數(shù)都返回了這個(gè) bit 位，因此它被覆蓋了?，F(xiàn)在我們?nèi)绻氩樵?“dianping” 這個(gè)值是否存在，哈希函數(shù)返回了 1、5、8三個(gè)值，結(jié)果我們發(fā)現(xiàn) 5 這個(gè) bit 位上的值為 0，說(shuō)明沒(méi)有任何一個(gè)值映射到這個(gè) bit 位上，因此我們可以很確定地說(shuō) “dianping” 這個(gè)值不存在。而當(dāng)我們需要查詢 “baidu” 這個(gè)值是否存在的話，那么哈希函數(shù)必然會(huì)返回 1、4、7，然后我們檢查發(fā)現(xiàn)這三個(gè) bit 位上的值均為 1，那么我們可以說(shuō) “baidu” 存在了么？答案是不可以，只能是 “baidu” 這個(gè)值可能存在。
這是為什么呢？答案跟簡(jiǎn)單，因?yàn)殡S著增加的值越來(lái)越多，被置為 1 的 bit 位也會(huì)越來(lái)越多，這樣某個(gè)值 “taobao” 即使沒(méi)有被存儲(chǔ)過(guò)，但是萬(wàn)一哈希函數(shù)返回的三個(gè) bit 位都被其他值置位了 1 ，那么程序還是會(huì)判斷 “taobao” 這個(gè)值存在。
哈希函數(shù)個(gè)數(shù)和布隆過(guò)濾器長(zhǎng)度 的選擇
- 過(guò)小的布隆過(guò)濾器很快所有的 bit 位均為 1，那么查詢?nèi)魏沃刀紩?huì)返回“可能存在”，起不到過(guò)濾的目的了。布隆過(guò)濾器的長(zhǎng)度會(huì)直接影響誤報(bào)率，布隆過(guò)濾器越長(zhǎng)其誤報(bào)率越小。
- 哈希函數(shù)的個(gè)數(shù)也需要權(quán)衡，個(gè)數(shù)越多則布隆過(guò)濾器 bit 位置位 1 的速度越快，且布隆過(guò)濾器的效率越低；但是如果太少的話，那我們的誤報(bào)率會(huì)變高。
