【实战问题】-- 缓存穿透之布隆过滤器（1）

前面我们提到，在防止缓存穿透的情况（缓存穿透是指，缓存和数据库都没有的数据，被大量请求，比如订单号不可能为-1，但是用户请求了大量订单号为-1的数据，由于数据不存在，缓存就也不会存在该数据，所有的请求都会直接穿透到数据库。）,我们可以考虑使用布隆过滤器，来过滤掉绝对不存于集合中的元素。

布隆过滤器是什么呢？

布隆过滤器（Bloom Filter）是由布隆（Burton Howard Bloom）在 1970 年提出的，它实际上是由一个很长的二进制向量和一系列随机 hash 映射函数组成（说白了，就是用二进制数组存储数据的特征）。可以使用它来判断一个元素是否存在于集合中，它的优点在于查询效率高，空间小，缺点是存在一定的误差，以及我们想要剔除元素的时候，可能会相互影响。

也就是当一个元素被加入集合的时候，通过多个 hash 函数，将元素映射到位数组中的 k 个点，置为 1。

为什么需要布隆过滤器？

一般情况下，我们想要判断是否存在某个元素，一开始考虑肯定是使用数组，但是使用数组的情况，查找的时候效率比较慢，要判断一个元素不存在于数组中，需要每次遍历完所有的元素。删除完一个元素后，还得把后面的其他元素往前面移动。

其实可以考虑使用hash表，如果有hash表来存储，将是以下的结构：

但是这种结构，虽然满足了大部分的需求，可能存在两点缺陷：

• 只有一个 hash 函数，其实两个元素 hash 到一块，也就是产生 hash 冲突的可能性，还是比较高的。虽然可以用拉链法（后面跟着一个链表）的方式解决，但是操作时间复杂度可能有所升高。

• 存储的时候，我们需要把元素引用给存储进去，要是上亿的数据，我们要将上亿的数据存储到一个 hash 表里面，不太建议这样操作。

对于上面存在的缺陷，其实我们可以考虑，用多个 hash 函数来减少冲突（注意：冲突时不可以避免的，只能减少），用位来存储每一个 hash 值。这样既可以减少 hash 冲突，还可以减少存储空间。

假设有三个 hash 函数，那么不同的元素，都会使用三个 hash 函数，hash 到三个位置上。

假设后面又来了一个张三，那么在 hash 的时候，同样会 hash 到以下位置，所有位都是 1，我们就可以说张三已经存在在里面了。

那么有没有可能出现误判的情况呢？这是有可能的，比如现在只有张三，李四，王五，蔡八，hash 映射值如下：

后面来了陈六，但是不凑巧的是，它 hash 的三个函数 hash 出来的位，刚刚好就是被别的元素 hash 之后，改成 1 了，判断它已经存在了，但是实际上，陈六之前是不存在的。

上面的情况，就是误判，布隆过滤器都会不可避免的出现误判。但是它有一个好处是，布隆过滤器，判断存在的元素，可能不存在，但是判断不存在的元素，一定不存在。，因为判断不存在说明至少有一位 hash 出来是对不上的。

也是由于会出现多个元素可能 hash 到一起，但有一个数据被踢出了集合，我们想把它映射的位，置为 0，相当于删除该数据。这个时候，就会影响到其他的元素，可能会把别的元素映射的位，置为了 0。这也就是为什么布隆过滤器不能删除的原因。

具体步骤

添加元素：

• 1. 使用多个 hash 函数对元素 item 进行 hash 运算，得到多个 hash 值。

• 2. 每一个 hash 值对 bit 位数组取模，得到位数组中的位置索引 index。

• 3. 如果 index 的位置不为 1，那么就将该位置为 1。

判断元素是否存在：

• 1. 使用多个 hash 函数对元素 item 进行 hash 运算，得到多个 hash 值。

• 2. 每一个 hash 值对 bit 位数组取模，得到位数组中的位置索引 index。

• 3. 如果 index 所处的位置都为 1，说明元素可能已经存在了。

误判率推导

庆幸的是，布隆过滤器的误判率是可以预测的，由上面的分析，也可以得知，其实是与位数组的大小，以及 hash 函数的个数等，这些都是息息相关的。

假设位数组的大小是 m，我们一共有 k 个 hash 函数，那么每一个 hash 函数，进行 hash 的时候，只能 hash 到 m 位中的一个位置，所以没有被 hash 到的概率是：

$$1-\frac{1}{m}$$

k 个 hash 函数都 hash 之后，该位还是没有被 hash 到 1 的概率是：

$$(1-\frac{1}{m})^k$$

如果我们插入了 n 个元素，也就是 hash 了 n*k 次，该位还是没有被 hash 成 1 的概率是：

$$(1-\frac{1}{m})^{kn}$$

那该位为 1 的概率就是：

$$1-(1-\frac{1}{m})^{kn}$$

如果需要检测某一个元素是不是在集合中，也就是该元素对应的 k 个 hash 元素 hash 出来的值，都需要设置为 1。也就是该元素不存在，但是该元素对应的所有位都被 hash 成为 1 的概率是：

$${(1-(1-\frac{1}{m})^{kn})}^{k}\approx {(1-e^{-kn/m})}^k $$

可以大致看出，随着位数组大小 m 和 hash 函数个数的增加，其实概率会下降，随着插入的元素 n 的增加，概率会有所上升。

最后也可以通过自己期待的误判率 P 和期待添加的个数 n，来大致计算出布隆过滤器的位数组的长度：

$$m=-(\frac{nInP}{(In2)^2})$$

上面就是误判率的大致计算方式，同时也提示我们，可以根据自己业务的数据量以及误判率，来调整我们的数组的大小。

布隆过滤器的作用

除了我们前面说的过滤爬虫恶意请求，还可以对一些 URL 进行去重，过滤海量数据里面的重复数据，过滤数据库里面不存在的 id 等等。

但是，即使有布隆过滤器，我们也不可能完全避免，或者彻底解决缓存穿透这个问题。只是相当于做了优化，将准确率提高。

很多的 key-value 数据库也会使用布隆过滤器来加快查询效率，因为全部挨个判断一遍，这个效率太低了。

【刷题笔记】

Github 仓库地址：https://github.com/Damaer/codeSolution

笔记地址：https://damaer.github.io/codeSolution/

【作者简介】：

秦怀，公众号【秦怀杂货店】作者，技术之路不在一时，山高水长，纵使缓慢，驰而不息。个人写作方向：Java 源码解析，JDBC，Mybatis，Spring，redis，分布式，剑指 Offer，LeetCode 等，认真写好每一篇文章，不喜欢标题党，不喜欢花里胡哨，大多写系列文章，不能保证我写的都完全正确，但是我保证所写的均经过实践或者查找资料。遗漏或者错误之处，还望指正。

2020年我写了什么？

开源刷题笔记

平日时间宝贵，只能使用晚上以及周末时间学习写作，关注我，我们一起成长吧~