前言

在大一刚学习编程的时候，课后习题有这么一道题：现有一个数量为n的有序整数集合，需要判断一个数是否在这个集合中。那时刚学习for循环，所以理所当然的，当时的做法为：
遍历整个集合，判断数字是否存在于集合中

过了一段时间，学习了一些查找算法，了解了时间复杂度的概念；再次看到了这道题目；此时的做法则为：
使用二分查找法，判断数字是否存在于集合中

再后来，学习了数据结构相关的知识，再次碰到了这道题目；不同的是这次的集合是无序的。这个时候想到了两种做法；

• 第一种：
  先使用快速排序将集合排序，然后再使用二分查找进行判断
  但快排本身的时间复杂度也有O(nlogn)，只为了查找一条数据的话还是有点慢的；于是有了第二种做法。
• 第二种：
  使用HashMap来存放数据，然后进行判断
  使用此方法，时间复杂度只需O(1)

曾经我以为HashMap算是这类问题的万能适用解了；但后来我又遇到了这么一个问题，依旧是数量为n的无序集合，判断一个整数是否存在其中，不过不同的是n的值为一亿。

一开始我自然是直接用HashMap处理了，但是在将数据存储至HashMap的时候内存溢出了，此时才明白除了时间复杂度以外，我们还需要考虑到空间问题。这时候布隆过滤就应运而生了。

原理

布隆过滤器使用二进制向量结合hash函数来记录任意一条数据是否已经存在于集合中。
布隆过滤器的执行流程为：

• 首先申请包含SIZE个bit位的Bit集合，并将所有Bit置0。
• 然后使用数种（k）不同的哈希函数对目标数据进行哈希计算并得到k个哈希值（确保哈希值不超过SIZE大小），然后将Bit集合中以哈希值为下标所处的bit值置为1，由于使用了k个哈希函数，因此记录一条数据的信息将在Bit集合中把k个bit值置为1。
• 由于哈希函数的稳定性，任意两条相同的数据在Bit集合中所对应的k个bit位置是完全相同的。那么在检测某一条数据是否已经在Bit集合中有记录时，只需检测该条数据的k个哈希值在Bit集合中对应的位置的bit是否均已被标记为1，相反的只要其存在一个哈希值对应的bit位置未被标记为1，则证明该值未被记录过。

使用示例

布隆过滤器的示例如下：

image.png

大体过程为：

• 首先初始化一个二进制的数组，长度设为 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 存在于集合中。
• 当有一个 B2=3000 时，也是同理。第一次 Hash 定位到 index=4 时，数组中的值为 1，所以再进行第二次 Hash 运算，结果定位到 index=5 的值为 0，所以认为 B2=3000 不存在于集合中。

优缺点

• 优点
  时间复杂度为O(n)，且布隆过滤器不需要存储元素本身，使用位阵列，占用空间也很小。
• 缺点
  通过布隆过滤，我们能够准确判断一个数不存在于某个集合中，但对于存在于集合中这个结论，布隆过滤会有误报（可能存在两组不同数据但其多个哈希值完全一样的情况）。但是通过控制Bit集合的大小（即SIZE）以及哈希函数的个数，可以将出现冲突的概率控制在极小的范围内，或者通过额外建立白名单的方式彻底解决哈希冲突问题。

误判率计算公式为(1 – e^(-nk/SIZE))k，其中n为目标数据的数量，SIZE为Bit集合大小，k为使用的哈希函数个数；假设现有一千万条待处理数据，Bit集合大小为2^30（约10亿，即占用内存128MB），使用9个不同的哈希函数，计算可得任意两条数据其9次哈希得到的哈希值均相同（不考虑顺序）的概率为2.6e-10，约为38亿分之一。