布隆过滤器

流程图

 一个请求经过了三个函数的Hash算法，分别在数组中计算出三个值，存放在布隆过滤器里面，后续请求经过Hash算法算出，只要有一个不命中，就无效。

布隆过滤器不适合删除数据，假如你好和hello经过哈希函数算出相等，那么下标为2的位置，就存了两个数据，当删除请求来的时候，就无法正确的进行删除 

基于谷歌Guava测试代码

package com.bloomFilter;import com.google.common.hash.Funnels;public class BloomFilterTest { private static int SIZE = 1000000; private static double FPP = 0.03; private static com.google.common.hash.BloomFilter bloomFilter = com.google.common.hash.BloomFilter.create(Funnels.integerFunnel(), SIZE, FPP); private static int total = 1000000; public static void main(String[] args) { for (int i = 0; i < total; i++) { bloomFilter.put(i); } int counts = 0; for (int i = total; i < total + 100000; i++) { if (bloomFilter.mightContain(i)) { counts++; } } System.out.println("被误判了：" + counts + " 次！"); }}

误判率随着你的预期大小，和你输入的误判率有关，但是这并不意味的你的误判率可以无限的小，因为缩小误判率是牺牲hash函数的计算时间而反正增加的，简而言之：误判率越小，hash函数越多，进源码看一看：

 此时是一百万预期大小，和误判率为0.03的数据，下面看一看0.01误判率

下面看下对比图 

 上图对比下图，Hash函数，比特数量都比下图少。当误判率极小时，查询效率会非常低，要机型大量的Hash函数计算，对比。

附：谷歌Guava.jar包链接