在《什么是布隆过滤器（Bloom Filter）？》一文中，多次提到了误识别率（FPP，false positive probabilistic）。

那么误识别率到底是多大，应该如何计算呢？

假设布隆过滤器大小为m比特，存储了n个元素，使用k次散列函数来计算元素的存储位置。

添加1个元素，则任一比特为1的概率为：1/m，任一比特为0的概率：1-1/m；
添加1个元素，执行k次散列之后，则任一比特为0的概率：(1-1/m)^k，任一比特为1的概率：1-(1-1/m)^k；
如果添加n个元素，那么任一比特为0的概率：(1-1/m)^kn，任一比特为1的概率：1-(1-1/m)^kn；
如果将1个新的元素，添加到已存在n个元素的布隆过滤器中，则任一比特已经为1的概率与上面相同，概率为：1-(1-1/m)^kn。因此，k个比特都为1的概率为：(1-(1-1/m)^kn)^k，此即为新插入元素的误识别率。

当n值比较大时，(1-(1-1/m)^kn)^k约等于：(1-e^-kn/m)^k

其中，e是一个数学常数，是自然对数函数的底数。有时被称为欧拉数（Euler's number），以瑞士数学家欧拉命名。它是一个无限不循环小数，数值约为2.71828182846。

假定布隆过滤器大小m为16比特，k为8，存储元素n为1，那么误识别（假阳性）的概率是万分之五（5/10000）。

此时，m/n=16，事实上这表示1个元素使用16个比特的空间来存储。

因此，当k相同时，m/n为16/1、32/2、64/4等值时具有相同的误识别率。

将数值代入公式，计算一下万分之五的概率是怎么来的：

kn=8*1=8

kn/m=8/16=1/2

e的-1次方转换为倒数：1/e=0.36787944117

再计算1/e的1/2次方，即对0.36787944117进行开方，得到：0.60653065971144443045693327628786

计算括号内的值：1-0.60653065971144443045693327628786=0.39346934028855556954306672371214

最后再计算k次方：0.39346934028855556954306672371214的8次方=5.7449622219356465294987619912758e-4

计算得到的误识别率为 5.7449622219356465294987619912758e-4 ，即万分之五。

下面是来自pages.cs.wisc.edu/~cao/papers…的一个误识别率表，可以很方便的查询出在m、n和k分别取不同值时的误识别率。

m/n和k取不同的值时，布隆过滤器的误识别率.
m/n	k	k=1	k=2	k=3	k=4	k=5	k=6	k=7	k=8
2	1.39	0.393	0.400
3	2.08	0.283	0.237	0.253
4	2.77	0.221	0.155	0.147	0.160
5	3.46	0.181	0.109	0.092	0.092	0.101
6	4.16	0.154	0.0804	0.0609	0.0561	0.0578	0.0638
7	4.85	0.133	0.0618	0.0423	0.0359	0.0347	0.0364
8	5.55	0.118	0.0489	0.0306	0.024	0.0217	0.0216	0.0229
9	6.24	0.105	0.0397	0.0228	0.0166	0.0141	0.0133	0.0135	0.0145
10	6.93	0.0952	0.0329	0.0174	0.0118	0.00943	0.00844	0.00819	0.00846
11	7.62	0.0869	0.0276	0.0136	0.00864	0.0065	0.00552	0.00513	0.00509
12	8.32	0.08	0.0236	0.0108	0.00646	0.00459	0.00371	0.00329	0.00314
13	9.01	0.074	0.0203	0.00875	0.00492	0.00332	0.00255	0.00217	0.00199
14	9.7	0.0689	0.0177	0.00718	0.00381	0.00244	0.00179	0.00146	0.00129
15	10.4	0.0645	0.0156	0.00596	0.003	0.00183	0.00128	0.001	0.000852
16	11.1	0.0606	0.0138	0.005	0.00239	0.00139	0.000935	0.000702	0.000574
17	11.8	0.0571	0.0123	0.00423	0.00193	0.00107	0.000692	0.000499	0.000394
18	12.5	0.054	0.0111	0.00362	0.00158	0.000839	0.000519	0.00036	0.000275
19	13.2	0.0513	0.00998	0.00312	0.0013	0.000663	0.000394	0.000264	0.000194
20	13.9	0.0488	0.00906	0.0027	0.00108	0.00053	0.000303	0.000196	0.00014
21	14.6	0.0465	0.00825	0.00236	0.000905	0.000427	0.000236	0.000147	0.000101
22	15.2	0.0444	0.00755	0.00207	0.000764	0.000347	0.000185	0.000112	7.46e-05
23	15.9	0.0425	0.00694	0.00183	0.000649	0.000285	0.000147	8.56e-05	5.55e-05
24	16.6	0.0408	0.00639	0.00162	0.000555	0.000235	0.000117	6.63e-05	4.17e-05
25	17.3	0.0392	0.00591	0.00145	0.000478	0.000196	9.44e-05	5.18e-05	3.16e-05
26	18	0.0377	0.00548	0.00129	0.000413	0.000164	7.66e-05	4.08e-05	2.42e-05
27	18.7	0.0364	0.0051	0.00116	0.000359	0.000138	6.26e-05	3.24e-05	1.87e-05
28	19.4	0.0351	0.00475	0.00105	0.000314	0.000117	5.15e-05	2.59e-05	1.46e-05
29	20.1	0.0339	0.00444	0.000949	0.000276	9.96e-05	4.26e-05	2.09e-05	1.14e-05
30	20.8	0.0328	0.00416	0.000862	0.000243	8.53e-05	3.55e-05	1.69e-05	9.01e-06
31	21.5	0.0317	0.0039	0.000785	0.000215	7.33e-05	2.97e-05	1.38e-05	7.16e-06
32	22.2	0.0308	0.00367	0.000717	0.000191	6.33e-05	2.5e-05	1.13e-05	5.73e-06

参考

《数学之美》

pages.cs.wisc.edu/~cao/papers…

zh.wikipedia.org/zh-cn/E_(%E…

en.wikipedia.org/wiki/Bloom_…

关于我

公众号：二进制之路

教程：996geek.com

博客：binarylife.icu

布隆过滤器之误识别率FPP公式的推导

参考

关于我