误判率计算公式

假设原始的数集有n个，bit数组的长度为m，hash函数的个数为k：

（1）bit数组中某一位不被设为1的概率为：1 - 1/m

（2）k个hash过后生成k个点，此时不被设为1的概率为：(1 - 1/m)^k

（3）n个原始集合插入结束之后，此时不被设置为1的概率为: (1 - 1/m)^kn，反过来被设置为1的概率为1 - (1 - 1/m)^kn，这就是匹配到全部元素为1的误算率。

通过公式反推：我们可以简单的得出k，m，n这三者之间的关系：

k = m/n * ln2约等于0.7 * m/n

m：布隆过滤器的长度n：n个元素k：有k个hash函数p：误判的概率

计算误判率的公式：p = 1 - (1 - 1/m)^kn

同时还能得出以下结论：要保持P不变的话，比特数和元素的个数需要线性增长想要降低误判率的话，需要增大m或者减小n。

语音朗读：