简介
布隆过滤器，Bloom Filter是1970年由Bloom提出的，它是由一组哈希（Hash）函数和一个位阵列组成。布隆过滤器可以用于查询一个元素是否存在于一个集合当中，查询结果为以下二者之一：
- 这个元素可能存在于这个集合当中。
- 这个元素一定不存在于这个集合当中。
布隆过滤器的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。
布隆过滤器在实际中主要用来解决网页URL去重复，垃圾邮件检测，大集合中重复元素判断和缓存击穿等问题。
设计原理
如果想判断一个元素是不是在一个集合里，一般想到的是将所有元素保存起来，然后通过比较确定。链表，树等等数据结构都是这种思路. 但是随着集合中元素的增加，我们需要的存储空间越来越大，检索速度也越来越慢(O(n),O(logn))。
这时候我们可以利用哈希表这种数据结构，基于哈希函数的特性，它在理想情况下(不发生哈希冲突)，检索速度可以达到O(1)。一张哈希表的示意图如下所示：
哈希函数是这样的：
这里的hashcode就是哈希桶的索引，如何哈希函数H足够完美，那么每个key就会对应一个唯一的hashcode，但实际上往往会出现哈希冲突，即两个不同的key对应同一个hashcode，如下图所示，“John Smith” 和 “Sandra Dee” 经过哈希之后得到了相同的哈希值“02”。
布隆过滤器使用了上面的思路，即利用哈希表这个数据结构，通过一个Hash函数将一个元素映射成一个位阵列（Bit array）中的一个点（每个点只能表示0或者1），这样一来，我们只要看看这个点是不是1就知道在集合中有没有它了。这就是Bloom Filter的基本思想。
但是在哈希冲突的情况下，我们无法使用一个哈希函数来判断一个元素是否存在于集合之中，解决方法也简单，就是使用多个哈希函数，如果其中有一个哈希函数判断该元素不在集合中（元素经过Hash之后映射在位阵列中的点为0），那肯定就不在。如果它们都判断存在，那也有一定可能性它们都在说谎，不过这要比只用一个哈希函数来判断“一个元素存在于集合之中”的可靠性要高很多。这种多个Hash组成的数据结构就叫Bloom Filter。
一个Bloom Filter是基于一个m位的位阵列（b1,…bm），这些位阵列的初始值为0。另外，还有一系列的hash函数（h1,…hk），这些hash函数的值域属于1~m。下图是一个bloom filter插入x,y,z并判断某个值w是否在该数据集的示意图：
上图中，m=18，k=3；
插入x时，三个hash函数分别得到蓝线对应的三个值，并将对应的位向量改为1，插入y，z时，类似的，分别将红线，紫线对应的位向量改为1。
查找时，当查找x时，三个hash值对应的位向量都为1，因此判断x在此数据集中。y，z也是如此。但是当查找w时，w有个hash值对应的位向量为0，因此可以判断不在此集合中。但是，假如w的最后那个hash值比上图中的大1，这是就会认为w在此集合中，而事实上，w可能不在此集合中，因此可能出现误报。显然的，插入数据越多，1的位数越多，误报的概率越大。
产生误报的原因是由于哈希碰撞导致的巧合而将不同的元素存储在相同的比特位上。幸运的是，布隆过滤器有一个可预测的误判率（FPP）：
n 是已经添加元素的数量；
k 哈希的次数；
m 布隆过滤器的长度（如比特数组的大小）；
极端情况下，当布隆过滤器没有空闲空间时（满），每一次查询都会返回 true 。这也就意味着 m 的选择取决于期望预计添加元素的数量 n ，并且 m 需要远远大于 n 。
实际情况中，布隆过滤器的长度 m 可以根据给定的误判率（FFP）的和期望添加的元素个数 n 的通过如下公式计算：
对于 m/n 比率表示每一个元素需要分配的比特位的数量，也就是哈希函数 k 的数量可以调整误判率。通过如下公式来选择最佳的 k 可以减少误判率（FPP）：
了解完上述的内容之后，我们可以得出一个结论，当我们搜索一个值的时候，若该值经过 K 个哈希函数运算后的任何一个索引位为 ”0“，那么该值肯定不在集合中。但如果所有哈希索引值均为 ”1“，则只能说该搜索的值可能存在集合中。
