布隆過濾器算法用於搜索

問題： 什麼是布隆過濾器？

答案 → 布隆過濾器是一種空間效率高的概率型數據結構。它已經存在了 50 年。它用於回答這樣的問題：這個元素是否在集合中？

問題： 布隆過濾器的實際應用有哪些？

答案 → 布隆過濾器是一種具有許多實際應用的數據結構。它可以在瀏覽器、網絡路由器和數據庫中找到，僅舉幾例。

問題： 可以用布隆過濾器的實際應用場景是什麼？

答案 → 布隆過濾器用於回答這個問題：這個元素是否存在於集合中？布隆過濾器會回答 “絕對不是” 或 “可能是”。這個 “可能是” 的部分使得布隆過濾器具有概率性。

• 可能發生假陽性，即元素實際上不在集合中，但布隆過濾器說它存在。• 不可能發生假陰性，即元素存在於集合中，但布隆過濾器說它不存在。

問題： 使用布隆過濾器的權衡是什麼？

答案 → 爲了有時提供不正確的假陽性答案，布隆過濾器比像哈希表這樣的數據結構消耗的內存要少得多，後者能夠每次都提供正確的答案。

問題： 使用布隆過濾器時我們必須注意什麼？

答案 → 如果我們的用例可以容忍一些假陽性並且不能容忍假陰性，那麼我們可以選擇布隆過濾器。

問題： 布隆過濾器是如何工作的？

答案 → 布隆過濾器的關鍵成分是一些好的哈希函數。

• 這些哈希函數應該快速，並且它們應該產生均勻且隨機分佈的輸出。• 只要碰撞很少，就沒關係。

理解 → 一個布隆過濾器是一個大的桶集合，每個桶包含一個比特位，它們都從零開始。假設我們想要跟蹤我喜歡的食物。以這個例子：

步驟 #1.) 我們從一個大小爲 10 的布隆過濾器開始，標記從 0 到 9：

步驟 #2.) 現在，對於每個傳入的元素：

• 我們將通過三個不同的哈希函數傳遞它。• 每個哈希函數最終會返回一個 0 到 9 的範圍內的值。

例如，我們想將元素 “Ribeye”（一種肉類）放入布隆過濾器。所以，通過三個哈希函數傳遞這個元素：

• 假設通過哈希函數 1 傳遞元素 “Ribeye” 時，我們得到的值爲 1。這意味着，索引 1 處的值會被標記爲 1。• 假設通過哈希函數 2 傳遞元素 “Ribeye” 時，我們得到的值爲 3。這意味着，索引 3 處的值會被標記爲 1。• 假設通過哈希函數 3 傳遞元素 “Ribeye” 時，我們得到的值爲 4。這

意味着，索引 4 處的值會被標記爲 1。

步驟 #3.) 現在，如果我們想檢查 “Ribeye” 是否在布隆過濾器中：

• 我們再次將 “Ribeye” 通過相同的三個哈希函數。• 如果所有三個哈希函數返回的索引位置上的值都是 1，那麼 “Ribeye” 可能在布隆過濾器中。

理解 → 由於我們檢查的每個索引位置上的值都是 1，所以 “Ribeye” 可能在布隆過濾器中。

這種方法可以快速檢查一個元素是否可能存在於一個集合中，同時使用的內存比存儲整個集合少得多。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/lyLnnambD9irB_Idb3XnPg