前言

最近有朋友问我这么一个面试题目：

现在有一个非常庞大的数据，假设全是 int 类型。现在我给你一个数，你需要告诉我它是否存在其中(尽量高效)。

需求其实很清晰，只是要判断一个数据是否存在即可。

但这里有一个比较重要的前提：非常庞大的数据。

常规实现

先不考虑这个条件，我们脑海中出现的第一种方案是什么？

我想大多数想到的都是用 HashMap 来存放数据，因为它的写入查询的效率都比较高。

写入和判断元素是否存在都有对应的 API，所以实现起来也比较简单。

为此我写了一个单测，利用 HashSet 来存数据（底层也是 HashMap ）；同时为了后面的对比将堆内存写死：

-Xms64m -Xmx64m -XX:+PrintHeapAtGC -XX:+HeapDumpOnOutOfMemoryError 

为了方便调试加入了 GC 日志的打印，以及内存溢出后 Dump 内存。

    @Test     public void hashMapTest(){         long star = System.currentTimeMillis();          Set<Integer> hashset = new HashSet<>(100) ;         for (int i = 0; i < 100; i++) {             hashset.add(i) ;         }         Assert.assertTrue(hashset.contains(1));         Assert.assertTrue(hashset.contains(2));         Assert.assertTrue(hashset.contains(3));          long end = System.currentTimeMillis();         System.out.println("执行时间：" + (end - star));     }

当我只写入 100 条数据时自然是没有问题的。

还是在这个基础上，写入 1000W 数据试试：

执行后马上就内存溢出。

可见在内存有限的情况下我们不能使用这种方式。

实际情况也是如此；既然要判断一个数据是否存在于集合中，考虑的算法的效率以及准确性肯定是要把数据全部 load 到内存中的。

Bloom Filter

基于上面分析的条件，要实现这个需求最需要解决的是如何将庞大的数据 load 到内存中。

而我们是否可以换种思路，因为只是需要判断数据是否存在，也不是需要把数据查询出来，所以完全没有必要将真正的数据存放进去。

伟大的科学家们已经帮我们想到了这样的需求。

Burton Howard Bloom 在 1970 年提出了一个叫做 Bloom Filter（中文翻译：布隆过滤）的算法。

它主要就是用于解决判断一个元素是否在一个集合中，但它的优势是只需要占用很小的内存空间以及有着高效的查询效率。

所以在这个场景下在合适不过了。

Bloom Filter 原理

下面来分析下它的实现原理。

官方的说法是：它是一个保存了很长的二级制向量，同时结合 Hash 函数实现的。

听起来比较绕，但是通过一个图就比较容易理解了。

如图所示：

• 首先需要初始化一个二进制的数组，长度设为 L（图中为 8），同时初始值全为 0 。
• 当写入一个 A1=1000 的数据时，需要进行 H 次 hash 函数的运算（这里为 2 次）；与 HashMap 有点类似，通过算出的 HashCode 与 L 取模后定位到 0、2 处，将该处的值设为 1。
• A2=2000 也是同理计算后将 4、7 位置设为 1。
• 当有一个 B1=1000 需要判断是否存在时，也是做两次 Hash 运算，定位到 0、2 处，此时他们的值都为 1 ，所以认为 B1=1000 存在于集合中。
• 当有一个 
  关键字：