布隆过滤器-蒲公英云

前述：

概述：

1.结构：

2.特点：

3.为什么要用它？

详述：

1.存储原理：

2.查询原理

问题

1.可能存在？

2.一定不存在？

使用：

1.防止redis穿透

2.防止恶意链接或者垃圾邮件，短信之类

3.检索系统查询当前的输入信息是否存在于数据库中

4.总之

总结：

前述：
最近在深入了解redis时，提到了在遇到redis穿透问题时，可以利用布隆过滤器进行判断，所以对布隆过滤器进行了了解与认识，在这里进行记录与分享

概述：
1.结构：
是一种数据结构，一种概率型数据结构，结构为：bit向量或者说bit数组

2.特点：
空间占用率很低！较高效的查询与插入。不支持删除！有一定的误报率(概率很低)！查询结果有两种：一定不存在！或者可能存在！

3.为什么要用它？
之所以叫过滤器，所以最重要的就是查询！
那为什么不用hashmap呢？而且时间复杂度为O(1)，效率高。但是！占内存啊！

详述：
1.存储原理：
(1.)准备一个布隆过滤器(bit数组)，初始所有值为0，一个要存储的值：baidu，3个不同的hash函数：hash1，hash2，hash3

(2.)我们使用这3个hash函数，分别对”baidu”进行计算，得出：1，4，7这个三个哈希值，我们将这三个哈希值匹配到bit数组对应的位置上，将该位置的值变为1，意味着该位置存在该哈希值。

(3.)此时，我们已经完成了布隆过滤器的存储工作！
可以看到工作原理为：我们将要存储的值通过n个hash函数计算，取得哈希值，将布隆过滤器中对应的哈希值位置上的值变更为1，以表示该哈希值已存在。
其中n是可变的，我们可以根据布隆过滤器数组的长度，我们存储数据的个数来决定hash函数的多少。

2.查询原理
(1.)也就是如何使用布隆过滤器，我们现在要判断”baidu”是否存在

(2.)根据上面同样的方式，使用固定的hash算法，对要查询的值”baidu”进行计算，取得哈希值

(3.)然后去布隆过滤器(bit数组)内查询指定的哈希值位置是否均为1，如果均为1，则可能存在，否则一定不存在！

问题
1.可能存在？
(1.)是的，可能存在！因为随着存储数量的增多，布隆过滤器(bit数组)内，越来越多的哈希值对应的值变为1，那么我们使用多个hash算法对某个值计算后，可能对应的值已经为1，但其实它不存在，所以存在一定的误报率！但概率很低
(2.)举个例子：
有一亿个用户，
使用hashmap来存储：一个用户名为4个汉字，一个汉字占用2个字节（Unicode情况下），一共有八亿个字节。一共占用763M的内存（这个里面不包括对象占用的空间，也不包括哈希表中浪费的空间），而实际情况占用的空间会比这个多得多。
使用布隆过滤器：在我们保证误报率为0.01%的情况下，我们需要大概19亿位的空间来保存数据（大约是230M的空间）。其中需要的hash函数的个数为13。而如果要稳定误报率：存储的用户数量n，与bit数组的长度k，要线性增加或减少。具体推导公式可参考这篇文章：https://www.cnblogs.com/xiaohuiduan/p/11488020.html

(3.)所以综合空间占用率，执行效率来看，布隆过滤器在特定场景下，确实有独到之处！

2.一定不存在？
(1.)是的，如果去布隆过滤器内查询，不是所有的哈希值存在(即所有的值为1)，则该查询的值一定不存在！

使用：
1.防止redis穿透
redis穿透：攻击者恶意使用不存在的用户信息进行登陆，导致大量频繁的透过redis访问db。
所以，利用布隆过滤器的”一定不存在“：对每个已存在的用户key信息放入布隆过滤器，当攻击者使用不存在的用户信息登陆时，先利用布隆过滤器判断是否存在，如一定不存在，则直接返回。

2.防止恶意链接或者垃圾邮件，短信之类
从数十亿个链接或者垃圾邮件中判断该链接（邮件发件人，短信发信人是否是在黑名单中），
平时手机上来电提示写着对方式恶意推销，外卖，这种场景也是可以用布隆过滤器来判断

3.检索系统查询当前的输入信息是否存在于数据库中
可以作为检索工具，判断是否存在，也是极为高效的方法与工具！

4.总之
就是利用布隆过滤器高效的查询功能，应对我们业务场景中需要判断是否存在的场景

总结：
redis最近了解了很长时间，以前顶多是使用，觉着redis就set，get得了，还能有啥问题。
通过不断深入的了解，发现随着用户量的增大，原本平时遇不到的问题，都会随之出现，与之伴随的就是相应的技术解决方案，深入进去，了解其中缘由，你会发现原来是这么回事。
最终构成自己对技术理解的体系。

以上都是自己结合网上所查阅的博客资料总结的，如果有疑问或者不严谨之处，真诚的希望可以留言，一起交流！

参考：
https://segmentfault.com/a/1190000019227651?utm_source=tag-newest
https://www.cnblogs.com/xiaohuiduan/p/11488020.html
https://www.jianshu.com/p/2104d11ee0a2