布隆过滤器是由 BURTON H. BLOOM 在 1970 年提出的一种哈希方法，用于判断一个元素是否存在于某个集合中。HashSet 或其他的数据结构都使用了传统的哈希方法，得到的结果是准确的，而布隆过滤器得到的结果不一定准确，因为它使用了一种近似的哈希算法。
那为什么还要使用它呢？因为数据量变大时，假如达到了 1 亿，传统的哈希方法效率将变低，布隆过滤器的性能却仍然很好。以下是论文的部分介绍，有兴趣的可以看下原论文。
传统哈希方法
先来回顾下传统的不允许错误的传统哈希方法。假设我们存储 n 条消息，每条消息有 b 位长。首先，我们将哈希区域分成 h 个单元，每个单元有 b + 1 位，h > n。多出来的 1 位用来标志该单元是否为空。所以每条消息是 b + 1 位，第一位始终为 1。存储过程如下：
生成一个哈希地址 k，0 <= k <= h - 1，这个哈希地址是一个伪随机数，检查第 k 个单元是否为空，如果为空，则将数据存储在第 k 个单元；否则再次生成一个哈希地址，直到该地址下的单元为空，然后把数据存储在这个单元里。
判断一个消息是否在集合中的原理类似，仍然继续生成哈希地址，直到满足以下条件之一：
- 找到一个单元，其中存储了与当前消息相同的数据，这种情况下，该消息数据该集合
- 找到一个空的单元，意味着该消息不属于该集合
允许错误的两个方法
方法 1
方法 1 是从传统的无误差方法中自然推导出来的，思路是集合中并不直接保存元素本身，而是将元素编码为 code 后保存，code 比元素本身小，从而能使集合容纳更多的元素。
code 设置为多大？code 的大小取决于你允许它犯错的概率，即误差分数。误差分数越大，code 越小；误差分数越小，code 的越大且越接近元素本身大小。当误差分数足够小时（约 2 的 -b 次方），code 大小几乎和元素本身一致。如果 P 表示误差分数，则 1 >> P >> 2 的 -b 次方。
所以假设 code 的大小为 c，则 c < b，且 c 的大小应使预期的错误分数接近并小于 P，哈希区域的每个单元的第一位仍然为 1。由于两个不同的消息可能转为同一个 code，所以这种方法会有一定的误差。
方法 2
网上文章讲述的大多是此方法，即将哈希区域被设置为 N 个单独的位置，从 0～N-1，这 N 个位置初始值都是 0，首先，需要将集合中的每个元素使用哈希算法映射在不同的地址上，将这些位置值为 1。当要判断一个元素是否存在某个集合中时，使用同样的哈希算法进行散列，如果对应位置的值都是 1，我们认为这个元素“可能”存在，反之一定不存在。
为什么是“可能”呢？因为随着元素变多，值为 1 的位置将越来越多，可能要判断元素的散列位置，被其他元素恰好都置为 1 了，这时我们以为该元素存在，实际上不存在。
实践
引入 maven 包：
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>28.0-jre</version>
</dependency>
创建一个集合，集合中放 1 亿个元素 0～99999999，然后判断 10000～100009999 在集合中的个数，理论上应该是 99990000 个，实际输出结果是 99990291 个。所以也验证了布隆过滤器确实存在一定误差。
public class BloomFilterDemo {
public static void main(String[] args) {
int total = 100000000;
// 集合中放 1 亿个数
BloomFilter<Integer> bf = BloomFilter.create(Funnels.integerFunnel(), total);
for (int i = 0; i < total; i++) {
bf.put(i);
}
// 判断 1 亿个数是否存在集合中
int ret = 0;
for (int i = 10000; i < total + 10000; i++) {
if (bf.mightContain(i)) {
ret++;
}
}
System.out.println(ret);
}
}
参考
Space/time trade-offs in hash coding with allowable errors：https://dl.acm.org/doi/10.1145/362686.362692
2. 5 分钟搞懂布隆过滤器，亿级数据过滤算法你值得拥有！:https://juejin.cn/post/6844904007790673933