布隆过滤器
1、什么是布隆过滤器
布隆过滤器是1970年由布隆提出的。它实际上是一个很长的二进制向量（位数组）和一系列随机映射函数（哈希函数）。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。
2、布隆过滤器的原理
2.1、添加元素
将一个元素添加到布隆过滤器中：
- 使用布隆过滤器中的哈希函数对元素值进行计算，得到哈希值。
- 根据得到的哈希值，在位数组中把对应下标的值置为 1。
2.2、判断元素
判断一个元素是否在布隆过滤器中
- 使用布隆过滤器中的哈希函数对元素值进行计算，得到哈希值；
- 得到值之后判断位数组中对应下标位置的元素是否都为 1，如果值都为 1，那么说明这个值在布隆过滤器中，如果存在一个值不为 1，说明该元素不在布隆过滤器中。
2.3、示例
上图是一个由3个哈希函数和1个位数组组成的布隆过滤器。
当我们将w元素添加到布隆过滤器中时，首先使用三个哈希函数对w进行哈希运算，得到3个哈希值，然后再根据这3个哈希值将位数组中对应下标的值置1。
当我们判断w元素是否在布隆过滤器中时，同样使用这三个哈希函数对w进行同样的哈希运算，并根据3个哈希值判断位数组中对应位置的元素是否都为1，如果值都为1，说明w在布隆过滤器中；如果有一个不为1，说明该元素不在布隆过滤器中。
3、布隆过滤器的应用
- 判断给定数据是否存在：比如判断一个数字是否存在于包含大量数字的数字集中（数字集很大，5亿以上！）、 防止缓存穿透（判断请求的数据是否有效避免直接绕过缓存请求数据库）等等、邮箱的垃圾邮件过滤、黑名单功能等等。
- 去重：比如爬给定网址的时候对已经爬取过的 URL 去重。
4、布隆过滤器的优缺点
4.1、优点
相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数。另外，散列函数相互之间没有关系，方便由硬件并行实现。布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。
4.2、缺点
4.2.1、存在误判
如果两个元素的哈希运算结果完成相同，会导致出现误判。
例如：
对于一个给定的布隆过滤器，“我”和“me”的哈希运算值完全相同。当布隆过滤器中只存了”我”，那么判断”me“是否在布隆过滤器中时，会判断出”me“存在集合中。
4.2.2、删除困难
两个元素经过布隆过滤器的哈希运算以后可能会有一些哈希值相同，这会导致我们删除一个元素的同时（将位数组中哈希值对应下标全部置为0），会删除另一个元素。
例如：
对于一个给定的布隆过滤器，“我”和“me”的哈希运算值中都有2。当布隆过滤器中保存了”我”和”me”，那么我们删除“me”时，会将位数组中下标为2的值置0，这会导致”我“也被删除了。
