直覺的說，bloom算法類似一個hash set，用來判斷某個元素（key）是否在某個集合中。
和一般的hash set不同的是，這個算法無需存儲key的值，對于每個key，隻需要k個比特位，每個存儲一個标志，用來判斷key是否在集合中。
算法：
1. 首先需要k個hash函數，每個函數可以把key散列成為1個整數
2. 初始化時，需要一個長度為n比特的數組，每個比特位初始化為0
3. 某個key加入集合時，用k個hash函數計算出k個散列值，并把數組中對應的比特位置為1
4. 判斷某個key是否在集合時，用k個hash函數計算出k個散列值，并查詢數組中對應的比特位，如果所有的比特位都是1，認為在集合中。
優點：不需要存儲key，節省空間
缺點：
1. 算法判斷key在集合中時，有一定的機率key其實不在集合中
2. 無法删除
典型的應用場景：
某些存儲系統的設計中，會存在空查詢缺陷：當查詢一個不存在的key時，需要通路慢裝置，導緻效率低下。
比如一個前端頁面的緩存系統，可能這樣設計：先查詢某個頁面在本地是否存在，如果存在就直接傳回，如果不存在，就從後端擷取。但是當頻繁從緩存系統查詢一個頁面時，緩存系統将會頻繁請求後端，把壓力導入後端。
這是隻要增加一個bloom算法的服務，後端插入一個key時，在這個服務中設定一次
需要查詢後端時，先判斷key在後端是否存在，這樣就能避免後端的壓力。
布隆過濾器［1］（Bloom Filter）是由布隆（Burton Howard Bloom）在1970年提出的。它實際上是由一個很長的二進制向量和一系列随機映射函數組成，布隆過濾器可以用于檢索一個元素是否在一個集合中。它的優點是空間效率和查詢時間都遠遠超過一般的算法，缺點是有一定的誤識别率（假正例False positives，即Bloom Filter報告某一進制素存在于某集合中，但是實際上該元素并不在集合中）和删除困難，但是沒有識别錯誤的情形（即假反例False negatives，如果某個元素确實沒有在該集合中，那麼Bloom Filter 是不會報告該元素存在于集合中的，是以不會漏報）。
在日常生活中，包括在設計計算機軟體時，我們經常要判斷一個元素是否在一個集合中。比如在字處理軟體中，需要檢查一個英語單詞是否拼寫正确（也就是要判斷 它是否在已知的字典中）；在 FBI，一個嫌疑人的名字是否已經在嫌疑名單上；在網絡爬蟲裡，一個網址是否被通路過等等。最直接的方法就是将集合中全部的元素存在計算機中，遇到一個新 元素時，将它和集合中的元素直接比較即可。一般來講，計算機中的集合是用哈希表（hash table）來存儲的。它的好處是快速準确，缺點是費存儲空間。當集合比較小時，這個問題不顯著，但是當集合巨大時，哈希表存儲效率低的問題就顯現出來 了。比如說，一個象 Yahoo,Hotmail 和 Gmai 那樣的公衆電子郵件（email）提供商，總是需要過濾來自發送垃圾郵件的人（spamer）的垃圾郵件。一個辦法就是記錄下那些發垃圾郵件的 email 位址。由于那些發送者不停地在注冊新的位址，全世界少說也有幾十億個發垃圾郵件的位址，将他們都存起來則需要大量的網絡伺服器。如果用哈希表，每存儲一億 個 email 位址， 就需要 1.6GB 的記憶體（用哈希表實作的具體辦法是将每一個 email 位址對應成一個八位元組的資訊指紋（詳見：googlechinablog.com/2006/08/blog-post.html）， 然後将這些資訊指紋存入哈希表，由于哈希表的存儲效率一般隻有 50%，是以一個 email 位址需要占用十六個位元組。一億個位址大約要 1.6GB， 即十六億位元組的記憶體）。是以存貯幾十億個郵件位址可能需要上百 GB 的記憶體。除非是超級計算機，一般伺服器是無法存儲的［2］。（該段引用谷歌數學之美：http://www.google.com.hk/ggblog/googlechinablog/2007/07/bloom-filter_7469.html）
基本概念
如果想判斷一個元素是不是在一個集合裡，一般想到的是将所有元素儲存起來，然後通過比較确定。連結清單，樹等等資料結構都是這種思路. 但是随着集合中元素的增加，我們需要的存儲空間越來越大，檢索速度也越來越慢。不過世界上還有一種叫作散清單（又叫哈希表，Hash table）的資料結構。它可以通過一個Hash函數将一個元素映射成一個位陣列（Bit Array）中的一個點。這樣一來，我們隻要看看這個點是不是 1 就知道可以集合中有沒有它了。這就是布隆過濾器的基本思想。
Hash面臨的問題就是沖突。假設 Hash 函數是良好的，如果我們的位陣列長度為 m 個點，那麼如果我們想将沖突率降低到例如 1%, 這個散清單就隻能容納 m/100 個元素。顯然這就不叫空間有效了（Space-efficient）。解決方法也簡單，就是使用多個 Hash，如果它們有一個說元素不在集合中，那肯定就不在。如果它們都說在，雖然也有一定可能性它們在說謊，不過直覺上判斷這種事情的機率是比較低的。
優點
相比于其它的資料結構，布隆過濾器在空間和時間方面都有巨大的優勢。布隆過濾器存儲空間和插入/查詢時間都是常數。另外, Hash 函數互相之間沒有關系，友善由硬體并行實作。布隆過濾器不需要存儲元素本身，在某些對保密要求非常嚴格的場合有優勢。
布隆過濾器可以表示全集，其它任何資料結構都不能；
k 和 m 相同，使用同一組 Hash 函數的兩個布隆過濾器的交并差運算可以使用位操作進行。
缺點
但是布隆過濾器的缺點和優點一樣明顯。誤算率（False Positive）是其中之一。随着存入的元素數量增加，誤算率随之增加。但是如果元素數量太少，則使用散清單足矣。
另外，一般情況下不能從布隆過濾器中删除元素. 我們很容易想到把位列陣變成整數數組，每插入一個元素相應的計數器加1, 這樣删除元素時将計數器減掉就可以了。然而要保證安全的删除元素并非如此簡單。首先我們必須保證删除的元素的确在布隆過濾器裡面. 這一點單憑這個過濾器是無法保證的。另外計數器回繞也會造成問題。
False positives 機率推導
假設 Hash 函數以等機率條件選擇并設定 Bit Array 中的某一位，m 是該位數組的大小，k 是 Hash 函數的個數，那麼位數組中某一特定的位在進行元素插入時的 Hash 操作中沒有被置位的機率是：
那麼在所有 k 次 Hash 操作後該位都沒有被置 "1" 的機率是：
如果我們插入了 n 個元素，那麼某一位仍然為 "0" 的機率是：
因而該位為 "1"的機率是：
現在檢測某一進制素是否在該集合中。标明某個元素是否在集合中所需的 k 個位置都按照如上的方法設定為 "1"，但是該方法可能會使算法錯誤的認為某一原本不在集合中的元素卻被檢測為在該集合中（False Positives），該機率由以下公式确定：
其實上述結果是在假定由每個 Hash 計算出需要設定的位（bit） 的位置是互相獨立為前提計算出來的，不難看出，随着 m （位數組大小）的增加，假正例（False Positives）的機率會下降，同時随着插入元素個數 n 的增加，False Positives的機率又會上升，對于給定的m，n，如何選擇Hash函數個數 k 由以下公式确定：
此時False Positives的機率為：
而對于給定的False Positives機率 p，如何選擇最優的位數組大小 m 呢，
上式表明，位數組的大小最好與插入元素的個數成線性關系，對于給定的 m，n，k，假正例機率最大為：
下圖是布隆過濾器假正例機率 p 與位數組大小 m 和集合中插入元素個數 n 的關系圖，假定 Hash 函數個數選取最優數目：
Bloom Filter 用例
Google 著名的分布式資料庫 Bigtable 使用了布隆過濾器來查找不存在的行或列，以減少磁盤查找的IO次數［3］。
Squid 網頁代理緩存伺服器在 cache digests 中使用了也布隆過濾器［4］。
Venti 文檔存儲系統也采用布隆過濾器來檢測先前存儲的資料［5］。
SPIN 模型檢測器也使用布隆過濾器在大規模驗證問題時跟蹤可達狀态空間［6］。
Google Chrome浏覽器使用了布隆過濾器加速安全浏覽服務［7］。
在很多Key-Value系統中也使用了布隆過濾器來加快查詢過程，如 Hbase，Accumulo，Leveldb，一般而言，Value 儲存在磁盤中，通路磁盤需要花費大量時間，然而使用布隆過濾器可以快速判斷某個Key對應的Value是否存在，是以可以避免很多不必要的磁盤IO操作，隻是引入布隆過濾器會帶來一定的記憶體消耗，下圖是在Key-Value系統中布隆過濾器的典型使用：
布隆過濾器相關擴充
Counting filters
基本的布隆過濾器不支援删除（Deletion）操作，但是 Counting filters 提供了一種可以不用重新建構布隆過濾器但卻支援元素删除操作的方法。在Counting filters中原來的位數組中的每一位由 bit 擴充為 n-bit 計數器，實際上，基本的布隆過濾器可以看作是隻有一位的計數器的Counting filters。原來的插入操作也被擴充為把 n-bit 的位計數器加1，查找操作即檢查位數組非零即可，而删除操作定義為把位數組的相應位減1，但是該方法也有位的算術溢出問題，即某一位在多次删除操作後可能變成負值，是以位數組大小 m 需要充分大。另外一個問題是Counting filters不具備伸縮性，由于Counting filters不能擴充，是以需要儲存的最大的元素個數需要提前知道。否則一旦插入的元素個數超過了位數組的容量，false positive的發生機率将會急劇增加。當然也有人提出了一種基于 D-left Hash 方法實作支援删除操作的布隆過濾器，同時空間效率也比Counting filters高。
Data synchronization
Byers等人提出了使用布隆過濾器近似資料同步［9］。
Bloomier filters
Chazelle 等人提出了一個通用的布隆過濾器，該布隆過濾器可以将某一值與每個已經插入的元素關聯起來，并實作了一個關聯數組Map［10］。與普通的布隆過濾器一樣，Chazelle實作的布隆過濾器也可以達到較低的空間消耗，但同時也會産生false positive，不過，在Bloomier filter中，某 key 如果不在 map 中，false positive在會傳回時會被定義出的。該Map 結構不會傳回與 key 相關的在 map 中的錯誤的值。
Compact approximators［11］
Stable Bloom filters［12］
Scalable Bloom filters［13］
Attenuated Bloom filters［14］
C#實作布隆過濾器
public class BloomFilter
{
public BitArray _BloomArray;
public Int64 BloomArryLength { get; }
public Int64 DataArrayLeng { get; }
public Int64 BitIndexCount { get; }
/// <summary>
/// 初始化
/// </summary>
/// <param name="BloomArryLength">布隆數組的大小</param>
/// <param name="DataArrayLeng">資料的長度</param>
/// <param name="bitIndexCount">hash數</param>
public BloomFilter(int BloomArryLength,int DataArrayLeng,int bitIndexCount)
{
_BloomArray = new BitArray(BloomArryLength);
this.BloomArryLength = BloomArryLength;
this.DataArrayLeng = DataArrayLeng;
this.BitIndexCount = bitIndexCount;
}
public void Add(string str)
{
var hashCode = GetHashCode(str);
Random random = new Random(hashCode);
for (int i = 0; i < BitIndexCount; i++)
{
var c = random.Next((int)(this.BloomArryLength - 1));
_BloomArray[c] = true;
}
}
public bool isExist(string str)
{
var hashCode = GetHashCode(str);
Random random = new Random(hashCode);
for (int i = 0; i < BitIndexCount; i++)
{
if(!_BloomArray[random.Next((int)(this.BloomArryLength - 1))])
{
return false;
}
}
return true;
}
public int GetHashCode(object value)
{
return value.GetHashCode();
}
public double getFalsePositiveProbability()
{
// (1 - e^(-k * n / m)) ^ k
return Math.Pow((1 - Math.Exp(-BitIndexCount * (double)DataArrayLeng / BloomArryLength)),
BitIndexCount);
}
}
static void Main(string[] args)
{
Bloom_Filter.BloomFilter bloom = new Bloom_Filter.BloomFilter(200000000, 50000000, 3);//五千萬條資料
for (int i = 0; i < bloom.DataArrayLeng; i++)//五千萬條資料
{
bloom.Add(i.ToString());
}
do
{
var c = Console.ReadLine();
if (c == "e")
break;
Stopwatch sw = new Stopwatch();
sw.Start();
var temp=bloom.isExist(c);
sw.Stop();
Console.WriteLine($"查找:{c}\n結果:{temp}\n總耗時:{sw.ElapsedTicks}\n錯誤機率:{bloom.getFalsePositiveProbability()}");
} while (true);
} 結果：使用記憶體27MB，查找結果一般在100毫秒以内。
-----------------------------------------------------------------
- 我做的小程式們
- 【推薦】Web版短信管理平台源碼
- WinForm版短信管理平台源碼
- 移動短信程式源碼Win服務版(CMPP3.0/CMPP2.0協定)
- 移動物聯網卡短信源碼(CMPP3.0協定，支援MsSql/MySql資料庫)
- C#實作聯通短信Sgip協定程式源碼
- C#實作電信短信SMGP協定程式源碼
- C#實作移動短信CMPP服務端程式源碼
- 小y的QQ：28657321 （歡迎交流）