需求場景
- 經(jīng)常需要判斷一個元素是否在一個集合中
- 集合規(guī)模巨大如孝，散列表存儲效率低。
2.1 散列表中，每條數(shù)據(jù)都需要對應(yīng)一個信息指紋犹撒。當(dāng)存儲海量數(shù)據(jù)時，需要太多空間
2.2 散列表存儲效率不高粒褒，一般只有 50%识颊。
布隆過濾器的優(yōu)點
通過數(shù)學(xué)原理——兩個完全隨機(jī)的數(shù)字沖突的概率極小。使得布隆過濾器可以只使用散列表 1/8 或者 1/4 的大小解決同樣的問題。
布隆過濾器的缺點
因為底層原理是兩個完全隨機(jī)的數(shù)字沖突的概率極小祥款，但是不可避免仍可能存在沖突清笨。此時的“沖突”，就會造成誤判刃跛。使得不在集合中的元素抠艾，被誤判為存在集合中，得到錯誤的結(jié)果桨昙。
彌補缺點
常見的解決辦法是再開一個小的白名單检号，存儲那些被誤判的信息。
工作原理
布隆過濾器實際上是一個很長的二進(jìn)制向量和一系列隨機(jī)映射函數(shù)蛙酪。
- 構(gòu)建布隆過濾器
- 假定存儲
i個數(shù)據(jù)齐苛，先建立16 * i個比特位，全部置為 0 桂塞。 - 對每個數(shù)據(jù)
x凹蜂，用8個不同的隨機(jī)數(shù)產(chǎn)生器F1, F2, ...,F8產(chǎn)生 8 個信息指紋f1, f2,..., f8 - 對每個信息指紋，用一個隨機(jī)數(shù)產(chǎn)生器
G映射成16 * i個比特位中的某一位阁危，得到這八個映射后的比特位下標(biāo)g1, g2, ..., g8玛痊。 - 把對應(yīng)八個比特位置為 1。
- 對
i個數(shù)據(jù)重復(fù) 2 到 4 三個步驟狂打。
- 使用布隆過濾器
- 對要檢測數(shù)據(jù)
y卿啡，重復(fù)構(gòu)建階段的 2 和 3 步驟，得到y菱父，對應(yīng)的八個比特位下標(biāo)t1, t2, ..., t8颈娜。 - 檢查這八個比特位下標(biāo)是否全為 1。若是浙宜，判定該元素已經(jīng)存在集合中官辽；否則，該元素不存在集合中粟瞬。
為什么選擇數(shù)字 16 和 8 作為構(gòu)建的參數(shù)同仆？
前面提到，布隆過濾器的一個不足之處就是它可以把可能不存在集合中的元素錯判成集合中的元素裙品，這在檢驗上被稱為“假陽性”俗批。
而使用這兩個數(shù)字構(gòu)建出來的布隆過濾器，市怎，假陽性的概率是萬分之五岁忘，在普通情況下配合白名單足夠滿足需求了。
關(guān)于這兩個數(shù)字的不同取值区匠，如何導(dǎo)致不同假陽性概率的分析干像，可以查看谷歌。
