bloom filter

如果檢測結果為是，該元素不一定在集合中；但如果檢測結果為否，該元素一定不在集合中。因此Bloom filter具有100%的召回率。這樣每個檢測請求返回有“在集合內（可能錯誤）”和“不在集合內（絕對不在集合內）”兩種情況，可見 Bloom filter 是犧牲了正確率和時間以節省空間。

如需要判斷一個元素是不是在一個集合中，我們通常做法是把所有元素保存下來，然後通過比較知道它是不是在集合內，鏈表、樹都是基於這種思路，當集合內元素個數的變大，我們需要的空間和時間都線性變大，檢索速度也越來越慢。 Bloom filter 採用的是哈希函數的方法，將一個元素映射到一個 m 長度的陣列上的一個點，當這個點是 1 時，那麼這個元素在集合內，反之則不在集合內。這個方法的缺點就是當檢測的元素很多的時候可能有衝突，解決方法就是使用 k 個哈希 函數對應 k 個點，如果所有點都是 1 的話，那麼元素在集合內，如果有 0 的話，元素則不在集合內。

Bloom filter 優點就是它的插入和查詢時間都是常數，另外它查詢元素卻不保存元素本身，具有良好的安全性。它的缺點也是顯而易見的，當插入的元素越多，錯判“在集合內”的概率就越大了，另外 Bloom filter 也不能刪除一個元素，因為多個元素哈希的結果可能在 Bloom filter 結構中佔用的是同一個位，如果刪除了一個比特位，可能會影響多個元素的檢測。

下面是一個簡單的 Bloom filter 結構，開始時集合內沒有元素

當來了一個元素 a，進行判斷，這裏哈希函數有兩個，計算出對應的比特位上為 0 ，即是 a 不在集合內，將 a 添加進去：

之後的元素，要判斷是不是在集合內，也是同 a 一樣的方法，只有對元素哈希後對應位置上都是 1 才認為這個元素在集合內（雖然這樣可能會誤判）：

隨着元素的插入，Bloom filter 中修改的值變多，出現誤判的幾率也隨之變大，當新來一個元素時，滿足其在集合內的條件，即所有對應位都是 1 ，這樣就可能有兩種情況，一是這個元素就在集合內，沒有發生誤判；還有一種情況就是發生誤判，出現了哈希碰撞，這個元素本不在集合內。