针对上面缓存穿透的解决方案，我们思考一下：假如一个`key`可以绕过第`1`种方法的校验，而此时有大量的不存在`key`被访问（如`1`亿个或者`10`亿个），那么这时候全部存储到内存中，是不太现实的。 那么有没有一种更好的解决方案呢？这就是我们接下来要介绍的布隆过滤器，布隆过滤器就可以用尽可能小的空间存储尽可能多的数据。 #### 什么是布隆过滤器 布隆过滤器（Bloom Filter）是由布隆在`1970`年提出的。它实际上是一个很长的二进制向量（位图）和一系列随机映射函数（哈希函数）。 布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率而且删除困难。 #### 位图（Bitmap） `Redis`当中有一种数据结构就是位图，布隆过滤器其中重要的实现就是位图的实现，也就是位数组，并且在这个数组中每一个位置只有`0`和`1`两种状态，每个位置只占用`1`个 bit，其中`0`表示没有元素存在，`1`表示有元素存在。 如下图所示就是一个简单的布隆过滤器示例（**一个`key`值经过哈希运算和位运算就可以得出应该落在哪个位置**）：  #### 哈希碰撞 上面我们发现，`lonely`和`wolf`落在了同一个位置，这种不同的`key`值经过哈希运算后得到相同值的现象就称之为**哈希碰撞**。发生哈希碰撞之后再经过位运算，那么最后肯定会落在同一个位置。 如果发生过多的哈希碰撞，就会影响到判断的准确性，所以为了减少哈希碰撞，我们一般会综合考虑以下`2`个因素： * 增大位图数组的大小（位图数组越大，占用的内存越大）。 * 增加哈希函数的次数（同一个`key`值经过`1`个函数相等了，那么经过`2`个或者更多个哈希函数的计算，都得到相等结果的概率就自然会降低了）。 上面两个方法我们需要综合考虑：比如增大位数组，那么就需要消耗更多的空间，而经过越多的哈希计算也会消耗`cpu`影响到最终的计算时间，所以位数组到底多大，哈希函数次数又到底需要计算多少次合适需要具体情况具体分析。