布隆过滤器Java指南

布隆过滤器

我们先看看度娘的定义：布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。

通俗的来讲，布隆过滤器可以用于检索一个元素是否存在于一个集合中，例如：001 00 00 000 ，下标index从0开始计数， index为2的位置值等于1，即代表着index=2 说映射的元素是存在于集合中的。

布隆过滤器用途

• 元素存在性校验
• 黑名单建设
• 大量url去重

例如我们可以利用布隆过滤器来防止缓存击穿，将目标数据集中的元素映射到Bitset 中，完成元素到点的转换，当待查找元素映射的点在BitSet中存在时，我们可以过滤该元素。

布隆过滤器java简单实现

public class BloomFilter {

    private final int size;

    private final BitSet bitSet;

    public BloomFilter(int size) {
        this.size = size;
        bitSet = new BitSet(size);
    }

    public void addValue(String value) {
        bitSet.set(Math.abs(value.hashCode()));
    }

    public boolean exists(String value) {
        return bitSet.get(Math.abs(value.hashCode()));
    }

    public static void main(String[] args) {
        BloomFilter filter = new BloomFilter(10);
        filter.addValue("www.baidu.com");
        filter.addValue("www.163.com");
        System.out.println(filter.exists("www.126.com"));
        System.out.println(filter.exists("www.163.com"));
        System.out.println(filter.exists("www.baidu.com"));
    }
}

如上只是一个简单的演示实现。

google开源实现

pom文件中新增如下依赖

<dependency>
      <groupId>com.google.guava</groupId>
      <artifactId>guava</artifactId>
      <version>25.1-jre</version>
 </dependency>

使用BloomFilter

package sunce.xin.education.filter;

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;

import java.nio.charset.Charset;

/**
 * @author lowrie
 * @date 2019-07-03
 */
public class GoogleBloom {


    public static void main(String[] args) {
        BloomFilter<String> filter = 
            BloomFilter.create(Funnels.stringFunnel(Charset.forName("UTF-8")), 1000);
        filter.put("www.baidu.com");
        filter.put("www.163.com");
        System.out.println(filter.mightContain("www.126.com"));
        System.out.println(filter.mightContain("www.163.com"));
        System.out.println(filter.mightContain("www.baidu.com"));
    }
}