Bloom Filter

當我們想要快速地知道某個資料是否曾經在系統中儲存過的時候，基本的作法就是時間複雜度 O(n) 或者是空間複雜度 O(n) 的選擇。

• 時間複雜度 O(n)：在存放的資料當中從第一個一直查到最後一個，花費 O(n) 的時間複雜度、同時沒有額外的空間複雜度需求，就能知道指定的某個資料到底有沒有存在。
• 空間複雜度 O(n)：存放一個配對表，例如如果資料是數字，那麼找配對表當中的指定位置，就能知道該資料是否存在。此時配對表需要花費 O(n) 的空間複雜度、但是帶來 O(1) 的時間複雜度優勢。

而 Bloom Filter 就是屬於中間型的解法，需要略高於 O(1) 的時間複雜度以及低於 O(n) 的空間複雜度。白話來說，就是 n 個資料並不需要長度為 n 的空間來存放，就能夠用來檢查 n 個資料中的任意資料是否存在於系統中。

概念上，Bloom Filter 就是使用一個陣列，用多個 hash function 來決定某個資料的位置，然後把陣列上的這些位置全都標為 1。其中資料不一定要是什麼格式，要求只是使用的 hash function 能夠輸出一個數字，來代表在陣列上的位置。因此檢查資料在不在系統中，只需要檢查這些位置是否全都是 1 就能夠知道了。不過因為是用 hash function，因此可以想見應該存在 collision 的問題，也就是有可能有多個資料會同時使用某個相同的位置，只是不會每個位置全都一樣。另外這個檢查方式也可以想像到潛在的問題：當檢查出某個資料的位置都是 1，有可能只是這些位置剛好都是被其他不同資料標上 1，並不一定真的表示我們要找的這個資料就確實存在。因此 Bloom Filter 無法保證某個資料一定存在（可能有 False Positive）、但可以保證某個資料一定不存在（不會有 False Negative）。

另一方面，因為 Bloom Filter 在儲存時只會存 0 和 1，表示它其實不知道每個位置是由哪個資料標上的。反過來說就是，當我因為加入資料的動作，把某個位置的值從 0 改為 1 後，日後我就再也無法把那個位置改回 0 了，因為 Bloom Filter 沒辦法知道這個位置跟哪個資料有關係。這也就形成 Bloom Filter 這個結構只能夠增加資料，而無法移除資料的限制。

所以簡要來說，Bloom Filter 就是個用比較少的儲存空間，快速判斷某個資料是否曾經被存放過的結構。

使用情境

以 Redia 文件 [4] 的範例來說，可以用來檢查像是帳號是否被使用過：

> BF.ADD usernames funnyfred
(integer) 1
> BF.ADD usernames fredisfunny
(integer) 1
> BF.ADD usernames fred
(integer) 1
> BF.ADD usernames funfred
(integer) 1

> BF.EXISTS usernames fred
(integer) 1
> BF.EXISTS usernames fred_is_funny
(integer) 0

參考資料

1. [論文解讀][Bloom Filter] 深入討論 Bloom Filter
2. 資料結構大便當：Bloom Filter
3. 海量数据处理算法—Bloom Filter
4. Redis: Bloom Filter Pattern