通常我们会遇到很多要判断一个元素是否在某个集合中的业务场景，一般想到的是将集合中所有元素保存起来，然后通过比较确定。链表、树、散列表（又叫哈希表，Hash table）等等数据结构都是这种思路。但是随着集合中元素的增加，我们需要的存储空间也会呈现线性增长，最终达到瓶颈。同时检索速度也越来越慢，上述三种结构的检索时间复杂度分别为O(n), O(logn), O(1)。这个时候，布隆过滤器就应运而生。
布隆过滤器（Bloom Filter）是1970年由布隆提出的。布隆过滤器其实就是一个很长的二进制向量和一系列随机映射函数。可以用于快速检索一个元素是否在一个集合中出现的方法。
如果想判断一个元素是不是在一个集合里，我们一般想到的是将所有元素保存起来，然后通过比较确定。我们熟悉的链表，树等等数据结构都是这种思路。但是随着集合中元素的增加，我们需要的存储空间越来越大，检索速度也越来越慢。不过世界上还有一种叫作散列表（又叫哈希表）的数据结构。它可以通过一个Hash函数将一个元素映射成一个位阵列中的一个点。这样一来，我们只要看看这个点是不是 1 就知道可以集合中有没有它了。这其实就是布隆过滤器的基本思想。
Hash算法面临的问题就是hash冲突。假设 Hash 函数是良好的，如果我们的位阵列长度为 m 个点，那么如果我们想将冲突率降低到例如 1%, 这个散列表就只能容纳 m/100 个元素。显然这就不叫空间有效了（Space-efficient）。解决方法：就是使用多个 Hash算法，如果它们有一个说元素不在集合中，那肯定就不在。如果它们都说在，有一定可能性它们在说谎，虽然概率比较低。
算法：
首先需要k个hash函数，每个函数可以把key散列成为1个整数
初始化时，需要一个长度为n比特的数组，每个比特位初始化为0
某个key加入集合时，用k个hash函数计算出k个散列值，并把数组中对应的比特位置为1
判断某个key是否在集合时，用k个hash函数计算出k个散列值，并查询数组中对应的比特位，如果所有的比特位都是1，认为在