前幾天看到了科技報橘的這篇文章「想當資深工程師？你需要熟悉這 3 種資料結構」，看完之後覺得Bloom Filter這個結構相當神奇，不僅設計得巧妙、也確實可以在特定情況下非常快速的過濾資料O(1)、同時使用固定的空間O(1)。因此，查了一些資料後，便用python做了簡單的實作及測試。
Bloom Filter 介紹
總歸來說，Bloom Filter是利用雜湊函式（Hash function）以及一連串Boolean陣列來實現的結構。資料被加入Filter時，先經過hash function得到一組數字，再mod陣列長度後將該位置設定成True，因此可以確保同一筆資料再度經過一樣的hash function，會得到同一個位置。也就是說，將資料經過指定的這些hash functions，如果每次指到的位置都是True，則可以推定他有極高的機率是我們需要的資料，但也會有非常少數「運氣好」的資料通過測試。
因此，Bloom Filter大概有以下幾個特性：
- 插入資料的時間是O(1)，即是運行固定數量hash functions的時間，但須確保hash function的運算時間也是O(1)。
- 需要的資料保證不會被誤判，但不需要的資料有一定機會被誤判（即為Fail negative, Fail to detect something.）。但誤判的機率可以用陣列長度以及hash function數量來控制。
- 使用的空間固定，而且對比資料量來說算是滿小的。
因此Bloom Filter的使用情境應該是在資料量極大、可以接受部份不需要資料被誤判的情況下，換取相當的時間與空間。上面的文章就提到了Gmail用來判定垃圾信件，或者我在另一篇文章看到的，交友軟體用來避免配對到已經看過的對象。
而我也有讀到另一個資料結構Counting Filter，算是Bloom Filter的改良版。由於Bloom Filter的陣列中只有True和False，因此我們無法在Filter中移除某一個資料，而Counting Filter就是讓陣列記住被設成True的次數，因此就可以移除一筆特定資料，但使用的空間就會增加。
Python實作與測試
在init的階段呢，可以設定陣列的大小以及hash functions的數量（最多五個），hash function則是使用python內建的hashlib。
而add_data與is_exist方法基本上是相當類似的，要注意的是需要將輸入的string編成utf-8。而hash function的結果要使用hexdigest()方法取得。
test的方法主要是要測試fail negative的比例，我把理論值直接使用True在陣列中的比例的hash次數次方，而實驗值就是一百萬筆測資的結果，測試多次發現誤差相當的小。
There are 258 True in the 1000 bit.
With 3 hash functions, calculated false negative rate is 1.71735%.
In 1000000 test cases, the false negative rate is 1.72330%.
This test takes 12.74s完整的程式碼我放在我的Github上。
