> For the complete documentation index, see [llms.txt](https://chenjunren.gitbook.io/read-the-beauty-of-mathematics/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://chenjunren.gitbook.io/read-the-beauty-of-mathematics/di-23-zhang-bu-long-guo-lv-qi.md).

# 第 23 章 布隆过滤器

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

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

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

## 小结

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