布隆过滤器 使用测试(Google Guava)_guava布隆过滤器使用

---

一、简介

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

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

二、原理

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

布隆过滤器添加元素

• 将要添加的元素给 k 个哈希函数
• 得到对应于位数组上的 k 个位置
• 将这 k 个位置设为 1

布隆过滤器查询元素

• 将要查询的元素给 k 个哈希函数
• 得到对应于位数组上的 k 个位置
• 如果 k 个位置有一个为 0，则肯定不在集合中
• 如果 k 个位置全部为 1，则可能在集合中

三、使用Google Guava的BloomFilter

添加依赖

<!-- https://mvnrepository.com/artifact/com.google.guava/guava -->
<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>31.0.1-jre</version>
</dependency>
1
2
3
4
5
6

代码案例

具体创建代码

   public static <T> BloomFilter<T> create(Funnel<? super T> funnel, int expectedInsertions, double fpp) {
        return create(funnel, (long)expectedInsertions, fpp);
    }
1
2
3

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

测试用例

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

/**
 * @author JM
 */
public class Te {

    private static int insertions = 10000000;

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

        Set<String> sets = new HashSet<String>(insertions);

        List<String> lists = new ArrayList<String>(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));
    }

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

测试 当改变预估数时候对真实误判率的影响

真实误判率为0.1%

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

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

应用场景

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

1、大数据去重；

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

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

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