“布鲁姆过滤器布鲁姆过滤器”(Bloom Filter )是布鲁姆于1970年提出的，实际上由长二进制向量和一系列随机映射函数组成。
可以教它是一种基于概率的数据结构，主要用来判断某个元素是否在集合内，它具有运行速度快（时间效率），占用内存小的优点（空间效率），但是有一定的误识别率和删除困难的问题某些元素一定不在集合内或可能在集合内。
作为原理分析的例子，假设数组长度m=19、k=2个散列函数
既然选择了混列算法，冲突的可能性必然存在。 根据两个完全不同的值计算出的混列值有可能一致。 多次使用混列算法，对同一值取不同的多个混列，混列越多。 冲突率会很低。 当然hash的数量也不是越多越好。
插入数据
如上所述，由于插入两个元素，x和y、x这两个散列值分别为4、9，所以4和9的比特设定为1； 由于y的两次混列提取后的值分别为14和19，所以14和19位设定为1。
如果将进程添加的元素插入k个散列函数中，使其与位数组中的k个位置相对应，并将此k个位置设置为1以查找数据BloomFilter查找元素，则使用与插入过程中相同的k个散列函数。 取型后，检索与各bit对应的值，如果所有bit都为1，则可能存在返回元素，否则可能不存在返回元素。
进程表示要查询的元素被提供给k个散列函数，以对应于位数组中的k个位置。 如果k个位置之一为0，则一定表示集合中k个位置均为1，那么可能表示集合中为什么只有bit均为1时才可能存在元素呢？ 当然，如上图所示，只有x、y存在，两个元素混列的值不重复的情况下。 在这种情况下，可以确认元素一定存在。
但是，还有别的情况。 假设在这里调查z要素。 假设z元素不存在。 但是，经过hash计算的位置是9，14。 我很清楚这里的9是x元素的，14是y元素的。 z不存在。 但是，混列计算的结果是返回值都是1。 因此，程序认为z存在，但实际上z不存在。 这种现象被称为假定位
数据bloom过滤器不允许执行删除操作的原因是，删除可能会导致原始元素不存在。 这是不允许的吗？ 还是用一个例子来说明：
在上图中，首先有元素x、y和z，其hash的bit如图所示删除x，然后将bit 4和9设置为0。 这同时也会引起查询z时报告不存在的问题。 这对于bloom过滤器来说是不可接受的。 为什么这么说，是因为绝对不存在，或者有可能存在。
问题： bloom过滤器不允许删除的机制可能会导致更多无效元素。 也就是说，实际上是正在删除磁盘的元素，但bloom过滤器认为可能存在，因此false positive正在增加。
优缺点常见的数据结构，例如hashmap、set和bit array，可以用于测试一个元素是否存在于一个集合中，那么BloomFilter对这些数据结构有什么好处呢？
与其他数据结构相比，布隆过滤器在空间和时间方面有很大的优势。 光晕滤波器的存储区域和插入/查询时间均为常数(o(k ) )。 另外，散列函数相互无关，便于硬件并行实现。 布隆过滤器不需要保存元素本身，在对保密要求非常严格的情况下有利。
在hashmap的情况下，本质上是指针数组，一个指针的开销是sizeof(void )，在64比特的系统中是64比特，如果用开放链方法处理冲突，则需要额外的指针开销(数据来自维基百科) )对于set，用hashmap方式实现时也是同样的。 以平衡树方式实现时，一个节点需要指针存储数据的位置，两个指针指向其子节点，因此开销比hashmap多。 在bit array中，对于是否存在某个元素，首先将元素hash，取模型放置在特定的bit中，如果bit为1则存在元素，如果bit为0则返回该元素不存在。可以看出，在存在返回元素时也存在错误判断。 要获得与bloom过滤器相同的错误判断率，比bloom过滤器更大的存储空间光晕过滤器必须表示全集，其他任何数据结构都不能。
保存全部量，但不保存数据本身。 适合要求保密的场景的空间复杂度为o(m )，不会随着元素的增加而增加，占用空间少，插入和查询时间复杂度都为o ) k )，不会随着元素的增加而增加，超出了一般算法但是，布隆过滤器的缺点和优点一样明显。 误算率就是其中之一。 随着进款元素数量的增加，误算率增加。 但是，如果元素数量过少，则使用哈希表就足够了。
此外，一般不能从光晕滤波器中删除要素。 将位数组设为整数数组，每次插入元素时对应的计数器加1，删除元素时减去计数器就可以了，这一点非常容易。 但是，安全删除元素并不容易。 首先，必须确保删除的元素位于布隆过滤器中。 这是
一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。 相对于hashmap和set，BloomFilter在返回元素可能存在的情况中，有一定的误判率，这时候，调用者在误判的时候，会做一些不必要的工作，而对于hashmap和set，不会存在误判情况对于bit array，BloomFilter在插入和查找元素是否存在时，需要做多次hash，而bit array只需要做一次hash，实际上，bit array可以看做是BloomFilter的一种特殊情况在降低误算率方面，有不少工作，使得出现了很多布隆过滤器的变种。
存在误算率，数据越多，误算率越高一般情况下无法从过滤器中删除数据二进制数组长度和 hash 函数个数确定过程复杂使用场景布隆过滤器的巨大用处就是，能够迅速判断一个元素是否在一个集合中。因此他有如下三个使用场景:
网页爬虫对URL的去重，避免爬取相同的URL地址
反垃圾邮件，从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱（同理，垃圾短信）
缓存穿透，将所有可能存在的数据缓存放到布隆过滤器中，当黑客访问不存在的缓存时迅速返回避免缓存及DB挂掉。
BloomFilter的使用-缓存穿透在大多应用中，当业务系统中发送一个请求时，会先从缓存中查询；若缓存中存在，则直接返回；若返回中不存在，则查询数据库。
缓存穿透：当请求数据库中不存在的数据，这时候所有的请求都会打到数据库上，这种情况就是缓存穿透。如果当请求较多的话，这将会严重浪费数据库资源甚至导致数据库假死。
BloomFilter解决缓存穿透的思路，这种技术在缓存之前再加一层屏障，里面存储目前数据库中存在的所有key，当业务系统有查询请求的时候，首先去BloomFilter中查询该key是否存在。若不存在，则说明数据库中也不存在该数据，因此缓存都不要查了，直接返回null。若存在，则继续执行后续的流程，先前往缓存中查询，缓存中没有的话再前往数据库中的查询。
项目中使用关于布隆过滤器，我们不需要自己实现，谷歌已经帮我们实现好了。
pom引入依赖 <!-- https://mvnrepository.com/artifact/com.google.guava/guava --><dependency> <groupId>com.google.guava</groupId> <artifactId>guava</artifactId> <version>27.0.1-jre</version></dependency> 代码guava 的布隆过滤器，封装的非常好，使用起来非常简洁方便。
1、布隆过滤器的默认容错率是0.03
public static void main(String[] args) { int size=10000; double fpp=0.0001; //没有设置误判率的情况下，10000→312，误判率3.12% BloomFilter<CharSequence> bloomFilter = BloomFilter.create(Funnels.stringFunnel( Charset.forName("utf-8")),10000); for (int m=0;m<size;m++){ bloomFilter.put(""+m); } List<Integer> list=new ArrayList<Integer>(); for(int n=size+10000;n<size+20000;n++){ if(bloomFilter.mightContain(""+n)){ list.add(n); } } System.out.println("误判数量：：："+list.size()); }//源码：：在调用没有设置容错率的创建实例方法时，默认0.03的容错率 public static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions) { return create(funnel, expectedInsertions, 0.03D); }2、测试容错率的变化，所需数组位数的变化
容错率0.0001，所需位数191701
public static void main(String[] args) { // 1.创建符合条件的布隆过滤器 // 预期数据量10000，错误率0.0001 BloomFilter<CharSequence> bloomFilter = BloomFilter.create(Funnels.stringFunnel( Charset.forName("utf-8")),10000, 0.0001); // 2.将一部分数据添加进去 for (int i = 0; i < 5000; i++) { bloomFilter.put("" + i); } System.out.println("数据写入完毕"); // 3.测试结果输出 for (int i = 0; i < 10000; i++) { if (bloomFilter.mightContain("" + i)) { System.out.println(i + "存在"); } else { System.out.println(i + "不存在"); } }} //根据插入的数量和误判率来得出位向量应有的长度long numBits = optimalNumOfBits(expectedInsertions, fpp);//根据插入的数量和位向量的长度来得出应该用多少个Hash函数int numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);容错率0.01，所需位数95850
由此可见，误判率越低，则底层维护的数组越长，占用空间越大。因此，误判率实际取值，根据服务器所能够承受的负载来决定，不是拍脑袋瞎想的。