布隆過濾器以少數錯誤答案換取極小的記憶體佔用

當一組項目數量龐大時，儲存每一個鍵是不可能的，但你仍需要知道某個項目是否在其中。布隆的例子是一本 50 萬字的字典，其中只有 10% 的字使用昂貴的連字規則：合理的檢查方式是避免一次磁碟存取，但字典太大，無法在可用記憶體中以無錯誤雜湊處理。

布隆過濾器以位元陣列和數個雜湊函數解決此問題。加入項目時會設定這些位置上的位元，測試時則詢問它們是否全部被設定。若任一為零，該項目必定不存在，因此不會有偽陰性；若全部被設定，該項目可能在集合中，也可能只是與其他項目發生碰撞，產生偽陽性。

由於錯誤是單向且可調整的，此結構得以保持精簡，同時仍能消除大多數不必要的磁碟讀取。雜湊區僅需無錯誤雜湊所需大小的 18%，即可消除 87% 的磁碟存取，而每元素少於十個位元即可達到約 1% 的偽陽性率。

讓位元陣列說「也許」，絕不誤說「不在」

當代價僅是額外一次檢查時，偽陽性是可接受的，但偽「不在」會遺失資料。

搭配數個雜湊函數的位元陣列，以每元素幾個位元儲存成員資格。

它消除了大多數昂貴的磁碟或網路查詢，而無需儲存實際的集合。

若可接受小機率回答「是」但不可接受偽「否」，就刻意接受單向錯誤；容許少數偽陽性往往是將龐大集合放入記憶體的唯一方法。

布隆過濾器遍及資料庫、快取、拼字檢查器和網路路由，用以避免昂貴的查詢，並出現在從 PostgreSQL 和 Apache Cassandra 到 Chromium 及大規模快取的系統中；以單向錯誤換取空間的底層技巧，如今已是電腦系統中的標準基本元件。