在日常生活中包括在设计计算机软件Software时我们经常要判断个元素是否在个集合中比如在字处理软件Software中需要检查个英语单词是否拼写正确(也就是要判断它是否在已知字典中)；在 FBI个嫌疑人名字是否已经在嫌疑名单上；在网络爬虫里个网址是否被访问过等等最直接思路方法就是将集合中全部元素存在计算机中遇到个新元素时将它和集合中元素直接比较即可般来讲计算机中集合是用哈希表(hash table)来存储它好处是快速准确缺点是费存储空间当集合比较小时这个问题不显著但是当集合巨大时哈希表存储效率低问题就显现出来了比如说个象 Yahoo,Hotmail 和 Gmai 那样公众电子邮件(email)提供商总是需要过滤来自发送垃圾邮件人(spamer)垃圾邮件个办法就是记录下那些发垃圾邮件 email 地址由于那些发送者不停地在注册新地址全世界少说也有几十亿个发垃圾邮件地址将他们都存起来则需要大量网络服务器如果用哈希表每存储亿个 email 地址 就需要 1.6GB 内存(用哈希表实现具体办法是将每个 email 地址对应成个 8字节信息指纹然后将这些信息指纹存入哈希表由于哈希表存储效率般只有 50%因此个 email 地址需要占用十 6个字节亿个地址大约要 1.6GB 即十 6亿字节内存)因此存贮几十亿个邮件地址可能需要上百 GB 内存除非是超级计算机般服务器是无法存储

　　今天我们介绍种称作布隆过滤器数学工具它只需要哈希表 1/8 到 1/4 大小就能解决同样问题

　　布隆过滤器是由巴顿.布隆于 9 7零年提出它实际上是个很长 2进制向量和系列随机映射我们通过上面例子来介绍说明起工作原理

　　假定我们存储亿个电子邮件地址我们先建立个十 6亿 2进制(比特)即两亿字节向量然后将这十 6亿个 2进制全部设置为零对于每个电子邮件地址 X我们用 8个区别随机数产生器(F1,F2, ...,F8) 产生 8个信息指纹(f1, f2, ..., f8)再用个随机数产生器 G 把这 8个信息指纹映射到 1 到十 6亿中 8个自然数 g1, g2, ...,g8现在我们把这 8个位置 2进制全部设置为当我们对这亿个 email 地址都进行这样处理后个针对这些 email 地址布隆过滤器就建成了(见下图)



　　现在让我们看看如何用布隆过滤器来检测个可疑电子邮件地址 Y 是否在黑名单中我们用相同 8个随机数产生器(F1, F2, ..., F8)对这个地址产生 8个信息指纹 s1,s2,...,s8然后将这 8个指纹对应到布隆过滤器 8个 2进制位分别是 t1,t2,...,t8如果 Y 在黑名单中显然t1,t2,..,t8 对应 8个 2进制定是这样在遇到任何在黑名单中电子邮件地址我们都能准确地发现

　　布隆过滤器决不会漏掉任何个在黑名单中可疑地址但是它有条不足的处也就是它有极小可能将个不在黑名单中电子邮件地址判定为在黑名单中有可能某个好邮件地址正巧对应个 8个都被设置成 2进制位好在这种可能性很小我们把它称为误识概率在上面例子中误识概率在万分的以下

　　布隆过滤器好处在于快速省空间但是有定误识别率常见补救办法是在建立个小白名单存储那些可能别误判邮件地址