Intro

How do you implement the blacklist of the mail system?

布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。

Bloom filter theory

当一个元素加入布隆过滤器中的时候，会进行如下操作：

• 使用布隆过滤器中的哈希函数对元素值进行计算，得到哈希值（有几个哈希函数得到几个哈希值）。
• 根据得到的哈希值，在位数组中把对应下标的值置为 1。

当我们需要判断一个元素是否存在于布隆过滤器的时候，会进行如下操作：

• 对给定元素再次进行相同的哈希计算；
• 得到值之后判断位数组中的每个元素是否都为 1，如果值都为 1，那么说明这个值在布隆过滤器中，如果存在一个值不为 1，说明该元素不在布隆过滤器中。

To sum up, 布隆过滤器说某个元素存在，小概率会误判(Hash碰撞)。布隆过滤器说某个元素不在，那么这个元素一定不在。布隆过滤器能够说明某个东西一定不存在!

Usage

1. 判断给定数据是否存在：
   • 比如判断一个数字是否存在于包含大量数字的数字集中（数字集很大，5 亿以上！);
   • 防止缓存穿透（判断请求的数据是否有效避免直接绕过缓存请求数据库）等等;
   • 邮箱的垃圾邮件过滤、黑名单功能等等。
2. 去重：比如爬给定网址的时候对已经爬取过的 URL 去重。

Implementation

如果你想要手动实现一个的话，你需要：

1. 一个合适大小的位数组保存数据;
2. 几个不同的哈希函数;
3. 添加元素到位数组（布隆过滤器）的方法实现;
4. 判断给定元素是否存在于位数组（布隆过滤器）的方法实现。