江苏龙网

  1. 主页 > 生活百科 > >

布隆过滤器究竟是什么，这一篇给讲的明明白白的( 二 )

布隆过滤器


布隆过滤器究竟是什么，这一篇给讲的明明白白的

文章插图
 
大家来看下这个图，我们看集合里面3个元素，现在我们要存了，比如说a，经过f1(a)，f2(a)，f3(a)经过三个哈希函数的计算，在相应的位置上存入1，元素b，c也是通过这三个函数计算放入相应的位置 。当取的时候，元素a通过f1(a)函数计算，发现这个位置上是1，没问题，第二个位置也是1，第三个位置上也是 1，这时候我们说这个a在布隆过滤器中是存在的，没毛病，同理我们看下面的这个d，通过三次计算发现得到的结果也都是1，那么我们能说d在布隆过滤器中是存在的吗，显然是不行的，我们仔细看d得到的三个1其实是f1(a)，f1(b)，f2(c)存进去的，并不是d自己存进去的，这个还是哈希碰撞导致的，我们把这种本来不存在布隆过滤器中的元素误判为存在的情况叫做假阳性（False Positive Probability，FPP） 。
我们再来看另一个元素，e 元素 。我们要判断它在容器里面是否存在，一样地要用这三个函数去计算 。第一个位置是 1，第二个位置是 1，第三个位置是 0 。那么e元素能不能判断是否在布隆过滤器中？答案是肯定的，e一定不存在 。你想啊，如果e存在的话，他存进去的时候这三个位置都置为1，现在查出来有一个位置是0，证明他没存进去啊 。。通过上面这张图加说明，我们得出两个重要的结论
从容器的角度来说：
如果布隆过滤器判断元素在集合中存在，不一定存在
如果布隆过滤器判断不存在，一定不存在
从元素的角度来说：
【布隆过滤器究竟是什么，这一篇给讲的明明白白的】如果元素实际存在，布隆过滤器一定判断存在
如果元素实际不存在，布隆过滤器可能判断存在
小伙们请牢记
Guava实现布隆过滤器JAVA为什么写的人多，基数大，因为是开源的，拥抱开源，框架多，轮子多，而且一个功能的轮子还不止一个，光序列化就有fastjson，jackson，gson，随你挑任你选，那布隆过滤器的轮子就是google提供的guava，我们用代码来看一下使用方法
首先引入我们的架包
      <dependency>          <groupId>com.google.guava</groupId>          <artifactId>guava</artifactId>          <version>21.0</version>      </dependency>这里先往布隆过滤器里面存放100万个元素，然后分别测试100个存在的元素和9900个不存在的元素他们的正确率和误判率
    //插入多少数据    private static final int insertions = 1000000;    //期望的误判率    private static double fpp = 0.02;    public static void main(String[] args) {        //初始化一个存储string数据的布隆过滤器,默认误判率是0.03        BloomFilter<String> bf = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), insertions, fpp);        //用于存放所有实际存在的key，用于是否存在        Set<String> sets = new HashSet<String>(insertions);        //用于存放所有实际存在的key，用于取出        List<String> lists = new ArrayList<String>(insertions);        //插入随机字符串        for (int i = 0; i < insertions; i++) {            String uuid = UUID.randomUUID().toString();            bf.put(uuid);            sets.add(uuid);            lists.add(uuid);        }        int rightNum = 0;        int wrongNum = 0;        for (int i = 0; i < 10000; i++) {            // 0-10000之间，可以被100整除的数有100个（100的倍数）            String data = i % 100 == 0 ? lists.get(i / 100) : UUID.randomUUID().toString();            //这里用了might,看上去不是很自信，所以如果布隆过滤器判断存在了,我们还要去sets中实锤            if (bf.mightContain(data)) {                if (sets.contains(data)) {                    rightNum++;                    continue;                }                wrongNum++;            }        }        BigDecimal percent = new BigDecimal(wrongNum).divide(new BigDecimal(9900), 2, RoundingMode.HALF_UP);        BigDecimal bingo = new BigDecimal(9900 - wrongNum).divide(new BigDecimal(9900), 2, RoundingMode.HALF_UP);        System.out.println("在100W个元素中，判断100个实际存在的元素，布隆过滤器认为存在的：" + rightNum);        System.out.println("在100W个元素中，判断9900个实际不存在的元素，误认为存在的：" + wrongNum + "，命中率：" + bingo + "，误判率：" + percent);    }


推荐阅读


上一篇：玫瑰花茶次喝几朵合适,玫瑰花茶怎么泡

下一篇：黑枸杞的生长环境,枸杞菊花茶用量