如何高效判断元素 w 是否位于集合 A 中？
常用方式：将集合A中元素存放到哈希表中，然后在哈希表中查询元素 w。
若集合 A 中元素数量巨大，其数据量大小远远超过机器内存空间，应该如何解决？
将集合中值映射到HashMap的key，可以在O(1)的时间复杂度内进行元素存在性判定，这种方式适用于小数据量场景下元素存在性判定。考虑到HashMap负载因子的存在（默认为0.75），通常空间是不能被用满的，而一旦集合中数据量过多（例如达到亿级别），那么HashMap占用的内存大小就变得很可观了。
对于这种情况可以通过“实现基于磁盘和内存的哈希索引” 或者 “借助布隆过滤器实现存在性判断” 两种方式解决，相对而言布隆过滤器更加简洁。
布隆过滤器（Bloom Filter）
概念
布隆过滤器包含一个长度为 N 的 01 数组 array，array中每个元素的初始值均为 0。
对集合 A 中的每个元素 a 做 K 次哈希，第 i 次哈希值对 N 取模得到一个 index(i)，即index（i）= HASH_i（a）% N，将 array 数组中的 array[index（i）] 置为1。最终 array 变成一个某些元素为 1 的 01 数组。
以集合 A = ｛x，y，z｝，K=3为例。初始化 array = 0000000000000000。
对于元素 x，HASH_0（x）= 1 ，HASH_1（x）= 5 ，HASH_2（x）= 13 ，因此 array = 0100010000010000。
对于元素 y，HASH_0（y）= 4 ，HASH_1（y）= 11 ，HASH_2（y）= 16 ，因此 array = 0100110001010010。
对于元素 z，HASH_0（z）= 3 ，HASH_1（z）= 5 ，HASH_2（z）= 11 ，因此 array = 0101110001010010。
最终得到的布隆过滤器串为：0101110001010010，如下图所示。
此时，对于目标元素 w 进行 K 次哈希：
HASH_0（w）= 4 ，HASH_1（w）= 13 ，HASH_2（w）= 15
可以发现，布隆过滤器中 array 的第 15 位为 0，因此可以确认元素 w 肯定不在集合 A 中。
如果另有一个元素 t，K 次哈希值分别为 ：
HASH_0（w）= 5 ，HASH_1（w）= 11 ，HASH_2（w）= 13
我们发现布隆过滤器创众的第 5、11、13 位都为 1，但是不能确定元素 t 一定在集合 A 中，最终得出 t 可能存在于集合 A 中。
布隆过滤器对于任意给定元素 w ，给出的存在性结果有两种：
1、元素 w 可能存在于集合 A 中
2 、元素 w 肯定不存在于集合 A 中
注意：普通的布隆过滤器不支持删除操作。
当 N 取 K*|A|/ln2 时，能够保证最佳的误判率。其中 |A| 表示集合A的元素个数，K 为对于每一个元素做 K 次哈希。
所谓的误判率就是过滤器判定元素可能在集合中，但实际不在集合中的占比。
借助布隆过滤器可以进行存在性判断。大多数情况下，要比普通的存在性判断方式更高效、占用空间更少，但缺点是其返回的结果是概率性的，不是确切的。
布隆过滤器作用
利用布隆过滤器减少磁盘IO或者网络带宽。
对于文章开始所提的案例，借助布隆过滤器可以提供新的解决方案。把集合 A 中的元素按照顺序分成若干块，每块不超过64KB，针对每块内的所有元素计算出对应该块的布隆过滤器，多个块的布隆过滤器组成索引数据。查找元素 w 时，针对索引数据中的所有布隆过滤器逐一进行存在性判断。对于可能存在的情况，读取对应数据块并查找元素 w 是否存在，若查找到元素 w，则停止查找操作。
