Redis布隆过滤器 _Redis

场景在项目开发中，我们经常会遇到去重问题。比如：判断一个人有没有浏览过一篇文章，判断一个人当天是否登录过某个系统，判断一个ip是否发过一个请求，等等。
比较容易想到的是使用set来实现这个功能。但如果数据量较大，使用set会非常消耗内存，性能也不高。在前面的文章中，我们介绍了一种数据结构：BitMap来提高性能。但BitMap仍然比较消耗内存，尤其是在数据比较稀疏的情况下，使用BitMap并不划算。
实际上，对于“去重”问题，业界有另外一个更优秀的数据结构来解决这类问题，那就是——布隆过滤器(BloomFilter) 。
原理【Redis布隆过滤器】布隆过滤器与BitMap类似，底层也是一个位数组。1表示有， 0表示无。但布隆过滤器比BitMap需要更少的内存，它是怎么办到的呢？答案是多个hash 。
我们知道hash算法，是把一个数从较大范围的值，映射到较小范围值。比如我们有一个10位的数组，使用某个hash算法及其数组上的表示：

hash(“xy”) = 3;
hash(“技术圈”) = 5;
0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0

这样，我们使用这个hash算法就能快速的判断一个字符串是不是存在一个集合里面了。但众所周知， hash算法是有可能发生hash冲突的。比如可能有两个不同的字符串映射到同一个数：

hash(“xy”) = 3;
hash(“xy的技术圈”) = 3;

这种情况下，就不能准确得判断出某个字符串是不是存在于集合之中呢。
那怎么解决这个问题呢？答案是使用多个不同的hash算法。比如：

h1(“xy”) = 3, h2(“xy”) = 5, h3(“xy”) = 7;
h1(“技术圈”) = 5, h2(“技术圈”) = 6, h3(“技术圈”) = 7;
h1(“xy的技术圈”) = 3, h2(“xy的技术圈”) = 6, h3(“xy的技术圈”) = 9;

最开始，集合里没有元素，所有位都是0：

0, 0, 0, 0, 0, 0, 0, 0, 0, 0

然后，插入“xy” ，利用多次hash ，把每次hash的结果下标3, 5, 7都插入到相应的地方：

0, 0, 0, 1, 0, 1, 0, 1, 0, 0

然后，插入“技术圈” ，利用多次hash ，把每次hash的结果下标5, 6, 7都插入到相应的地方，已经是1的下标不变：

0, 0, 0, 1, 0, 1, 1, 1, 0, 0

这个时候，如果想要判断“xy”是否在集合中，只需要使用同样的3个hash算法，来计算出下标是3, 5, 7 ，发现这3个下标都为1 ，那么就认为“xy”这个字符串在集合中。而“xy的技术圈”计算出来的下标是3 ， 6 ， 9 。发现这三个下标有不是1的地方，比如下标为9的地方是0 ，那就说明“xy的技术圈”这个字符串还不在集合中。
误差从原理可以看得出来，布隆过滤器是有可能存在一定的误差的。尤其是当hash函数比较少的时候。布隆过滤器是根据多次hash计算下标后，数组的这些下标是否都为1来判断这个元素是否存在的。所以是存在一定的几率，要检查的元素实际上没有插入，但被其它元素插入影响，导致所有下标都为1 。
所以布隆过滤器不能删除，因为一旦删除（即将相应的位置为0），就很大可能会影响其他元素。
如果使用布隆过滤器判断一个函数是否存在于一个集合，如果它返回true ，则代表可能存在。如果它返回false ，则代表一定不存在。
由此可见，布隆过滤器适合于一些需要去重，但不一定要完全精确的场景。比如：