带你一起来理解布隆过滤器，带图分析~

关于布隆过滤器，这个名词其实在我学 redis 不久后就知道了，但是对他没有一种很深刻的理解。

前言

首次听到布隆过滤器还是在Redis的缓存穿透的解决方案中看到的。

当时一直没有应用场景，就一直摆在那，也没仔细学。但是现在感觉不卷，已经快没有活路，所以又开始看起了面试题。

今天谈到的就是布隆过滤器，偏向于理论知识

卷又卷不动，躺又躺不平，麻了。

一、什么是布隆过滤器？

布隆过滤器，术语解释：它实际上是一个很长的二进制向量和一系列随机映射函数。主要用于判断一个元素是否在一个集合中。

二进制也就是0和1，这里判断某个元素是否存在集合中，0表示不存在，1代表存在。

你也可以简单理解为，他就是一个集合，然后可以通过一些定义好的方法，可以较为快速的判断出某个变量是否存在集合中。

在布隆过滤器中，判断为存在，实际上它是可能存在也可能不存在的，但是判断为不存在的数据，则一定是不存在的。

现在听起来还有些迷茫，稍后看分析，就会知道为什么是这样滴。

二、应用场景：

• Redis 的缓存穿透的一种解决方案
• 垃圾邮件过滤，对每一个发送邮件的地址进行判断是否在布隆的黑名单中，如果在就判断为垃圾邮件。
• 一般应用场景：在大量数据中，判断某个数据是否一定不存在或者可能存在。

三、简单的原理分析

我们平常在判断某个元素存不存在的时候，比较偏向于使用hashMap，因为它的key值是确定，当我们想要查找某个值时，只需要拿key直接获取即可，速度也是极快的。但是我们不得不考虑到，当数据量十分大的时候，内存的占用也变得极为险峻。

在这方面，布隆过滤器做的会更好一些，在查询速度和内存利用率上都优化不少。当然这也是利用了一定的误判率来换取空间。

（图片说明：存储过程）

流程解释：

1. 我现在要将 id = 10，存进布隆过滤器，

2. 首先要经过一个hash函数，

3. hash函数要求：

   1）hash出来的结果要处于数组存储范围之间

   2）hash出来的结果要尽可能的散列，以减少hash冲突的出现，提高效率，一个好的hash函数，可以说是布隆过滤器的关键部分。

4. id=10经过hash后的结果值，对应着数组中的下标，根据对应的下标，将数组中的零改为一。

到此刻，一个非常简单的往布隆过滤器中存储的过程就结束啦

查询过程：其实也是一样的，

---

思考思考，还存在哪些问题呢？

首先要明白一件事情，hash散列是会存在冲突的。

那么也就意味着，我id=10的值经过hash函数出来后的结果是3，我id=100的值经过hash出来的结果可能也还是3，但实际上，我根本没有往布隆过滤器中存过id=100的值，这就产生了误判。

布隆算法是由于存在hash碰撞，所以会导致误判。

这也对应了我上文提到了一句话：布隆过滤器判断一个值存不存在时，存在的有可能是不存在的，不存在的则一定不存在。

另外布隆过滤器的效率是通过一定的误判来换取空间的。

为什么说换取了空间呢？

因为bit数组十分的小，1个亿的bit数组，所占空间，还不足100MB~

四、如何降低hash碰撞的概率

1. 加大hash数组的长度

   hash数组的长度越长，就越不容易产生碰撞，这点很好理解哈~

2. 增加hash函数的个数

第二点来说明一下：

假设现在我的 bit 数组长度为100，我传入一个id=100给布隆过滤器，

以前经过一个hash函数就能判断一个值存不存在，现在变成了3个，那么相应的hash散列碰撞的概率也就降低了。

因为一个值的时候，产生碰撞的概率是1/100，变成3个之后，三个位置产生的碰撞的概率就变为1/100^3，三个都冲突，才会产生误判。

当然如果数据量变得更大的时候，误判量会相应变得更大，解决的方法也是继续扩大bit数组，这可以说是同时递增的。

4.1、合理的hash函数数量

还必须要说明的是，hash函数的数量并不是越多越好，而是一个合适的值。

请看下列说法：

1、假如你的bit数组的长度为10，然后你写了10个函数，每个都对应数组中的一个消标，那么误判率就没法想象了。

2、使用的越多的hash函数，计算时间和使用空间都要相应递增。如果hash较多，而数组范围较小，那么当数据一多，误判率将会增加的非常快。

所以，要根据大约的数据量，去决定hash函数数量以及bit数组的大小

到这个时候，我想大家应该已经明白，为什么我会说布隆算法说数据存在，实际上是可能存在也可能不存在，但是说数据不存在，那么就一定不存在的原因了吧。

因为如果说存在的时候，可能是发生的hash碰撞，并非是真的存在，但是如果说不存在，那么就代表数组中那个下标的值并没有改变过。

五、布隆过滤器存在的缺陷

这个弊端其实很容易想到，就是如果要删除数据的话，是会存在问题的。

上一小节也讲到了hash碰撞，bit数组中的一个下标中的1，它可能代表了不止一个数据，而是好几个数据，如果删除了，那么这几个依赖于这个数组下标的数据，都会直接判定为不存在。

一种取巧的方式就是利用计数器吧。

当执行删除操作时，判断一下那个数组下标中的计数器的值是否为0，为0就可以放心的删除~

感觉有那么一点不太优雅，，为了一层套上一层~