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

答案 → 布隆過濾器是一種空間效率高的概率型數(shù)據(jù)結(jié)構(gòu)。它已經(jīng)存在了50年。它用于回答這樣的問題：這個(gè)元素是否在集合中？

問題： 布隆過濾器的實(shí)際應(yīng)用有哪些？

答案 → 布隆過濾器是一種具有許多實(shí)際應(yīng)用的數(shù)據(jù)結(jié)構(gòu)。它可以在瀏覽器、網(wǎng)絡(luò)路由器和數(shù)據(jù)庫中找到，僅舉幾例。

問題： 可以用布隆過濾器的實(shí)際應(yīng)用場(chǎng)景是什么？

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

• 可能發(fā)生假陽性，即元素實(shí)際上不在集合中，但布隆過濾器說它存在。
• 不可能發(fā)生假陰性，即元素存在于集合中，但布隆過濾器說它不存在。

問題： 使用布隆過濾器的權(quán)衡是什么？

答案 → 為了有時(shí)提供不正確的假陽性答案，布隆過濾器比像哈希表這樣的數(shù)據(jù)結(jié)構(gòu)消耗的內(nèi)存要少得多，后者能夠每次都提供正確的答案。

問題： 使用布隆過濾器時(shí)我們必須注意什么？

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

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

答案 → 布隆過濾器的關(guān)鍵成分是一些好的哈希函數(shù)。

• 這些哈希函數(shù)應(yīng)該快速，并且它們應(yīng)該產(chǎn)生均勻且隨機(jī)分布的輸出。
• 只要碰撞很少，就沒關(guān)系。

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

步驟#1.) 我們從一個(gè)大小為10的布隆過濾器開始，標(biāo)記從0到9：

步驟#2.) 現(xiàn)在，對(duì)于每個(gè)傳入的元素：

• 我們將通過三個(gè)不同的哈希函數(shù)傳遞它。
• 每個(gè)哈希函數(shù)最終會(huì)返回一個(gè)0到9的范圍內(nèi)的值。

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

• 假設(shè)通過哈希函數(shù)1傳遞元素“Ribeye”時(shí)，我們得到的值為1。這意味著，索引1處的值會(huì)被標(biāo)記為1。
• 假設(shè)通過哈希函數(shù)2傳遞元素“Ribeye”時(shí)，我們得到的值為3。這意味著，索引3處的值會(huì)被標(biāo)記為1。
• 假設(shè)通過哈希函數(shù)3傳遞元素“Ribeye”時(shí)，我們得到的值為4。這意味著，索引4處的值會(huì)被標(biāo)記為1。

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

• 我們?cè)俅螌ⅰ癛ibeye”通過相同的三個(gè)哈希函數(shù)。
• 如果所有三個(gè)哈希函數(shù)返回的索引位置上的值都是1，那么“Ribeye”可能在布隆過濾器中。

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

這種方法可以快速檢查一個(gè)元素是否可能存在于一個(gè)集合中，同時(shí)使用的內(nèi)存比存儲(chǔ)整個(gè)集合少得多。