1. 怎么来的？
假设我们有 1 千万个整数，整数的范围是 1 到 1亿之间。如果给定一个整数，查询其是否在这 1 千万个整数之中？那么我们可以使用顺序查找、二分查找（有序前提下）、跳表查找、散列表查找、红黑树查找等等都可以。但是这些方法的话，都需要将这 1 千万个整数全都存储下来，有没有更加节省内存和时间的查询方法呢？这里其实也可以使用位图的方式，我们申请一个 1 亿个比特位的位图，之后将这 1 千万个数字使用位图来存储，比如针对数字 100，那么，我们就将第 100 个比特位设置为 1，表示 100 这个数字存在。查询时，我们查看第 100 个比特位的位置是否为 1，如果为 1 则表示 100 这个数字存在，否则不存在。通过比较可以发现，位图的使用空间大概在 12MB，而散列表等至少需要 40 MB。
但是，整数的范围如果很大，比如整数的范围在 1 到 10 亿之间，还是有 1 千万个整数，那么位图方式使用的空间会变大，需要大约 120 MB 的内存空间。显然，相比散列表等方式，消耗的内存空间，不降反增。
为了解决这个问题，我们可以使用布隆过滤器。布隆过滤器本身是基于位图的，是对位图的一种改进。布隆过滤器的做法是，仍然使用 1 亿个二进制位大小的位图，通过哈希函数，对数字进行哈希处理，让它落在 1 到 1 亿范围内。比如，我们将哈希函数设计成 f(x)=x%n， 其中 x 表示数字， n 表示位图的大小（1 亿），也就是数字跟位图大小进行取模。
但是，取模的方式肯定存在冲突。比如 1 和 1 亿零 1 这两个数字使用取模的哈希函数的话，是落在位图相同的地方。虽然，采用更复杂点、更随机点的哈希函数，会降低这种冲突的概率，但是也还是会存在冲突。那么布隆过滤器在位图和一个哈希函数的基础之上，多增加几个哈希函数，用多个哈希函数来定位一个数据。
2. 怎么做的？
那么布隆过滤器到底是怎么用多个哈希函数来定位一个数据的呢？我们使用 K 个哈希函数，对同一个数字求哈希值，我们会得到 K 个不同的哈希值，分别记为 x1、x2、x3,...,xk。我们把这 K 个数字作为位图中的下标，将对应的 BitMap[x1]、BitMap[x2]、...、BitMap[xk]，都设置为 1，也就相当于用 k 个二进制位来表示一个数字的存在。
当查询某个数字是否存在的时候，我们使用同样的 K 个哈希函数，对这个数字求哈希值，得到 y1、y2、...、yk。之后，根据这 K 个哈希值判断位图相应位置的值是否为 1，如果都为 1，那么则表示这个数字存在，如果有一个不为 1 则表示这个数字不存在。
这种方式虽然将冲突的概率降低了，你要想 K 个哈希值都一样的话，这个概率很低很低。但是这种方式容易误判，也就是某个数字经过布隆过滤器之后是存在的，那么这个数字不一定存在；但是某个数字经过布隆过滤器判断之后是不存在的，那么这个数字一定是不存在的。针对，这种情况，我们可以调整哈希函数的个数、位图的大小跟要存储数字的个数之间的比例，从而将这种误判的概率降到非常低。
即使将哈希函数的个数、位图的大小跟要存储数字的个数之间的比例调整得很完美。当往布隆过滤器中不断添加新的数据时，位图中不是 true 的位置将会越来越少，从而也会导致误判率越高（这跟散列表是一个特性的）。因此，我们需要支持自动扩容的功能，当布隆过滤器中，数据个数与位图大小的比例超过某个阈值的时候，我们就重新申请一个位图。
- 后面来的新数据，会被放到新的位图中。
- 查询某个数据时，我们可以就需要查看多个位图（效率会有所降低）。
3. 用在哪里？
虽然布隆过滤器存在误判，但是布隆过滤器非常适合那些不需要 100% 准确、允许存在小概率误判的大规模场景。
- 比如我们使用布隆过滤器来记录已经爬取的网页。那么假设一个网页没有被爬取过，但是却被当成爬取过了，那也不是什么特别大的事情，是可以容忍的。
- 比如统计一个大型网站的每天的 UV 数，由于每天访问的用户数特别多。因此，也可以使用布隆过滤器对重复访问的用户进行去重。
Java 中的 BitSet 类就是一个位图。Redis 也提供了 BitMap 位图类。Google 的 Guava 工具包也提供了 BloomFilter 布隆过滤器。
bloom filter：False is always false. True is maybe true.
4. 与散列表相比
布隆过滤器用多个哈希函数对同一个网页链接进行处理，CPU 只需要将网页链接从内存中读取一次，进行多次哈希计算，理论上讲这组操作是 CPU 密集型。
而散列表的处理方式中，当将网页链接从内存中读取出来进行比较时，需要比较多个网页链接（存在散列冲突），进行字符串匹配。这个操作涉及到比较多的内存数据的读取，所以是内存密集型的。CPU 的处理速度是比内存访问更快速的，所以理论上来说布隆过滤器的方式更快速。
5. 总结
布隆过滤器是什么？其实就是位图这种数据结构 + 多个哈希函数，组成一种新的数据结构。这种组合方法和散列表的组成方法是类似的。
布隆过滤器存在误判的情况，也就是一个不存在的值可能会被判断为存在了（不存在的会一直判断为不存在）。因此，布隆过滤器适合用于那些对误判存在一定容忍度的场景。
巨人的肩膀
- 极客时间-《数据结构与算法》-王争老师
