在信息指纹那篇文章我们提到，使用哈希时，利用信息指纹将字符串转为128位整数既可以降低内存需耗，又可以节省查找时间；但是如果要处理的信息量特别大时，哈希表存储效率低的问题就显现出来了，此时就需要考虑其他数据结构了：Bloom Filter。
什么是布隆过滤器？为什么要使用布隆过滤器？
我们经常会遇到要判断一个元素是否在一个集合中这样的问题，例如以下情景：
- 字处理软件中，需要检查一个英语单词是否拼写正确（也就是要判断它是否在已知的字典中）
- 网络爬虫里，一个网址是否被访问过等等 最直接的方法就是将集合放入内存，使用哈希的方法，好处是快速、准确；缺点是费空间。请注意，这件事情是在内存中完成的，所以空间问题必须作为考虑因素。当要哈希的集合比较小时，这个问题不显著，但是当集合巨大时，对于有限的内存来说，哈希表存储效率低的问题就显现出来了，这里借数学之美中的案例说明一下bloom Filter的思想及使用它的必要性：
Yahoo,Hotmail 和 Gmai 那样的公众电子邮件（email）提供商，总是需要过滤来自发送垃圾邮件的人（spamer）的垃圾邮件。一个办法就是记录下那些发垃圾邮件的 email 地址，全世界少说也有几十亿个发垃圾邮件的地址。如果用哈希表，每存储一亿个 email 地址， 就需要 1.6GB 的内存（十亿字节为1G。用哈希表实现的具体办法是将每一个 email 地址对应成一个八字节的信息指纹，然后将这些信息指纹存入哈希表，由于哈希表的存储效率一般只有 50%，因此一个 email 地址需要占用十六个字节。一亿个地址大约要 1.6GB， 即十六亿字节的内存）。因此存贮几十亿个邮件地址可能需要上百 GB 的内存，一般服务器是无法存储的。
一种称作布隆过滤器的数学工具，它只需要哈希表 1/8 到 1/4 的大小就能解决同样的问题。
布隆过滤器实际上是一个很长的二进制向量和一系列随机映射函数。
按我的理解：说白了，bloom filter就是将集合元素进行位编码存储。
我们通过上面的例子来说明其工作原理：假定我们存储一亿个电子邮件地址
我们先建立一个十六亿二进制（比特），即两亿字节的向量（200M），然后将这十六亿个二进制全部设置为零。对于每一个电子邮件地址 X，我们用八个不同的随机数产生器（F1,F2, ...,F8） 产生八个信息指纹（f1, f2, ..., f8）。再用一个随机数产生器 G 把这八个信息指纹映射到 1 到十六亿中的八个自然数 g1, g2, ...,g8。现在我们把这八个位置的二进制全部设置为1。这便是布隆过滤器的思想，见下图。注意：传统哈希利用信息指纹时，一个email地址需要十六个字节，哈希一个格子一个格子存储共需要十六亿字节；而使用bloom filter，采用位存储，一个email这里假设需要十六位（bit），位编码共需两亿字节，空间可谓大大缩小了。
如何用布隆过滤器来检测一个可疑的电子邮件地址 Y 是否在黑名单中。我们用相同的八个随机数产生器（F1, F2, ..., F8）对这个地址产生八个信息指纹 s1,s2,...,s8，然后将这八个指纹对应到布隆过滤器的八个二进制位，分别是 t1,t2,...,t8。如果 Y 在黑名单中，显然，t1,t2,..,t8 对应的八个二进制一定是1。
原理说白了很简单，用位数组和k个不同的HASH函数。将HASH函数对应的值的位数组置1，查找时如果发现所有HASH函数对应位都是1说明存在。
布隆过滤器决不会漏掉任何一个在黑名单中的可疑地址。但是，它有一条不足之处。也就是它有极小的可能将一个不在黑名单中的电子邮件地址判定为在黑名单中，因为有可能某个好的邮件地址正巧对应八个都被设置成一的二进制位。好在这种可能性很小。我们把它称为误识概率。
总结：
布隆过滤器就是一种位存储，它的好处在于快速，省空间（解决传统哈希费空间的缺点）。但是有一定的误识别率。
Bloom Filter 蕴含了一种“正确率换空间”的思想，不但如此，它完全摆脱了传统哈希的那种使用一个哈希函数并将每个元素只映射到一个格子的存储方法， Bloom Filter 更像是对集合元素的一种位编码，它同时使用若干个独立的哈希函数对集合元素进行编码，将每一个哈希函数映射的地址都置为1。这种编码方法可谓是另辟蹊径。我们知道，在数据压缩中，编码位数是和正确率交换的筹码，因此，在Bloom Filter中，与正确率交换的筹码就变成了哈希函数的个数以及整个哈希区域（即位数组）的大小。
本文参考文献：