布隆过滤器—guava-BloomFilter

应用场景：

• 字处理软件中，需要检查一个英语单词是否拼写正确
• 在 FBI，一个嫌疑人的名字是否已经在嫌疑名单上
• 在网络爬虫里，一个网址是否被访问过
• 邮箱垃圾邮件过滤功能
• 比特币网络

1. 　guava-BloomFilter

2. 分布式场景：　　自定义布隆过滤器　　hashcode + redis Getbit

原理：

布隆过滤器

缓存，cache，比如 redis、hashmap，是将数据存放在内存中。
cache 与 filter 有异曲同工之妙。两者为 互补 的关系。

原理：不同于 hashmap 将元素映射到某个具体链表上，filter 将一个元素 散射 到一个 二进制向量 中。

底层：使用一个很长的二进制向量和一个映射函数。

注意：检索一个元素，如果检索结果是元素不在集合中，那么肯定正确的（就表明不在）。如果检索结果是元素在集合中，那么有一定的概率是判断错了（也能不在集合中）

优点：空间效率和查询时间远超一般的算法

缺点：有一定的误识别率和删除困难

判断错误：B实际不存在，但是判断结果是存在：错误映射

特点：判断不存在时肯定是对的，判断存在时可能出错

如果判断 “真正存在” 呢？要去数据库进一步确认

Bloom Filter 使用场景：在前面过滤一次，过滤掉不存在的元素（不存在就是不存在），就不用去数据库查询了

但他也和 cache 是一样的，在后面必须跟一个真正的数据存储系统（DB、文件）

前边是预处理模块，后边的数据权威机构

Guava [BloomFilter] 简单使用

guava 依赖：

<dependency>    <groupId>com.google.guava</groupId>    <artifactId>guava</artifactId>    <version>19.0</version></dependency>

调整参数fpp：手动设置错误率为 0.0001

 // 要处理1亿个数据，用64MB大小的位图

BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charset.defaultCharset()),        size, 0.0001);

     //1%，有个概率问题，布隆越大，占用的空间越多，但是错误概率减小了        BloomFilter bloomFilter= BloomFilter.create(Funnels.stringFunnel(Charset.defaultCharset()),1000000,0.001);

测试程序：将 100w 个数据放入布隆结合，分别判断 100w 个在其中的元素的“不存在”概率 和 100w 个不存在其中的元素的 “存在”概率

@Testpublic void mmm() {    int size = 1000_000;　//默认fpp 0.03    BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charset.defaultCharset()), size);　／    for (int i = 0; i < size; i++) {        bloomFilter.put(i + "");    }                //判定存在的元素    for (int i = 0; i < size; i++) {        boolean exist = bloomFilter.mightContain(i + "");        if (!exist) {            //如果判定为不存在，那么一定不存在。            System.out.println("发现漏网之鱼！！！" + i);//该语句未执行        }    }    //判定不存在的元素    int mistake = 0;    for (int i = size; i < size * 2; i++) {        boolean exist = bloomFilter.mightContain(i + "");        if (exist) {            //如果判定为存在，那么可能不存在。            mistake++;            //System.out.println("哦吼~误判了！！！" + i);        }    }    System.out.println("误判率：" + (mistake * 1.0) / size);// 0.030094}

分布式自定义：　hashcode +redis

 // 自定义一个布隆过滤器    public static class MyBloomFilter {        // 定义位图的大小，一般需要定义为2的整次幂        private Integer cap;        public MyBloomFilter(Integer cap) {            this.cap = cap;        }        // 实现一个hash函数        public Long hashCode( String value, Integer seed ){            Long result = 0L;            for( int i = 0; i < value.length(); i++ ){                result = result * seed + value.charAt(i);            }            return result & (cap - 1);        }    }

将位图放入reids

Redis Getbit 命令用于对 key 所储存的字符串值，获取指定偏移量上的位(bit)。

jedis = new Jedis("localhost", 6379);myBloomFilter = new MyBloomFilter(1<<29);    // 要处理1亿个数据，用64MB大小的位图  // 1. 取当前的userId            Long userId = elements.iterator().next().getUserId();            // 2. 计算位图中的offset            Long offset = myBloomFilter.hashCode(userId.toString(), 61);            // 3. 用redis的getbit命令，判断对应位置的值            Boolean isExist = jedis.getbit(bitmapKey, offset);            if( !isExist ){                // 如果不存在，对应位图位置置1                jedis.setbit(bitmapKey, offset, true);                // 更新redis中保存的count值                Long uvCount = 0L;    // 初始count值                String uvCountString = jedis.hget(countHashName, countKey);                if( uvCountString != null && !"".equals(uvCountString) )                    uvCount = Long.valueOf(uvCountString);                jedis.hset(countHashName, countKey, String.valueOf(uvCount + 1));                out.collect(new PageViewCount("uv", windowEnd, uvCount + 1));            }