关于布隆过滤器，这个名词其实在我学 redis 不久后就知道了，但是对他没有一种很深刻的理解。
前言
首次听到布隆过滤器还是在Redis的缓存穿透的解决方案中看到的。
当时一直没有应用场景，就一直摆在那，也没仔细学。但是现在感觉不卷，已经快没有活路，所以又开始看起了面试题。
今天谈到的就是布隆过滤器，偏向于理论知识
卷又卷不动，躺又躺不平，麻了。
一、什么是布隆过滤器？
布隆过滤器，术语解释：它实际上是一个很长的二进制向量和一系列随机映射函数。主要用于判断一个元素是否在一个集合中。
二进制也就是0和1，这里判断某个元素是否存在集合中，0表示不存在，1代表存在。
你也可以简单理解为，他就是一个集合，然后可以通过一些定义好的方法，可以较为快速的判断出某个变量是否存在集合中。
在布隆过滤器中，判断为存在，实际上它是可能存在也可能不存在的，但是判断为不存在的数据，则一定是不存在的。
现在听起来还有些迷茫，稍后看分析，就会知道为什么是这样滴。
二、应用场景：
- Redis 的缓存穿透的一种解决方案
- 垃圾邮件过滤，对每一个发送邮件的地址进行判断是否在布隆的黑名单中，如果在就判断为垃圾邮件。
- 一般应用场景：在大量数据中，判断某个数据是否一定不存在或者可能存在。
三、简单的原理分析
我们平常在判断某个元素存不存在的时候，比较偏向于使用
hashMap，因为它的key值是确定，当我们想要查找某个值时，只需要拿key直接获取即可，速度也是极快的。但是我们不得不考虑到，当数据量十分大的时候，内存的占用也变得极为险峻。
在这方面，布隆过滤器做的会更好一些，在查询速度和内存利用率上都优化不少。当然这也是利用了一定的误判率来换取空间。
（图片说明：存储过程）
流程解释：
- 我现在要将 id = 10，存进布隆过滤器，
- 首先要经过一个hash函数，
- hash函数要求：
1）hash出来的结果要处于数组存储范围之间
2）hash出来的结果要尽可能的散列，以减少hash冲突的出现，提高效率，一个好的hash函数，可以说是布隆过滤器的关键部分。 - id=10经过hash后的结果值，对应着数组中的下标，根据对应的下标，将数组中的零改为一。
到此刻，一个非常简单的往布隆过滤器中存储的过程就结束啦
查询过程：其实也是一样的，
思考思考，还存在哪些问题呢？
首先要明白一件事情，hash散列是会存在冲突的。
那么也就意味着，我id=10的值经过hash函数出来后的结果是3，我id=100的值经过hash出来的结果可能也还是3，但实际上，我根本没有往布隆过滤器中存过id=100的值，这就产生了误判。
布隆算法是由于存在hash碰撞，所以会导致误判。
这也对应了我上文提到了一句话：布隆过滤器判断一个值存不存在时，存在的有可能是不存在的，不存在的则一定不存在。
另外布隆过滤器的效率是通过一定的误判来换取空间的。
为什么说换取了空间呢？
因为bit数组十分的小，1个亿的bit数组，所占空间，还不足100MB~
四、如何降低hash碰撞的概率
- 加大hash数组的长度
hash数组的长度越长，就越不容易产生碰撞，这点很好理解哈~ - 增加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就可以放心的删除~
感觉有那么一点不太优雅，，为了一层套上一层~
后记
今天文章就到这里啦~
