大類的技術手記

Bloom Filter 是一種可以儲存「某一個元素是否存在」的集合， 我們可以用這種資料結構快速查詢像是「某隻小雞是否在這間雞舍」或「某位學生是不是在這間實驗室」 這一類的資訊。

這種資料結構有三個非常重要的特性：

• 不存在漏報(False Negative)：有一定會說
• 但卻可能誤報(False Positive)：但說了不一定會對
• 確定某元素是否在集合的代價和元素數目無關：不管對不對，反正很快

這個結構有趣的地方在於它並不準確，它可能會誤報，也許它會說：「這隻小雞在這間雞舍！」， 但實際上這隻小雞並不在這間雞舍。不過反過來說，若它說：「這隻小雞『不在』這間雞舍！」， 那小雞就絕對不會出現在這間雞舍中。

雖然這種資料結構可能不準確，但查詢速度卻非常快，所以很適合用來當作事前的篩選。 舉例而言，若我想找「某隻小雞在那一間雞舍的資訊」，就可以透過 Bloom Filter 對每一間雞舍做篩選， 篩去 Bloom Filter 說「這隻小雞不在這間雞舍」的雞舍，再對剩下的雞舍做詳細的調查， 這樣就會比漫無目的找還要快上許多。

一般而言，一個搜尋演算法，若搜尋的速度要很快，資料結構所佔的空間就會相對比較大， 但若要求佔的空間要小，速度可能就快不起來。基本上，好的演算法就是取得空間和速度的平衡點， 讓速度足夠快，而且空間也不會用太多。

但 Bloom filter 卻很神奇的既速度快，而且所佔的空間也很小，不過代價是用準確率換取的空間大小。 空間越大，準確率越高，空間越小，準確率就越低。

「那麼這個方法到底是怎麼做到這一點的呢？」

這個方法是由一個叫 Bloom 的人提出的(顯而易見吧？)， 它實際上是一個很長的 bit-vector，和很多個 Hash 函式組成。 演算法的最初的概念也很簡單，想要找某元素存不存在？ 那就準備一個 bit-vector，再使用 Hash 函式為每個元素找對應的位置。 如果該元素存在，即設為 1，如果不存在，就設為 0。 那麼以後想查詢某元素存不存在，只要看 Hash 函式編碼後對應的位置內容是不是 1 即可。

很簡單吧？不過若要使用 Hash 函式的話，就會有一個很重要但很基本問題一定要考慮， 那就是 Key 和 Key 之間可能會有「碰撞」的問題，而一旦發生「碰撞」，就有可能誤報， 明明不存在，卻回報存在。

這個問題最直觀的解決辦法就是增加 bit-vector 的大小，但是增加大小就會佔用更多的空間， 這樣就會違反 Bloom filter 要佔很小空間的初衷了。

所以 Bloom 實際上採用的是另一種解法，那就是使用多個 Hash 函式。

「一個 Hash 函式發生碰撞很容易，但若使用多個不同的 Hash 函式， 要每一個 Hash 函式對應的位置都剛好同時碰撞就很不容易了吧？」

若使用多個 Hash 函式對應到 bit-vector 上，因為要每一個對應到的都是 1 才會符合， 只要有其中一個 Hash 函式對應到的位置內容不為 1，就一定不會存在，所以相對於原本的方法， 「誤報」的可能性自然會比較低。不過這並不代表不會發生碰撞，所以仍然有「誤報」的可能。

這個方法的好處是可以在不增加 bit-vector 的大小而且保持搜尋速度的情況下， 有效的減少了誤報的機會。

由於 Bloom Filter 其實就是使用 Hash 函式，所以搜尋的速度很快， 而且所佔的空間也很小(Hash 方法的特性)。不過這個方法雖然好，但還是有一些缺點， 其中最重要的就是不支援刪除，由於採用多個 Hash 函式的原因， 所以我們不敢隨便把一個 Hash 函式對應的位置從 1 改成 0， 因為這有可能會影響別的 Hash 函式。

很多地方都可以用到 Bloom Filter ，比如說 IP Iookup。使用的概念主要都是 「為了增加搜尋的速度，於是在搜尋的過程中另外添加一個篩選器，先過濾掉不可能的結果， 再做搜尋，這樣就可以增加搜尋的速度。」，如下圖：

另外還有很多不同的運用和延伸，這之後再研究吧。