概念理解
- 本質(zhì)上布隆過濾器是一種數(shù)據(jù)結(jié)構(gòu)，比較巧妙的概率型數(shù)據(jù)結(jié)構(gòu)（probabilistic data structure）汁汗，特點(diǎn)是高效地插入和查詢咪辱，可以用來告訴你"某樣?xùn)|西一定不存在 或者 可能存在"棋电。
- 相比于傳統(tǒng)的 List、Set苇侵、Map 等數(shù)據(jù)結(jié)構(gòu)赶盔，它更高效、占用空間更少榆浓，但是缺點(diǎn)是其返回的結(jié)果是概率性的于未，而不是確切的。
- 不支持刪除
實(shí)現(xiàn)原理
布隆過濾器是一個 bit 向量或者說 bit 數(shù)組陡鹃，長這樣：
如果我們要映射一個值到布隆過濾器中烘浦，我們需要使用多個不同的哈希函數(shù)生成多個哈希值，并對每個生成的哈希值指向的 bit 位置 1萍鲸，例如針對值 “baidu” 和三個不同的哈希函數(shù)分別生成了哈希值 1谎倔、4、7猿推，則上圖轉(zhuǎn)變?yōu)椋?/p>
Ok片习，我們現(xiàn)在再存一個值 “tencent”，如果哈希函數(shù)返回 3蹬叭、4藕咏、8 的話，圖繼續(xù)變?yōu)椋?/p>
值得注意的是秽五，4 這個 bit 位由于兩個值的哈希函數(shù)都返回了這個 bit 位孽查，因此它被覆蓋了。現(xiàn)在我們?nèi)绻氩樵?“dianping” 這個值是否存在坦喘，哈希函數(shù)返回了 1盲再、5、8三個值瓣铣，結(jié)果我們發(fā)現(xiàn) 5 這個 bit 位上的值為 0答朋，說明沒有任何一個值映射到這個 bit 位上，因此我們可以很確定地說 “dianping” 這個值不存在棠笑。而當(dāng)我們需要查詢 “baidu” 這個值是否存在的話梦碗，那么哈希函數(shù)必然會返回 1、4蓖救、7洪规，然后我們檢查發(fā)現(xiàn)這三個 bit 位上的值均為 1，那么我們可以說 “baidu” 存在了么循捺？答案是不可以斩例，只能是 “baidu” 這個值可能存在。
這是為什么呢从橘？答案跟簡單念赶，因?yàn)殡S著增加的值越來越多础钠，被置為 1 的 bit 位也會越來越多，這樣某個值 “taobao” 即使沒有被存儲過晶乔，但是萬一哈希函數(shù)返回的三個 bit 位都被其他值置位了 1 ，那么程序還是會判斷 “taobao” 這個值存在牺勾。
哈希函數(shù)個數(shù)和布隆過濾器長度 的選擇
- 過小的布隆過濾器很快所有的 bit 位均為 1正罢，那么查詢?nèi)魏沃刀紩祷亍翱赡艽嬖凇保鸩坏竭^濾的目的了驻民。布隆過濾器的長度會直接影響誤報(bào)率翻具，布隆過濾器越長其誤報(bào)率越小。
- 哈希函數(shù)的個數(shù)也需要權(quán)衡回还，個數(shù)越多則布隆過濾器 bit 位置位 1 的速度越快裆泳，且布隆過濾器的效率越低；但是如果太少的話柠硕，那我們的誤報(bào)率會變高工禾。
