所谓的大数据判存算法，就是如何在海量数据中快速判断某个数据是否存在。这里用到的知识是布隆过滤器（Bloom Filter），下面按照 what - why - how 的顺序来学习它。

1、什么是布隆过滤器

布隆过滤器（英语：Bloom Filter）是 1970 年由布隆提出的，布隆过滤器可以用于检索一个元素是否在一个集合中，因此它是一个空间效率极高的概率型算法；它实际上是一个很长的二进制向量和一系列随机映射函数；

上面给出了布隆过滤器的两个核心：二进制向量和一系列随机映射函数。我们说，数据结构的两个必备要素，一是数据，二是算法。二进制向量就是 bit 数据，可以简单的理解为一个只保存 01 的数组；而算法就是这些随机映射函数，可以简单理解成哈希函数。

注意，只保存 01 的数组与哈希函数只是二进制向量和随机映射函数的一种表现形式，不要以偏概全。随机映射函数还有其他形式，只不过布隆过滤器中用到了哈希函数，所以才说可以简单的认为是哈希函数，便于理解这些晦涩的术语。

布隆过滤器（Bloom Filter）是一种空间效率高、适合大规模数据集的概率性数据结构，用于快速检查一个元素是否可能在一个集合中存在。布隆过滤器可以告诉你“可能在集合中”或“肯定不在集合中”，但是不能告诉你“肯定在集合中”。

布隆过滤器的基本原理是使用多个哈希函数以及一个位数组来表示元素的存在情况。当一个元素被加入布隆过滤器时，将这个元素经过多个哈希函数计算出多个哈希值，在位数组对应的位置置为 1。当需要查询元素是否在布隆过滤器中时，同样对元素进行多次哈希计算，检查对应的位数组位置是否都为 1，如果有任何一位不为 1，则可以确定元素一定不在集合中；如果所有位都为 1，则说明元素可能在集合中。

下面通过一个业务场景来进一步理解布隆过滤器。假如存在三个物流单号：

想把这些单号存入布隆过滤器中，假设过滤器的映射函数有三个，二进制向量有 24 位。那么每个单号经过 f1、f2、f3 这三个哈希函数运算之后会把向量中的某些位置为 1。当你想要查询某个单号是否在过滤器中时，需要对该单号经过 f1、f2、f3 这三个函数运算，查看计算结果中应该为 1 的位置在向量中是否为 1，如果所有应该为 1 的位置在向量中均为 1，说明该单号可能在向量中，但如果有一位不同，则说明该单号一定不在向量中。

布隆过滤器的优点包括：

1. 空间效率高：相比于传统的数据结构，布隆过滤器可以使用较少的空间来存储大量元素的存在情况。
2. 查询速度快：布隆过滤器的查询时间复杂度是常数时间 O(n)，不受元素数量的影响（受随机映射函数数量 n 的影响，时间复杂度为 O(n)）。
3. 可扩展性强：可以根据需要调整哈希函数的数量和位数组的大小来适应不同规模的数据集。
4. 信息安全性较高：即便布隆过滤器的数据被盗，由于该数据无法逆向计算，也就无法还原出原本的数据。

然而，布隆过滤器也存在一些缺点，主要包括：

1. 存在误判：由于多个元素可能映射到同一个位置，因此可能存在误报的情况，即判断元素在集合中，但实际上并不在集合中（哈希碰撞造成的，这种误判率是可以控制的）。
2. 无法删除元素：一旦元素被加入到布隆过滤器中，就无法从中删除，因为删除一个元素可能会影响其他元素的判断结果（还是由于存在哈希碰撞，可能多个数据的同一个位置都是 1，如果因为删除其中一个数据将该位置为 0 会影响其他数组）。

2、为何学习布隆过滤器

布隆过滤器在实际应用中常被用于缓存、拼写检查、反垃圾邮件过滤等场景，可以有效减少对庞大数据集的访问次数，提高系统性能。

下面列出一些具体的业务场景，主要还是在海量数据之中判断一个元素是否存在：

• 比如编程 IDE 会提醒你可能拼错的英文单词，画一个红色的下划线。这需要在上百万个单词中去找是否有你写的那个单词
• 判断身份证号码是否在嫌疑人名单中
• 360 浏览器提醒你将要访问的网站有潜在危险

3、算法落地

Google Guava 库在 18.0 版本之上提供了布隆过滤器的实现，这里我们看 guava 19.0 版本的源码：

dependencies {implementation 'com.google.guava:guava:19.0'
}

