抛砖引玉
假设遇到这样一个问题：
一个网站有 20 亿 url 存在一个黑名单中，这个黑名单要怎么存？
若此时随便输入一个 url，你如何快速判断该 url 是否在这个黑名单中？
并且需在给定内存空间（比如：500M）内快速判断出。
方案一
可能很多人首先想到的会是使用 HashSet，因为 HashSet基于 HashMap，理论上时间复杂度为：O(1)。
达到了快速的目的，但是空间复杂度呢？
URL字符串通过Hash得到一个Integer的值，Integer占4个字节，那20亿个URL理论上需要：
20亿*4/1024/1024/1024=7.45G的内存，不满足空间复杂度的要求。
方案二
可以初始化一个很长的一个Bit数组，将数值对应的Bit位置为true，然后根据是true还是false判断对应位置的数值是否存在。
例如现在有数值0、3、63，我们可以初始化一个长度为64的Bit数组，
将0、3、63置为true，然后通过get()方法查看对应位置的数值是否存在。
方案二局限
BitSet有两个比较局限的地方：
1.当样本分布极度不均匀的时候，BitSet会造成很大空间上的浪费。举个例子，比如你有5个数，分别是1、2、3、4、999，那么这个BitSet至少得有1000位，中间的位置很多就被浪费掉了。
2.BitSet只面向数字比较，并且还得是正数，其他类型需要先转换成int类型，但是转换过程中难免会出现重复，BitSet的准确性就会降低。
针对以上两个问题，解决思路就是：
分布不均匀的情况可以通过hash函数，将元素都映射到一个区间范围内，
减少大段区间闲置造成的浪费。然后可以把其他类型映射成整数，
映射时可以多hash几次同时扩大数组的范围，减少hash冲突的概率。
方案三
这里就引出本文要介绍的“布隆过滤器”。
首先说结论：
布隆过滤器判断某个元素存在，那么可能这个元素不存在，因为可能存在误判。
布隆过滤器判断某个元素不存在，那么这个元素一定不存在。
布隆过滤器（英语：Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制矢量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。
布隆过滤器的本质
布隆过滤器本质是一个位数组, 位数组就是数组的每个元素都只占用1bit 。
每个元素只能是 0 或者 1。
这样申请一个 10000 个元素的位数组只占用 10000 / 8 = 1250 B 的空间。
布隆过滤器除了一个位数组，还有 K 个哈希函数。
当一个元素加入布隆过滤器中的时候，会进行如下操作：
使用 K 个哈希函数对元素值进行 K 次计算，得到 K 个哈希值。
根据得到的哈希值，在位数组中把对应下标的值置为 1。
举个栗子：
布隆过滤器本质上是一个bit数组。
初始状态：
如果我们要映射一个值到布隆过滤器中，我们需要使用多个不同的哈希函数生成多个哈希值(假设为3个)，并对每个生成的哈希值指向的 bit 位置 1。例如针对值 “tianmao” 和三个不同的哈希函数分别生成了哈希值 1、3、5。
现在再存一个值 “tencent”，如果哈希函数返回 3、4、8。值得注意的是，3 这个 bit 位由于两个值的哈希函数都返回了这个 bit 位，因此它被覆盖了。
现在我们如果想查询 “zhongxing” 这个值是否存在，哈希函数返回了 1、2、8三个值，结果我们发现 2 这个 bit 位上的值为 0，说明没有任何一个值映射到这个 bit 位上，因此我们可以很确定地说 “zhongxing” 这个值不存在。
而当我们需要查询 “tianmao” 这个值是否存在的话，那么哈希函数必然会返回 1、3、5，然后我们检查发现这三个 bit 位上的值均为 1，那么我们可以说 “tianmao” 存在了么？答案是不可以，只能是 “tianmao” 这个值可能存在。这是为什么呢？因为随着增加的值越来越多，被置为 1 的 bit 位也会越来越多。比如某个值 “shanghai” 即使没有被存储过，但是万一哈希函数返回的三个 bit 位都被其他值置位了 1 ，那么程序还是会判断 “shanghai” 这个值存在。
优点
相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数（O(k)）。 散列函数相互之间没有关系，方便由硬件并行实现。 布隆过滤器不需要存储元素本身，在某些对内存要求非常严格的场合有优势。布隆过滤器可以表示全集，其它任何数据结构都不能； k和m相同，使用同一组散列函数的两个布隆过滤器的交并差运算可以使用位操作进行。
缺点
误算率。随着存入的元素数量增加，误算率随之增加。但是如果元素数量太少，则使用散列表足矣。一般情况下不能从布隆过滤器中删除元素. 我们很容易想到把位数组变成整数数组，每插入一个元素相应的计数器加1, 这样删除元素时将计数器减掉就可以了。然而要保证安全地删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面. 这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。 在降低误算率方面，有不少工作，使得出现了很多布隆过滤器的变种。
Redis中的布隆过滤器
使用场景
1、黑名单
2、URL去重(如爬取网页信息时)
3、单词拼写检查
4、Key-Value缓存系统的Key校验
5、ID校验，比如订单系统查询某个订单ID是否存在，如果不存在就直接返回。
6、Goolge在BigTable中就使用了BloomFilter，以避免在硬盘中寻找不存在的条目。
7、垃圾邮件过滤
场景举例
比如业务系统的用户状态查询接口，现在一个新用户过来了，它会先去缓存里查询有没有这个用户的状态数据。因为是新用户，所以肯定缓存里没有。然后它就要去查数据库，结果数据库也没有。如果这样的新用户大批量瞬间涌入，那么可以预见数据库的压力会比较大，会存在大量的空查询。
我们非常希望 Redis 里面有这样的一个 set，它存放了所有用户的 id，这样通过查询这个 set 集合就知道是不是新用户来了。当用户量非常庞大的时候，维护这样的一个集合需要的存储空间是很大的。这时候就可以使用布隆过滤器，它相当于一个 set，但是呢又不同于 set，它需要的存储空间要小的多。
比如你存储一个用户 id 需要 64 个字节，而布隆过滤器存储一个用户 id 只需要 1个字节多点。
但是呢它存的不是用户 id，而是用户 id 的指纹，所以会存在一定的小概率误判，它是一个具备模糊过滤能力的容器。
当它说用户 id 不在容器中时，那么就肯定不在。
当它说用户 id 在容器里时，99% 的概率下它是正确的，还有 1% 的概率它产生了误判。
不过在这个案例中，这个误判并不会产生问题，误判的代价只是缓存穿透而已。
相当于有 1% 的新用户没有得到布隆过滤器的保护直接穿透到数据库查询，
而剩下的 99% 的新用户都可以被布隆过滤器有效的挡住，避免了缓存穿透。
关于布隆过滤器元素删除问题的拓展：
布隆过滤器不支持直接删除元素的原因主要有以下几点：
- 空间效率：布隆过滤器的主要优势之一是其高效的空间利用率。它可以存储大量的元素，而只需要占用相对较小的内存空间。删除元素需要在位图中将相应的位设置为 0，这将导致误判率的增加，因为其他元素可能共享相同的位。
- 数据一致性：布隆过滤器是一种概率性数据结构，它可以返回元素“可能存在”或“一定不存在”的结果。由于误判率的存在，删除元素可能会导致误判结果的变化，从而影响到其他查询结果的准确性和一致性。为了保持布隆过滤器的可靠性和一致性，Redis 布隆过滤器限制了对元素的删除操作。
如何实现布隆过滤器删除？
布隆过滤器无法实现删除的理论上一节已经说了，为此，我们只能另辟捷径。计算机业界有一个很“伟大”的理论，那就是：加一层，没有什么技术难题是加一层解决不了的。
比如，已经删除的元素我们可以加一层 Set 缓存，彻底删除的数据可以加入到这个 Set 集合中。如果判断在布隆过滤器中存在，需要再去判断是否在 Set 集合，如果存在就证明元素存在。优点是可以满足删除元素后的复用问题，缺点是需要进行多次网络查询，以及删除要维护多个数据。
还有一种方法就是使用布谷鸟过滤器，可以实现元素的删除。