Bloom Filter原理

布隆過濾器（Bloom Filter，簡稱BF）是用來檢測某個元素是否是大資料集合的成員的一個有效方法，具有很好的空間和時間效率。

BF是一個二進制向量資料結構，可以了解為有m個抽屜的桌子。

設計一個BF需要有3個功能部件：（1）有n個元素的集合M；（2）長度為m的位數組（BF結構）；（3）k個哈希函數。

初始狀态：位數組各位都為0，即每個抽屜都是空的。

實作過程：依次取集合M中的元素，例如a，計算hi(a)=x ，其中1<= i <=k，1<= x <=m，并将位數組的第x位設定為1.

                   可見：對每一個元素，都使用了k個哈希函數對其進行了計算，并将相應的抽屜都設定為1。

如何判斷：元素b是否在位數組中？對b，使用hi(b)=x ，其中1<= i <=k，并檢視第x個抽屜是否為1。

                  如果有一個抽屜不為1，即可知道b不在集合M中；反之，表明b在M中。

誤判：元素不在集合M中，但通過BF判斷其在M中。

漏判：如果元素在集合M中，則通過BF判斷其一定在M中。

注意：BF會産生誤判，但不會發生漏判。

産生誤判的原因：因為位數組中很多位都被設定成了1，使得通過哈希函數産生的數對應的位數都為1。

影響誤判的因素：（1）位數組長度，位數組越長，使得剩餘0的個數會越多，産生誤判的機率越小；

                                 （2）集合M的元素個數n，n越大，使得位數組各位産生1的機率增大，産生誤判的機率随之增大；

                                 （3）哈希函數的數量。