Google Guava 提供了很多基础工具的增强实现，包含了 Google 这些技术天才在进行 Java 开发时凝练出的精华，比 JDK 的功能更强大。比如 Connection、事件总线、哈希算法、IO 增强、反射增强、多线程开发增强、HTML 的解析帮助等等。

3.1 简单使用

我们先来看布隆过滤器一个简单的使用示例：

public class BloomFilterDemo {private static final int insertions = 1_000_000;public void test() {// 创建存储 String 的布隆过滤器，大小为 100WBloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), insertions);HashSet<String> hashSet = new HashSet<>(insertions);ArrayList<String> list = new ArrayList<>(insertions);// 向三个容器初始化 100 万个随机且唯一的字符串，100 万个 uuid 34M 多for (int i = 0; i < insertions; i++) {String uuid = java.util.UUID.randomUUID().toString();bloomFilter.put(uuid);hashSet.add(uuid);list.add(uuid);}// 过滤器判断正确与错误的次数int right = 0, wrong = 0;for (int i = 0; i < 10000; i++) {String test = i % 100 == 0 ? list.get(i / 100) : UUID.randomUUID().toString();if (bloomFilter.mightContain(test)) {if (hashSet.contains(test)) {right++;} else {wrong++;}}}// right = 100 ,wrong = 288System.out.println("right = " + right + " ,wrong = " + wrong);}public static void main(String[] args) {new BloomFilterDemo().test();}
}

对布隆过滤器、HashSet 和 ArrayList 都初始化相同的 100 万个数据。然后从中选择 1 万数据进行测试，先通过 bloomFilter.mightContain() 查看这些数据是否可能在布隆过滤器中，然后对同样的数据再看是否在 HashSet 中。由于 HashSet 的数据不存在误判，因此可以用来衡量 bloomFilter.mightContain() 判断正确和错误的次数，最终输出这些次数，可以看到判断错误的次数是 288。多次运行程序可以发现 right 一直等于 100，而 wrong 一直在 300 左右徘徊，也就是说 10000 个数据中大概有 300 个数据会判断错误，误判率在 3% 左右。

3.2 源码简析

布隆过滤器的实现类是 guava-19.0.jar!\com\google\common\hash\BloomFilter.class，通过查看源码我们发现误判率是可以通过方法参数进行控制的。

我们通过 BloomFilter 的 create() 创建布隆过滤器对象时，可以传不止两个参数：

  public static <T> BloomFilter<T> create(Funnel<? super T> funnel, int expectedInsertions) {return create(funnel, (long) expectedInsertions);}public static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions) {return create(funnel, expectedInsertions, 0.03); // FYI, for 3%, we always get 5 hash functions}public static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions, double fpp) {return create(funnel, expectedInsertions, fpp, BloomFilterStrategies.MURMUR128_MITZ_64);}

我们在上面的示例中使用的是第一个重载的 create()，指定了 Funnel 接口的具体类型为 StringCharsetFunnel，还指定了插入数据的数量 expectedInsertions 为 100 万。该方法会调用三个参数的 create()，增加的参数 fpp 就是误判率，默认指定为 0.03 也就是 3%，与上面例子中的数据吻合。

也就是说，误判率可以通过方法的参数显示指定。

然后我们先看 create() 最终会被调用的、拥有 4 个参数的重载方法：

  @VisibleForTestingstatic <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions, double fpp, Strategy strategy) {checkNotNull(funnel);checkArgument(expectedInsertions >= 0, "Expected insertions (%s) must be >= 0", expectedInsertions);checkArgument(fpp > 0.0, "False positive probability (%s) must be > 0.0", fpp);checkArgument(fpp < 1.0, "False positive probability (%s) must be < 1.0", fpp);checkNotNull(strategy);if (expectedInsertions == 0) {expectedInsertions = 1;}// numBits 是二进制向量的长度，numHashFunctions 是随机映射函数，也就是哈希函数的个数long numBits = optimalNumOfBits(expectedInsertions, fpp);int numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);try {return new BloomFilter<T>(new BitArray(numBits), numHashFunctions, funnel, strategy);} catch (IllegalArgumentException e) {throw new IllegalArgumentException("Could not create BloomFilter of " + numBits + " bits", e);}}

运行程序打断点，在误判率为默认的 3% 的情况下，numBits = 7298440，numHashFunctions = 5。但是如果调用 create() 创建过滤器时将误判率设置为 0.1% 的话：

BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), insertions, 0.001);

再次进行断点调试，会发现 numBits = 14377587，numHashFunctions = 10。说明想要降低误判率，是需要复出增多二进制向量位数和哈希函数数量的代价的。至于为什么是这些数量，是 Google 工程师根据大量测算给出的推荐值。