Redis系列之 ——Bloom(布隆过滤器)

Tip：假如生活欺骗了你，你能咋滴…
我是小刀，在互联网中夹缝求生的一颗螺丝我希望你开心…

Redis系列之 ——Bloom（布隆过滤器）

开篇简介

我们的业务中经常会遇到穿库的问题，面试中问的也比较多，通常可以通过缓存解决。将这个key的值置为0存入缓存不就行了吗？确实，这是一个好的方案。大部分情况我们都是这样做的，当访问一个不存在的key的时候，设置一个带有过期时间的标志，然后放入缓存。不过这样做的缺点也很明显，浪费内存和无法抵御随机key攻击。并且如果数据维度比较多，结果数据集合比较大时，缓存的效果就不明显了。因此为了解决穿库的问题，我们可以引入Bloom Filter。还有好多场景也可以用到：爬虫URL去重，推荐系统避免重复推送，邮箱系统的垃圾邮件过滤等场景中，用起来也是特别香。

布隆过滤器原理

每个布隆过滤器对应到Redis的数据结构中就是一个大型的位数组和几个不同的无偏hash函数，无偏表示分布均匀。添加key时，使用多个hash函数对key进行hash运算得到一个整数索引值，对位数组长度进行取模运算得到一个位置，每个hash函数都会得到一个不同的位置，将这几个位置都置1就完成了add操作。查询同理，只要有一位是0就表示这个key不存在，但如果都是1，则不一定存在对应的key。
Redis系列之 ——Bloom(布隆过滤器)

布隆过滤器处理流程

开辟空间：开辟一个长度为m的位数组（或者称二进制向量），这个不同的语言有不同的实现方式。

寻找hash函数：获取几个hash函数，前辈们已经发明了很多运行良好的hash函数，比如BKDRHash，JSHash，RSHash等等。直接获取就可以了。

写入数据：将所需要判断的内容经过这些hash函数计算，得到几个值，比如用3个hash函数，得到值分别是1000，2000，3000。之后设置m位数组的第1000，2000，3000位的值位二进制1。

判断：接下来就可以判断一个新的内容是不是在我们的集合中。

穿库问题解决：

Redis系列之 ——Bloom(布隆过滤器)

误判问题

布隆过滤器虽然很高效（写入和判断都是O(1)，所需要的存储空间极小），但是缺点也非常明显，那就是会误判。当集合中的元素越来越多，二进制序列中的1的个数越来越多的时候，判断一个字符串是否在集合中就很容易误判，原本不在集合里面的字符串会被判断在集合里面。但是当布隆过滤器说某个值存在时，这个值可能不存在；当它说不存在时，那就肯定不存在。我们可以理解为一个不怎么精确的 set 结构，但是布隆过滤器也不是特别不精确，只要参数设置的合理，它的精确度可以控制的相对足够精确，只会有小小的误判概率。