需求場(chǎng)景

1. 經(jīng)常需要判斷一個(gè)元素是否在一個(gè)集合中
2. 集合規(guī)模巨大，散列表存儲(chǔ)效率低。
   2.1 散列表中，每條數(shù)據(jù)都需要對(duì)應(yīng)一個(gè)信息指紋。當(dāng)存儲(chǔ)海量數(shù)據(jù)時(shí)，需要太多空間
   2.2 散列表存儲(chǔ)效率不高，一般只有 50%。

布隆過(guò)濾器的優(yōu)點(diǎn)

通過(guò)數(shù)學(xué)原理——兩個(gè)完全隨機(jī)的數(shù)字沖突的概率極小。使得布隆過(guò)濾器可以只使用散列表 1/8 或者 1/4 的大小解決同樣的問(wèn)題。

布隆過(guò)濾器的缺點(diǎn)

因?yàn)榈讓釉硎莾蓚€(gè)完全隨機(jī)的數(shù)字沖突的概率極小，但是不可避免仍可能存在沖突。此時(shí)的“沖突”，就會(huì)造成誤判。使得不在集合中的元素，被誤判為存在集合中，得到錯(cuò)誤的結(jié)果。

彌補(bǔ)缺點(diǎn)

常見(jiàn)的解決辦法是再開(kāi)一個(gè)小的白名單，存儲(chǔ)那些被誤判的信息。

工作原理

布隆過(guò)濾器實(shí)際上是一個(gè)很長(zhǎng)的二進(jìn)制向量和一系列隨機(jī)映射函數(shù)。

• 構(gòu)建布隆過(guò)濾器

1. 假定存儲(chǔ) i 個(gè)數(shù)據(jù)，先建立 16 * i 個(gè)比特位，全部置為 0 。
2. 對(duì)每個(gè)數(shù)據(jù) x，用 8 個(gè)不同的隨機(jī)數(shù)產(chǎn)生器 F1, F2, ...,F8 產(chǎn)生 8 個(gè)信息指紋 f1, f2,..., f8
3. 對(duì)每個(gè)信息指紋，用一個(gè)隨機(jī)數(shù)產(chǎn)生器 G 映射成 16 * i 個(gè)比特位中的某一位，得到這八個(gè)映射后的比特位下標(biāo) g1, g2, ..., g8。
4. 把對(duì)應(yīng)八個(gè)比特位置為 1。
5. 對(duì) i 個(gè)數(shù)據(jù)重復(fù) 2 到 4 三個(gè)步驟。

• 使用布隆過(guò)濾器

1. 對(duì)要檢測(cè)數(shù)據(jù) y，重復(fù)構(gòu)建階段的 2 和 3 步驟，得到 y，對(duì)應(yīng)的八個(gè)比特位下標(biāo) t1, t2, ..., t8。
2. 檢查這八個(gè)比特位下標(biāo)是否全為 1。若是，判定該元素已經(jīng)存在集合中；否則，該元素不存在集合中。

為什么選擇數(shù)字 16 和 8 作為構(gòu)建的參數(shù)？

前面提到，布隆過(guò)濾器的一個(gè)不足之處就是它可以把可能不存在集合中的元素錯(cuò)判成集合中的元素，這在檢驗(yàn)上被稱(chēng)為“假陽(yáng)性”。

而使用這兩個(gè)數(shù)字構(gòu)建出來(lái)的布隆過(guò)濾器，，假陽(yáng)性的概率是萬(wàn)分之五，在普通情況下配合白名單足夠滿(mǎn)足需求了。

關(guān)于這兩個(gè)數(shù)字的不同取值，如何導(dǎo)致不同假陽(yáng)性概率的分析，可以查看谷歌。