布隆过滤器(bloom filter)及php和redis实现布隆过滤器(3)

(1−etk)ln(1−etk)=etklnetk

计算出来的k为ln2mn,约等于0.693mn,将k代入p(误判),我们可以得到概率和m、n之间的关系,最后的结果

(1/2)ln2mn,约等于0.6185m/n

以上我们就得出了最佳hash函数个数以及误判率与mn之前的关系了。

下表是m与n比值在k个hash函数下面的误判率

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

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:http://www.heiqu.com/1956.html