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

布隆過濾器的工作原理

從數據庫或存儲中讀取數據是一項成本較高的操作。為了優化這一過程，我們使用布隆過濾器來檢查鍵值對是否存在，只有當過濾器返回“是”的時候，我們才會執行數據庫讀取操作。布隆過濾器節省空間，可以存儲在內存中。此外，對一個值進行查找測試可以在O(1)時間內完成。稍后會詳細介紹這一點。讓我們通過一個例子來探討這個概念：

我們為鍵“Key1”創建了一個布隆過濾器。當客戶端請求與“Key1”的任何值相關聯的數據時，我們首先通過布隆過濾器傳遞該值以檢查其是否存在。在上面的圖中，我們嘗試讀取與“Key1”的三個不同值相關聯的有效載荷：

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

盡管可能會出現假陽性，但永遠不會出現假陰性——這意味著不可能存在一個鍵值對，而過濾器返回“否”。

如何實現布隆過濾器

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

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

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

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

選擇合適的哈希函數和足夠長度的位數組有助于減少沖突。此外，了解可能輸入值的范圍，例如所有有限范圍內的字符串或數字，可以幫助選擇最優的哈希函數和位數組長度。

時間和空間復雜度

哈希函數的運行時間為O(1)，使得設置和測試操作均為常數時間操作。所需空間取決于位數組的長度，然而，與傳統索引相比，布隆過濾器所占空間極小，因為它并不存儲實際值，而只是為每個值存儲幾個比特。

限制條件

1. 布隆過濾器僅支持精確匹配，因為其操作依賴于通過哈希函數傳遞輸入，這需要精確匹配。
2. 從布隆過濾器中刪除一個值并非易事，因為數組中的位不能簡單地被重置。數組中設置的位可能對應多個值。若要支持刪除操作，則需要重新創建位數組。
3. 如果哈希函數和位數組長度選擇不當，可能會導致假陽性數量增加，使過濾器效率低下，甚至可能成為負擔。在最壞的情況下，添加完所有值后，數組中的所有位都可能被設置。在這種情況下，任何測試都會從過濾器中得到肯定的響應。為解決此問題，可以使用調整大小的位數組和針對需求定制的新哈希函數重新創建過濾器。

寫在最后的話

希望這篇文章能為你介紹布隆過濾器（如果你之前還不熟悉的話），并為你提供一個有價值的數據結構來擴展你的知識。和其他任何數據結構一樣，它的使用取決于特定的用例，但在合適的機會出現時，它可能會非常有用。

原文標題：An Introduction to Bloom Filters，作者：Sandeep Kumar Gond