预估要存的数据量为: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值: