Bloom filter
Bloom filter 是一個概念很簡單又好用的東西，之前看過就想記錄一下
為何要用 Bloom filter
可以快速確認一個 key 是否存在一個資料集內，且不需花太多空間來儲存這些多餘的資訊。
Hash table 也可以做到快速查詢，但空間使用量就是會多不少
演算法
一個 Bloom filter 是一個長度為 m 的 bit 陣列，配上 k 個 hash function。每個 hash function 可以隨機的把 key 對應到 m 格陣列上。
加入資料
當要把一個 key 加入資料集時，就用 k 個 hash function 對這個 key 做計算，把對應的陣列位置設成 1
查找資料
當要確認一個 key 是否在資料集內時，也是用 k 個 hash function 對這個 key 做計算。
如果陣列對應的位置所有的值都是 1，這個 key 就有"可能"存在此資料集，就可以進行搜尋，因為之前加進來的 key 們也有機會把該 key 對應到的 k 個陣列位置設為 1。
如果其中某些位置是 0，則 key 完全不可能存在此資料集。
應用場景
Cassandra DB 就有使用到 Bloom filter。
Cassandra 用的是類似 log structured merge tree 的結構，內部會有多個樹，資料可能存在任何地方，要找一筆資料時如果每顆樹都要搜尋一定會慢，所以每顆樹都會配上一個 bloom filter 來加速查詢，決定要不要搜尋這顆樹。
結論
因為 Bloom filter 只會出現 false positive 的情況 (判斷資料存在卻不存在)，不會有 false negative (判斷資料不存在卻存在)，所以不會有正確性的問題。出現 false positive 時只是進去搜尋沒搜尋到而已。
要達到 1% 的 false positive rate 只需要大約 10 bits/element，真的是超級節省D
