Bloom Filter的關鍵公式

Bloom Filter有以下參數：

• m bit數組的寬度（bit數）
• n 加入其中的key的數量
• k 使用的hash函數的個數
• f False Positive的比率

(1−(1−1m)kn)k≈(1−e−knm)k

給定 m、n ，使 f 最小化k

k=mnln2≈9m13n≈0.7mn

此時的 f 為

(12)2≈0.6185mn

由此給定 f ，

n=mln(0.6185)lnf

用 k 個hash函數實作，

k=−lnfln2

k 取整數，使用下面公式得到f

f=(1−e−kmn)k