编写代码时，经常会确定元素是否已经存在。 常用的是把已经存在的元素都存储在一个集合中，新元素检查它是否在集合中，判断是否已经存在。 该集合的数据结构一般采用HashMap。 这可以按o(1)的时间复杂度返回结果，非常有效率。 但是，存在一个个的数据完全被存储在集合中的问题，容量大的情况下，占有的存储器区域成为问题。
如果你正好遇到这方面的问题，想想布隆过滤器。
另一方面，模糊滤波器的原理和作用1、原理布隆过滤器实际上是一个很长的二进制向量和一系列随机映射函数。二进制向量实际上只能存储0和1的数组，每个位置的初始值为0。 随机映射函数，计算元素以获取哈希值，并将数组中与此哈希值的下标位置相对应的值更改为1。 例如
定义长度为10的二进制向量
用三种映射函数计算字符“周”的哈希值，分别得到2、5、8时，将二进制向量，即与数组下标位置对应的值都设为1
再做一个文字“华”吧。 如果用三种映射函数计算哈希值分别得到2、5、6，则处理后的数组是这样的
需要判断文字“煌”是否存在时，首先利用相同的三个映射函数分别计算哈希值，例如3、4、5，判断与排列中下标位置对应的值。只要有一个为0，那么说明这个字符一定不存在，但是如果全是1呢，只能说可能存在。为什么不呢？
我知道散列评估可能会发生冲突。 (请参阅HashMap中使用数组链表的结构)随着存储的数据增加，字符计算的哈希值可能相同。 此时，无法判断是否一定存在一个要素。 ——这是有误判的。
很明显，二进制向量长度太小的布隆过滤器将很快使所有位都变为1，并且在询问任何值时都会返回“可能存在”，从而无法实现过滤目的。 布隆过滤器的长度直接影响误报率，布隆过滤器越长误报率越小。 另外，映射函数的数量也需要折衷，数量越大，模糊滤波器的位位置位1的速度越快，模糊滤波器的效率越低； 但是太少的话，我们的误报率会很高。
k是散列函数个数，m是布隆过滤器的长度，n是要插入的要素的个数，p是误报率
是如何选择适合业务的 k 和 m 值呢。 在此直接粘贴公式：
我们讨论了布隆过滤器的元素添加和是否存在的判断，是否支持删除？
上面的东西不行。 为什么呢？ 例如，如果要删除“周”字符，请将数组中2、5和8位置的值设置为0。 但是，也有2和5这个位置的文字“华”。 如果把这两个位置的值变成了0，那么下次判断文字“华”时就认为0存在所以不存在，实际上人是存在的。
要解决这个问题，删除计数是答案。 但是，在删除计数时，需要保存数值而不是原始位，使用的内存大小会变大。 于是，增加一个值就是增加一个存储在相应索引时隙中的值，在删除的情况下减少一个值，在判断是否存在的情况下看值是否大于0。
2、用途分析了以上原理，至少知道了布隆过滤器的特点
优点：因为没有存储完整的数据，所以占用的内存少，而且添加、查询速度足够快。 缺点：随着数据的增加，无法删除误判率增加的数据； 只能判断数据是否一定存在，不能判断数据是否一定存在。 应用场景是什么？
1)缓存穿透
某些数据(如产品详细信息)经常放在Redis等缓存中。 以这种方式收到查询请求后，可以根据产品Id直接将数据检索到缓存中，而不是读取数据库。 这是提高性能最简单、最常见、最有效的方法。 典型的查询请求流程是，首先检查缓存，有缓存时直接返回，不在缓存时去数据库查询，将从数据库检索的数据放入缓存中，一切看起来都很美。 但是，如果现在有大量的请求进来，要求不存在的产品Id，会发生什么？ 既然产品Id不存在，就一定没有高速缓存和高速缓存。 大量的请求涌向数据库，一下子增加了数据库的压力，也有可能杀死数据库。
解决这个问题的方法有很多，但我们的主角是“布隆过滤器”。 没错，“布隆过滤器”可以解决(缓解)缓存直通问题。 看看为什么是“缓解”就知道了。
2)大量数据，判断给定的是否在其中
虽然现在有大量数据，但是这些数据的大小远远超过了服务器的内存。 现在我再给你一个数据。 你怎么判断给你的数据是否在那里？ 如果服务器有足够的内存，使用HashMap是一个很好的解决方案，理论时间复杂度可以达到O(1)，但是现在数据的大小远远超过服务器的内存，所以不能使用HashMap。 此时，可以使用“布隆过滤器”解决这个问题。 但是，还是一样，有一定的“误判率”。
二、布隆过滤器的Java实现1 )可以使用二进制向量、BitSet (存储类型为boole
an，所有位置默认值是false）取代。2）多个映射函数：分别配合一组不同的质数求值。3）哈希值不超过数组下标：对结果再进行 &(长度-1) 的操作。直接上代码（线程安全且支持自定义长度和映射函数数量）
import java.util.BitSet;import java.util.Objects;import java.util.concurrent.locks.ReentrantReadWriteLock;/** * 布隆过滤器 * * @author Zhou Huanghua */public class BloomFilter { private BitSet bits; private SimpleHash[] hashFuncs; private ReentrantReadWriteLock readWriteLock = new ReentrantReadWriteLock(); private ReentrantReadWriteLock.ReadLock readLock = readWriteLock.readLock(); private ReentrantReadWriteLock.WriteLock writeLock = readWriteLock.writeLock(); public BloomFilter(int bitNum, int hashFuncNum) { if (bitNum < 1 || bitNum < 1) { throw new IllegalArgumentException("bitNum and hashFuncNum must greater than 0"); } bits = new BitSet(bitNum); hashFuncs = new SimpleHash[hashFuncNum]; int[] primes = getPrimes(hashFuncNum); for (int i = 0; i < hashFuncNum; i++) { hashFuncs[i] = new SimpleHash(bitNum, primes[i]); } } public void add(String value) { if (Objects.isNull(value)) { throw new NullPointerException("value can't be null"); } writeLock.lock(); try { for (SimpleHash f : hashFuncs) { bits.set(f.hash(value), true); } } finally { writeLock.unlock(); } } public boolean contains(String value) { if (value == null) { return false; } readLock.lock(); try { boolean ret = true; for (SimpleHash f : hashFuncs) { ret = ret && bits.get(f.hash(value)); } return ret; } finally { readLock.unlock(); } } private int[] getPrimes(int num) { int[] primes = new int[num]; for (int i = 2, idx = 0; idx < num; ++i) { boolean isPrime = true; for (int j = 2, middle = i / 2; j <= middle; ++j) { if (i % j == 0) { isPrime = false; break; } } if (isPrime) { primes[idx++] = i; } } return primes; } private class SimpleHash { private int cap; private int seed; public SimpleHash(int cap, int seed) { this.cap = cap; this.seed = seed; } public int hash(String value) { int result = 0; for (int i = 0, len = value.length(); i < len; i++) { result = seed * result + value.charAt(i); } return (cap - 1) & result; } }}用法如下
public static void main(String[] args) { BloomFilter bloomFilter = new BloomFilter(2 << 24, 8); String value = "zhou"; Assert.assertFalse(bloomFilter.contains(value)); bloomFilter.add(value); Assert.assertTrue(bloomFilter.contains(value)); Assert.assertFalse(bloomFilter.contains(null)); // 抛异常 bloomFilter.add(null); } 三、网上现有的开源工具发明轮子只是为了理解其背后的实现原理，真正使用还得拥抱流行的开源-_-。
guava和elasticsearch的实现很相似。
1、Guava的BloomFilterFunnel参数的作用就是，根据你传入的对象确定真正插入和用于判断的key。传入预期插入值和误报率之后，它会帮你自动设置向量长度和函数个数。
// 创建实例，传入"转换器"、预期插入值、误报率 BloomFilter bloomFilter = BloomFilter.create(new Funnel<String>() { @Override public void funnel(String s, PrimitiveSink primitiveSink) { primitiveSink.putString(s, Charset.defaultCharset()); } }, 2 << 24, 0.0000001D); String value = "周"; // 此时不存在 Assert.assertFalse(bloomFilter.mightContain(value)); // 添加值 bloomFilter.put(value); // 现在存在了 Assert.assertTrue(bloomFilter.mightContain(value)); 2、Elasticsearch的BloomFilter传入预期插入值和误报率之后，它会帮你自动设置向量长度和函数个数。
// 创建实例，传入预期插入值、误报率 BloomFilter bloomFilter = BloomFilter.create(2 << 24, 0.0000001D); BytesRef value = new BytesRef("周"); // 此时不存在 Assert.assertFalse(bloomFilter.mightContain(value)); // 添加值 bloomFilter.put(value); // 现在存在了 Assert.assertTrue(bloomFilter.mightContain(value)); 3、Redis的布隆过滤器使用redis 4.0以上的版本可以通过加载module来使用redis中的布隆过滤器。但是这不是最简单的方式，使用docker可以直接在redis中体验布隆过滤器。
暂时没发现比较好的开源实现，不过你可以自己写一个。
总结一下：布隆过滤器可以确定一个元素一定不存在，只能判断一个元素可能存在，向量长度和随机函数数量决定其误报率。