第 23 章 布隆过滤器

布隆过滤器实际上是一个很长的二进制向量和一系列随机映射函数。

布隆过滤器过滤垃圾邮件的工作原理：对于每一个电子邮件地址，用 8 个不同的随机数产生器产生 8 个信息指纹（f1，f2，...f8）。再用一个随机数产生器把这 8 个信息指纹映射到布隆过滤器的 8 个二进制位，并把这 8 个位置的二进制全部设置为 1 。

如果邮件在黑名单中，该邮件经过两次映射最终得到的 8 个二进制位都是 1 。

小结

布隆过滤器优点在于快速、省空间，但是有一定的误识别率。常见的办法是再建立一个小的白名单，存储那些有可能被误判的邮件地址。