布隆过滤器

简介：本质上布隆过滤器是一种数据结构，比较巧妙的概率型数据结构（probabilistic data structure），特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”

判断一个元素是不是在一个集合里，一般想到的是将所有元素保存起来，然后通过比较来确定。链表、平衡二叉树、散列表，或者是把元素放到数组或链表里，都是这种思路。以上三种结构的检索时间复杂度分别为O(n), O(logn), O(n/k)，O(n),O(n)。而布隆过滤器(Bloom Filter)也是用于检索一个元素是否在一个集合中，它的空间复杂度是固定的常数O(m)，而检索时间复杂度是固定的常数O(k)。相比而言，有1%误报率和最优值k的布隆过滤器，每个元素只需要9.6个比特位--无论元素的大小。这种优势一方面来自于继承自数组的紧凑性，另外一方面来自于它的概率性质。1%的误报率通过每个元素增加大约4.8比特，就可以降低10倍

应用场景：主要是解决大规模数据下不需要精确过滤的场景，如检查垃圾邮件地址，爬虫URL地址去重，解决缓存穿透问题等。

在缓存穿透问题上，使用布隆过滤器判断数据是否存在，不存在直接返回
海量数据去重：爬虫系统中对成千上万的url的去重等
邮箱系统的垃圾邮件过滤功能

实际测试代码

import java.util.ArrayList;
import java.util.List;

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

public class Bloom {

private static int size = 1000000;  
// private static BloomFilter<CharSequence> bloomFilter =  
// BloomFilter.create(Funnels.stringFunnel(Charset.forName("utf-8")),  
private static BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, 0.0001);

public static void main(String\[\] args) {

    for (int i = 0; i < size; i++) {  
        bloomFilter.put(i);  
    }  
    System.out.println("write over!");

    for (int i = 0; i < size; i++) {  
        if (!bloomFilter.mightContain(i)) {  
            System.err.println("有逃犯越狱了");  
        }  
    }

    List<Integer> list = new ArrayList<Integer>();  
    for (int i = size + 10000; i < size + 20000; i++) {  
        if (bloomFilter.mightContain(i)) {  
            list.add(i);  
        }  
    }  
    System.out.println("误伤数：" + list.size());  
}  
// 可能存在误判，当布隆过滤器说某个值存在时，这个值可能不存在；当它说不存在时，那就肯定不存在  

}

com.google.guava guava 28.0-jre