布隆过滤器

流程图

 一个请求经过了三个函数的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包链接