再谈BloomFilter设计

对于Bloom Filter而言，容量和错误率（False Positive Rate）已经由数学原理确定了。我们要关心的是其性能。Bloom Filter的性能其实就是其中使用的HASH算法的性能。在《选择一种优秀的HASH算法》一文中，我测试了一些著名的HASH算法。由于Bloom Filter每次插入或查询需要多个HASH值，最理想的做法就是计算一个长的HASH，然后把它切成等长的几个短HASH值。以速度和质量而言，最理想的就是MD5或SHA1了。

下面的表格是使用MD5或SHA1时Bloom Filter的特性。以第一行为例，解读为：当HASH长度为32bit时，占用内存512M，使用4个HASH，在错误率为6.25%时，容量为7.44亿个项目。使用MD5算法时，m乘以k的值不得大于128bit，而SHA1则是160bit。

MD5
m (bits)	mem (bytes)	k	f	n
32	536870912	4	6.25%	744268976
31	268435456	4	6.25%	372134488
30	134217728	4	6.25%	186067244
29	67108864	4	6.25%	93033622
28	33554432	4	6.25%	46516811
27	16777216	4	6.25%	23258405
26	8388608	4	6.25%	11629202
25	4194304	5	3.13%	4651681
24	2097152	5	3.13%	2325840
23	1048576	5	3.13%	1162920
22	524288	5	3.13%	581460
21	262144	6	1.56%	242275
20	131072	6	1.56%	121137
19	65536	6	1.56%	60568
18	32768	7	0.78%	25958
17	16384	7	0.78%	12979
16	8192	8	0.39%	5678
SHA1
m (bits)	mem (bytes)	k	f	n
32	536870912	5	3.13%	595415181
31	268435456	5	3.13%	297707590
30	134217728	5	3.13%	148853795
29	67108864	5	3.13%	74426897
28	33554432	5	3.13%	37213448
27	16777216	5	3.13%	18606724
26	8388608	6	1.56%	7752801
25	4194304	6	1.56%	3876400
24	2097152	6	1.56%	1938200
23	1048576	6	1.56%	969100
22	524288	7	0.78%	415328
21	262144	7	0.78%	207664
20	131072	8	0.39%	90853
19	65536	8	0.39%	45426
18	32768	8	0.39%	22713
17	16384	9	0.20%	10094
16	8192	10	0.10%	4542

通过对比，我发现内存使用量相同的情况下，MD5的错误率稍高，而容量也稍大一点。使用MD5算法要达到和SHA1相同的容量，其错误率会提高0.1%～0.2%。考虑到MD5的速度较快，我觉得这点错误率的上升也是可以接受的，因为实际使用中选择的Bloom Filter容量应该比应用所需容量大一些，而在此前提下，Bloom Filter的错误率是呈指数方式下降的。