# Bloom Filter 結構

布隆過濾器（Bloom Filter），1970 年由 Burton Howard Bloom 在論文《Space/Time Trade-offs in Hash Coding with Allowable Errors》提出。布隆過濾器是一種基於 Hash 的高效查找結構，能夠快速（常數時間內）回答“某個元素是否在一個集合內”的問題。

該結構因為其高效性，被大量應用到網絡和安全領域，例如信息檢索（BigTable 和 HBase）、垃圾郵件規則、註冊管理等。

## 基於 Hash 的快速查找

在布隆過濾器之前，先來看基於 Hash 的快速查找算法。在前面的講解中，我們提到，Hash 可以將任意內容映射到一個固定長度的字符串，而且不同內容映射到相同串的概率很低。因此，這就構成了一個很好的“內容 -> 索引”的生成關係。

試想，如果給定一個內容和存儲數組，通過構造 Hash 函數，讓映射後的 Hash 值總不超過數組的大小，則可以實現快速的基於內容的查找。例如，內容 “hello world” 的 Hash 值如果是 “100”，則存放到數組的第 100 個單元上去。如果需要快速查找任意內容，如 “hello world” 字符串是否在存儲系統中，只需要將其在常數時間內計算 Hash 值，並用 Hash 值查看系統中對應元素即可。該系統“完美地”實現了常數時間內的查找。

然而，令人遺憾的是，當映射後的值限制在一定範圍（如總數組的大小）內時，會發現 Hash 衝突的概率會變高，而且範圍越小，衝突概率越大。很多時候，存儲系統的大小又不能無限擴展，這就造成算法效率的下降。為了提高空間利用率，後來人們基於 Hash 算法的思想設計出了布隆過濾器結構。

## 更高效的布隆過濾器

![布隆過濾器](https://2764190444-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LTVpKVB_-0AGEl1PbRN%2F-LTVq2pGzV7aRkCYNbvV%2F-LTVq9q7fJrdO9MsVpkL%2Fbloom_filter.png?generation=1544591820280641\&alt=media)

布隆過濾器採用了多個 Hash 函數來提高空間利用率。

對同一個給定輸入來說，多個 Hash 函數計算出多個地址，分別在位串的這些地址上標記為 1。進行查找時，進行同樣的計算過程，並查看對應元素，如果都為 1，則說明較大概率是存在該輸入。

布隆過濾器相對單個 Hash 算法查找，大大提高了空間利用率，可以使用較少的空間來表示較大集合的存在關係。

實際上，無論是 Hash，還是布隆過濾器，基本思想是一致的，都是基於內容的編址。Hash 函數存在衝突，布隆過濾器也存在衝突。這就造成了兩種方法都存在著誤報（False Positive）的情況，但絕對不會漏報（False Negative）。

布隆過濾器在應用中誤報率往往很低，例如，在使用 7 個不同 Hash 函數的情況下，記錄 100 萬個數據，採用 2 MB 大小的位串，整體的誤判率將低於 1%。而傳統的 Hash 查找算法的誤報率將接近 10%。