布隆过滤器误判率数学推导

预估要存的数据量为：n

期望的误判率为：P

Bit数组的大小为：m

Hash函数的个数为：k

推导过程：

1）对某一特定bit位在一个元素由某特定hash函数插入时没有被置为1的概率为：

2）则k个hash函数都没有将其置为1概率为：

3）如果插入了n个元素，都未将其置为1的概率为：

4）反过来，则此位被置为1的概率为：

5）一个不在集合中的元素，被误判在集合中的概率：

6）根据自然常数公式： lim(1+1/x)^x, x→∞，得出：

7）k为何值时可以使得误判率最低。设误判率为k的函数：

8）设：

9）则简化为：

10）两边取对数：

11）两边对k求导：

12）下面求最值：

则误判率最低时，得出k值：

13）把k代入误判率公式，得出：

14）把k代入误判率公式，得出m值：