下列针对布隆过滤器的描述错误的是(分布式布隆过滤器)

一、简介二、原理

布隆过滤器添加元素布隆过滤器查询元素 三、使用Google Guava的BloomFilter

添加依赖代码案例测试 当改变预估数时候对真实误判率的影响 应用场景

布隆过滤器（Bloom Filter），以空间换时间的算法。布隆过滤器由布隆在 1970 年提出。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。

优点 空间效率和查询时间缺点 有一定的误识别率和删除困难

假如有一个集合{x,y,z}三个元素，每个元素映射出一个hashcode，而这个hashcode的值通过算法会分成3个或者k个值。

将要添加的元素给 k 个哈希函数得到对应于位数组上的 k 个位置将这 k 个位置设为 1 布隆过滤器查询元素

将要查询的元素给 k 个哈希函数得到对应于位数组上的 k 个位置如果 k 个位置有一个为 0，则肯定不在集合中如果 k 个位置全部为 1，则可能在集合中 三、使用Google Guava的BloomFilter 添加依赖

    com.google.guava
    guava
    31.0.1-jre

具体创建代码

   public static  BloomFilter create(Funnel funnel, int expectedInsertions, double fpp) {
        return create(funnel, (long)expectedInsertions, fpp);
    }

Funnel funnel 存放Funnel对象 比如Funnels.stringFunnel(Charset.defaultCharset())或者Funnels.其他方法
int expectedInsertions 预估个数 比如100000000
double fpp 误判率 比如0.001

测试用例

import static java.nio.charset.Charset.*;


public class Te {

    private static int insertions = 10000000;

    @Test
    public void bloomFilter() throws InterruptedException {
        BloomFilter charSequenceBloomFilter = BloomFilter.create(Funnels.integerFunnel(), 1000, 0.999);
        BloomFilter bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charset.defaultCharset()), insertions, 0.001);

        Set sets = new HashSet(insertions);

        List lists = new ArrayList(insertions);

        for (int i = 0; i < insertions; i++) {
            String uid = UUID.randomUUID().toString();
            bloomFilter.put(uid);
            sets.add(uid);
            lists.add(uid);
        }

        int right = 0;
        int wrong = 0;

        for (int i = 0; i < 10000; i++) {
            String data = i % 100 == 0 ? lists.get(i / 100) : UUID.randomUUID().toString();
            if (bloomFilter.mightContain(data)) {
                if (sets.contains(data)) {
                    right++;
                    continue;
                }
                wrong++;
            }
        }

        NumberFormat percentFormat = NumberFormat.getPercentInstance();
        percentFormat.setMaximumFractionDigits(2);
        float percent = (float) wrong / 9900;
        float bingo = (float) (9900 - wrong) / 9900;

        System.out.println("在 " + insertions + " 条数据中，判断 100 实际存在的元素，布隆过滤器认为存在的数量为：" + right);
        System.out.println("在 " + insertions + " 条数据中，判断 9900 实际不存在的元素，布隆过滤器误认为存在的数量为：" + wrong);
        System.out.println("命中率为：" + percentFormat.format(bingo) + "，误判率为：" + percentFormat.format(percent));
    }

}

真实误判率为0.1%

当误判率设置为0.001时，改变预估数量，大概都在一个合理区间内。

反之，确定估计数量为1000000，改变误判率参数，所得出的结论也在一个合理区间。

利用布隆过滤器减少磁盘 IO 或者网络请求，因为一旦一个值必定不存在的话，我们可以不用进行后续昂贵的查询请求，比如以下场景：

1、大数据去重；

2、网页爬虫对 URL 的去重，避免爬取相同的 URL 地址；

3、反垃圾邮件，从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱；

4、缓存击穿，将已存在的缓存放到布隆中，当黑客访问不存在的缓存时迅速返回避免缓存及数据库挂掉。