布隆过滤器⽤于快速检测不存在数据，主要⽤位数组的结构来存储。其中为了保证布隆过滤器有适当的正确率通常会设置⼏个参数。 设：
k = hash函数个数，⽤于将⼀个数据通过不同hash函数计算为不同值，如“test” hash1-> 10,hash2-> 91, hash3->88等等，其中hash值即为位数组下标。如上⾯计算的三个值则位数组上坐标为10、91、88的位置上会被标记为1，其他位置还是0。 n = 数据量⼤⼩。如：现有⼀个100万⽂件的⽂件夹，我⼿中有⼀个⽂件不知道这个⽂件夹中是否有这个⽂件，如果没有就放进去，有的话我再另外处理。此时n则是100万
m = 位数组长度。如上上⾯经过hash计算的值是⼩于⼀个最⼤值的，这个最⼤值则是这个位数组的长度。
p = 布隆过滤器正确率。hash计算的值位数是有限的，当数据量⼤了之后必然存在多个值重复交叉的问题，例如有另外两个数据三个hash 函数算出的值分别是（11,10,88），（91,54,10），那如果这时再检测并没有存⼊的“test”她的hash值为（10,91,88）在位数组中是存在的。这时就会误报“test”已存在。那
基金频道么这个误报率就是p。这⾥也可以看出布隆过滤器并不适合检测数据是否存在，⽽适合检测数据⼀定不存在。
陈衍使⽤布隆过滤器我们⾃然想要误报率p不能太⾼，当然长度m也不能太⼤不然还不如直接⽤其他更准确的数据结构。
那么这些参数的关系是怎样的呢。这⾥直接给出公式：
，，可以看出hash函数个数只与精确度有关，⽽m与k值和数据量有关。
对地观测中心
显然k值我们只能取整数，那么对应的p值为多少呢，这⾥我给出⼏个常见值对应表，
其中k/ln2⽤系数r表⽰即
k p r
10.5 1.442695041
20.25 2.885390082
30.125 4.328085123
40.0625 5.770780164
50.031257.213475204
60.0156258.656170245
70.007812510.09886529
80.0039062511.54156033
羊毛纸90.00195312512.98425537
100.00097656314.42695041
我们可以看到当k取5时的误判率已经⼩于5%，此时的系数约等于7。也就是说，如果数据量为100万，那么位数组长度需要700万才能保证使⽤5个hash函数时误判率⼩于5%。700万位，约等于875kb。如果⼀个⽂件只有1k⼤⼩，总⼤⼩也将近1G了。通过布隆过滤器，只需要875k的内存⼤⼩便能快速判断某个⽂件是否在这个⽂件夹中，且准确率⾼达96.8%。
布隆过滤器在⼤量数据判断是否存在的场景⾮常有⽤，速度快，占⽤内存少。
订阅蜂
当然布隆过滤器最耗时可能在hash函数中。此时选择的hash函数也要考虑使⽤性能较⾼的hash函数才能使整体效率较⾼。当然hash函数的散列均匀度也影响误判概率。此⽂中的公式是默认所有hash函数计算的值是绝对均匀的。dx4
说了这么多废话，你肯定会问：能不能给⼒点啊⽼师！talk is cheap，show me the code.
好了，google.guava已经给你实现好了。BloomFilter，⽤静态⽅法create(int parm1，double param2)进⾏构建。第⼀个参数是你准备填充的数据总量，即⽂中的n。第⼆个参数是失败率，如你期望失败率为5%，则参数传0.05；当然，这是在java语境中的对象过滤。所以，理论上你把失败率设置为很低也不会太占⽤内存，⽐如0.00000000001。当然前提是你的总量不会太⼤。不过，第⼀个参数也限定了是个int⽽不是long。虽然组合起来可能会让布隆过滤器占⽤内存很⼤。但，⼀般的应⽤，你的失败率只要不设置的过分离谱，谁在乎呢。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议