布隆過濾器經(jīng)常用于判斷一個(gè)數(shù)據(jù)是否存在的手段箩溃。由于在查詢時(shí)間和空間使用率上有著優(yōu)勢(shì)被廣泛使用。這里記錄一下布隆過濾器的原理。
布隆過濾器用一個(gè)bit的vector來存貯結(jié)果挖滤，并使用多個(gè)hash函數(shù)议纯。在插入的時(shí)候會(huì)將相關(guān)的數(shù)據(jù)hash計(jì)算出來并將對(duì)應(yīng)的位設(shè)置為1父款。如果需要檢測(cè)某一個(gè)項(xiàng)是否存在，需要計(jì)算每一個(gè)hash函數(shù)，并查看對(duì)應(yīng)bit的值是否已經(jīng)為1憨攒。如果有一個(gè)hash函數(shù)的對(duì)應(yīng)的bit不為1則相關(guān)數(shù)據(jù)一定不存在世杀。如果每個(gè)都為1則可能存在（存在false positive 問題）
False positive 問題。
由于布隆過濾器是將相應(yīng)位置為1肝集，存在檢驗(yàn)的值可能是由多個(gè)數(shù)據(jù)拼湊而成瞻坝。舉一個(gè)例子，假設(shè)現(xiàn)在布隆過濾器有5個(gè)bit（實(shí)際要大得多）杏瞻。在插入data1的時(shí)候兩個(gè)hash函數(shù)分別將1所刀，4置為1，插入數(shù)據(jù)data2的時(shí)候兩個(gè)hash函數(shù)分別將2捞挥，3置為1「〈矗現(xiàn)在我試圖檢驗(yàn)data3是否存在，而data3算出來的hash分別是1砌函，3斩披。雖然對(duì)應(yīng)位已經(jīng)是1了，但是實(shí)際是沒有這個(gè)數(shù)據(jù)的胸嘴。
布隆過濾器缺點(diǎn)
1. 擴(kuò)容比較困難
2.刪除比較困難
