布隆過濾器（Bloom Filter）

布隆過濾器是由巴頓.布隆於一九七零年提出的。它實際上是一個很長的二進位向量和一系列隨機映射函數。我們通過垃圾郵件地址過濾的例子來說明其工作原理。

假定我們存儲一億個垃圾電子郵件地址，我們先建立一個十六億二進位（比特），即兩億位元組的向量，然後將這十六億個二進位全部設置為零。

對於每一個電子郵件地址 X，我們用八個不同的隨機數產生器（F1,F2, ...,F8） 產生八個信息指紋（f1, f2, ..., f8）。

再用一個隨機數產生器 G 把這八個信息指紋映射到 1 到十六億中的八個自然數 g1, g2, ...,g8。現在我們把這八個位置的二進位全部設置為一。

當我們對這一億個 email 地址都進行這樣的處理后。一個針對這些 email 地址的布隆過濾器就建成了。（見上圖）

它只需要哈希表 1/8 到 1/4 的大小就能解決同樣的問題。