布隆过滤器的原理及应用场景

1. 什么是布隆过滤器

布隆过滤器（Bloom Filter）由布隆于 1970 年提出，它实际上由一个很长的二进制向量和一系列随机映射函数组成。布隆过滤器可以用于查询一个元素是否在一个集合中，它的优点是空间和时间效率都远超一般的算法，缺点是会有一定的误判和删除困难。

• 它并不存储数据本身，因此不能从布隆过滤器中取出原数据。
• 它判断数据存在时，有一定误差：某数据不存在其中，但是它可能说数据存在。
• 如果它判断出数据不在其中，那么就一定是的。
• 只能往里添加数据，不能移除数据。

2. 布隆过滤器的原理 (参考文章)

先了解下哈希函数的概念是：将任意大小的数据转换成特定大小的数据的函数，转换后的数据称为哈希值或哈希编码。

布隆过滤器的底层是一个比特数组，将某个数据A放入时，通过若干个哈希函数计算出若干个值，假设通过3个哈希函数，算出3个哈希值x，y，z。x，y，z对应到比特数组的相应位置，将该位置上的比特位设置为1. 那么该数据就被放进来了。

在下面的图中，蓝/红/紫色表示有3个数据被放入了比特数组，各自相应的比特位被设置为1.
此时，数据w并没有被放入比特数组，但它相应的哈希值对应的比特位都为1，那么布隆过滤器就会认为w存在。这就会造成误判。

布隆过滤器底层

3. 应用场景

布隆过滤器适用于大数据量，但又能允许一定程度的误差，这样的场景。例如：

• 爬虫url判断重复
  将要爬一个url时，用布隆过滤器判断是否存在，不存在则放入，存在则不处理。误判就是此url没爬过，但布隆过滤器说爬过了，那么爬虫过程中会缺失一些url，这个不影响。

• 缓存穿透
  通过布隆过滤器将所有数据都放入比特数组。当有请求过来，如果请求的是存在的数据，那么肯定会放行；如果是不存在的数据，可能会被挡住，小概率可能被放行。那么，大部分的恶意请求就能被挡下来。

4. 布隆过滤器的Java实现

Guava包中提供了BloomFilter的实现。

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

public class BloomFilterTest {

    public static void main(String[] args) {
        BloomFilter<CharSequence> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), 200000, 1E-7);
                
        bloomFilter.put("test");
        
        boolean contain = bloomFilter.mightContain("test");
        
        if (contain)
            System.out.println("contain test");
    }

}