布隆過濾器（Bloom Filters）是一種不太為人所知的數(shù)據(jù)結(jié)構(gòu)，目前開發(fā)者并沒有廣泛使用它。不過，布隆過濾器是一種高效節(jié)省空間且高度依賴概率的數(shù)據(jù)結(jié)構(gòu)，每一位開發(fā)者都應(yīng)當(dāng)對(duì)其有所了解，它能夠在很大程度上加快精確匹配查詢的速度，尤其是在沒有為該字段添加索引的情況下。布隆過濾器的空間效率還帶來了額外的優(yōu)勢(shì)，即可以為多個(gè)字段創(chuàng)建過濾器。

布隆過濾器的工作原理

從數(shù)據(jù)庫(kù)或存儲(chǔ)中讀取數(shù)據(jù)是一項(xiàng)成本較高的操作。為了優(yōu)化這一過程，我們使用布隆過濾器來檢查鍵值對(duì)是否存在，只有當(dāng)過濾器返回“是”的時(shí)候，我們才會(huì)執(zhí)行數(shù)據(jù)庫(kù)讀取操作。布隆過濾器節(jié)省空間，可以存儲(chǔ)在內(nèi)存中。此外，對(duì)一個(gè)值進(jìn)行查找測(cè)試可以在O(1)時(shí)間內(nèi)完成。稍后會(huì)詳細(xì)介紹這一點(diǎn)。讓我們通過一個(gè)例子來探討這個(gè)概念：

我們?yōu)殒I“Key1”創(chuàng)建了一個(gè)布隆過濾器。當(dāng)客戶端請(qǐng)求與“Key1”的任何值相關(guān)聯(lián)的數(shù)據(jù)時(shí)，我們首先通過布隆過濾器傳遞該值以檢查其是否存在。在上面的圖中，我們嘗試讀取與“Key1”的三個(gè)不同值相關(guān)聯(lián)的有效載荷：

1. 對(duì)于第一個(gè)值“Value1”，過濾器返回“否”，這使我們能夠中斷讀取操作并返回“不可用”。
2. 在第二個(gè)例子中，“Value2”存在于數(shù)據(jù)庫(kù)中。過濾器返回“是”，這促使我們執(zhí)行數(shù)據(jù)庫(kù)讀取以檢索與“Key1”等于“Value2”相關(guān)聯(lián)的有效載荷。
3. 第三個(gè)例子更為有趣：過濾器對(duì)“Value3”返回“是”，但數(shù)據(jù)庫(kù)中不存在與“Key1”等于“Value3”相關(guān)聯(lián)的有效載荷。這被稱為假陽性。在這種情況下，執(zhí)行了數(shù)據(jù)庫(kù)讀取，但沒有返回任何值。

盡管可能會(huì)出現(xiàn)假陽性，但永遠(yuǎn)不會(huì)出現(xiàn)假陰性——這意味著不可能存在一個(gè)鍵值對(duì)，而過濾器返回“否”。

如何實(shí)現(xiàn)布隆過濾器

布隆過濾器是一個(gè)長(zhǎng)度為“n”的位數(shù)組，所有值都初始化為0。它需要“h”個(gè)不同的哈希函數(shù)來填充位數(shù)組。當(dāng)一個(gè)值被添加到過濾器中時(shí)，每個(gè)哈希函數(shù)都應(yīng)用于該值，以生成一個(gè)介于0和n之間的數(shù)字，并在位數(shù)組中設(shè)置相應(yīng)的“h”個(gè)位。

為了測(cè)試一個(gè)元素是否存在于數(shù)組中，我們將相同的哈希函數(shù)集合應(yīng)用于該元素，生成介于0和n之間的“h”個(gè)索引。然后，我們檢查這些索引對(duì)應(yīng)的位數(shù)組中的相應(yīng)位是否被設(shè)置為1。如果所有位都被設(shè)置為1，則認(rèn)為是命中，過濾器返回“真（true）”。

如上例所示，Value1、Value2和Value3被添加到過濾器中。每個(gè)值都通過三個(gè)哈希函數(shù)，并將位數(shù)組中對(duì)應(yīng)的位設(shè)置好。之后，在測(cè)試階段，Value1、Value4和Value5通過相同的哈希函數(shù)集來確定這些值是否存在。

由于哈希函數(shù)的特性和其有限的輸出值范圍，多個(gè)輸入可能會(huì)生成相同的哈希值，從而導(dǎo)致沖突。沖突可能會(huì)導(dǎo)致假陽性，如Value5的情況所示。

選擇合適的哈希函數(shù)和足夠長(zhǎng)度的位數(shù)組有助于減少?zèng)_突。此外，了解可能輸入值的范圍，例如所有有限范圍內(nèi)的字符串或數(shù)字，可以幫助選擇最優(yōu)的哈希函數(shù)和位數(shù)組長(zhǎng)度。

時(shí)間和空間復(fù)雜度

哈希函數(shù)的運(yùn)行時(shí)間為O(1)，使得設(shè)置和測(cè)試操作均為常數(shù)時(shí)間操作。所需空間取決于位數(shù)組的長(zhǎng)度，然而，與傳統(tǒng)索引相比，布隆過濾器所占空間極小，因?yàn)樗⒉淮鎯?chǔ)實(shí)際值，而只是為每個(gè)值存儲(chǔ)幾個(gè)比特。

限制條件

1. 布隆過濾器僅支持精確匹配，因?yàn)槠洳僮饕蕾囉谕ㄟ^哈希函數(shù)傳遞輸入，這需要精確匹配。
2. 從布隆過濾器中刪除一個(gè)值并非易事，因?yàn)閿?shù)組中的位不能簡(jiǎn)單地被重置。數(shù)組中設(shè)置的位可能對(duì)應(yīng)多個(gè)值。若要支持刪除操作，則需要重新創(chuàng)建位數(shù)組。
3. 如果哈希函數(shù)和位數(shù)組長(zhǎng)度選擇不當(dāng)，可能會(huì)導(dǎo)致假陽性數(shù)量增加，使過濾器效率低下，甚至可能成為負(fù)擔(dān)。在最壞的情況下，添加完所有值后，數(shù)組中的所有位都可能被設(shè)置。在這種情況下，任何測(cè)試都會(huì)從過濾器中得到肯定的響應(yīng)。為解決此問題，可以使用調(diào)整大小的位數(shù)組和針對(duì)需求定制的新哈希函數(shù)重新創(chuàng)建過濾器。

寫在最后的話

希望這篇文章能為你介紹布隆過濾器（如果你之前還不熟悉的話），并為你提供一個(gè)有價(jià)值的數(shù)據(jù)結(jié)構(gòu)來擴(kuò)展你的知識(shí)。和其他任何數(shù)據(jù)結(jié)構(gòu)一樣，它的使用取決于特定的用例，但在合適的機(jī)會(huì)出現(xiàn)時(shí)，它可能會(huì)非常有用。

原文標(biāo)題：An Introduction to Bloom Filters，作者：Sandeep Kumar Gond