布隆过滤器(Bloom Filter)，是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。
Bloom Filter原理
当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个位数组中的K个点，把它们置为1。检索时，我们只要看看这些点是不是都是1就（大约）知道集合中有没有它了：如果这些点有任
何一个0，则被检元素一定不在；如果都是1，则被检元素很可能在。
比如数据库的id现在有：1、2、3
那就用id：1 为例子他在上图中经过三次hash之后，把三次原本值0的地方改为1
下次我进来查询如果id也是1 那我就把1拿去三次hash 发现跟上面的三个位置完全一样，那就能证明过滤器中有1的
应用场景
1.大数据判断是否存在
HashMap可以判断某个元素是否存，可以将值映射到 HashMap 的 Key，然后可以在 O(1) 的时间复杂度内返回结果，效率奇高。但是 HashMap 的实现也有缺点，例如存储容量占比高，考虑到负载因子的存在，通常空间是不能被用满的，而一旦你的值很多例如上亿的时候，那 HashMap 占据的内存大小就变得很可观了。这时候我们就需要考虑布隆过滤器了。
2.解决缓存穿透
布隆过滤器(Bloom Filter)提前将数据库的数据hash存到过滤器中，然后当redis没有这个key，请求来的时候先去布隆过滤器x次hash这个key，看是否都为1（都为1说明很大概率有这个key），如果是缓存穿透，就是数据库和redis都没有这个数据的话，布隆过滤器很大概率也没有，这样就能过滤掉绝大部分的没有得值
如何实现
引入依赖
<dependency> <groupId>com.google.guava</groupId> <artifactId>guava</artifactId> <version>19.0</version> </dependency>
代码
private static int size = 1000000;//预计要插入多少数据 private static double fpp = 0.01;//期望的误判率 private static BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, fpp); public static void main(String[] args) { //插入数据 for (int i = 0; i < 1000000; i++) { bloomFilter.put(i); } int count = 0; for (int i = 1000000; i < 2000000; i++) { if (bloomFilter.mightContain(i)) { count++; System.out.println(i + "误判了"); } } System.out.println("总共的误判数:" + count); }
经过测试，误判率大概在0.01，不影响大局
