本文由 简悦 SimpRead 转码， 原文地址 www.toutiao.com
关注公众号：xy 的技术圈场景在项目开发中，我们经常会遇到去重问题。比如：判断一个人有没有浏览过一篇文章，判断一个人当天是否登录过某个系统，判断一
关注公众号：xy 的技术圈
在项目开发中，我们经常会遇到去重问题。比如：判断一个人有没有浏览过一篇文章，判断一个人当天是否登录过某个系统，判断一个 ip 是否发过一个请求，等等。
比较容易想到的是使用 set 来实现这个功能。但如果数据量较大，使用 set 会非常消耗内存，性能也不高。在前面的文章中，我们介绍了一种数据结构：BitMap 来提高性能。但 BitMap 仍然比较消耗内存，尤其是在数据比较稀疏的情况下，使用 BitMap 并不划算。
实际上，对于 “去重” 问题，业界有另外一个更优秀的数据结构来解决这类问题，那就是——布隆过滤器 (BloomFilter) 。
布隆过滤器与 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，则代表一定不存在。
由此可见，布隆过滤器适合于一些需要去重，但不一定要完全精确的场景。比如：
- 判断一个用户访问了一篇文章
- 判断一个 ip 访问了本网站
- 判断一个 key 是否被访问过
相应的，布隆过滤器不适合一些要求零误差的场景，比如：
- 判断一个用户是否收藏了一篇文章
- 判断一个用户是否订购了一个课程
这就是布隆过滤器的基本原理。由上面的例子可以看出来，如果空间越大，hash 函数越多，结果就越精确，但空间效率和查询效率就会越低。
这里有一个测试数据：
后面 4 列中的数据就是发生误差的数量。可见，空间大小和集合大小不变的情况下，增加 hash 函数可以显著减小误差。但一旦集合大小达到空间大小的 25% 左右后，增加 hash 函数带来的提神效果并不明显。这个时候应该增加空间大小。
Redis 中的布隆过滤器
Redis 的布隆过滤器不是原生自带的，而是要通过 module 加载进去。Redis 在 4.0 的版本中加入了 module 功能。具体使用可以直接看 RedisBloom github 的 README：github.com/RedisBloom/…
Redis 的布隆过滤器主要有两个命令：
- bf.add 添加元素到布隆过滤器中：bf.add strs xy
- bf.exists 判断某个元素是否在过滤器中：bf.exists strs xy
Redis 中有一个命令可以来设置布隆过滤器的准确率：
|
|
三个参数的含义：
- 第一个值是过滤器的名字。
- 第二个值为 error_rate 的值：允许布隆过滤器的错误率。
- 第三个值为 initial_size 的值：初始化位数组的大小。
Java 实现的布隆过滤器
如果你的项目没有使用 Redis，那可以使用一些开源库，基于代码实现，直接存放在内存。比如 Google 的 guava 包中提供了 BloomFilter 类，有兴趣的读者可以去了解一下，研究研究源码和使用。
布谷鸟过滤器
RedisBloom 模块还实现了布谷鸟过滤器，它算是对布隆过滤器的增强版。解决了布隆过滤器的一些比较明显的缺点，比如：不能删除元素，不能计数等。除此之外，布谷鸟过滤器不用使用多个 hash 函数，所以查询性能更高。除此之外，在相同的误判率下，布谷鸟过滤器的空间利用率要明显高于布隆，空间上大概能节省 40% 多。
笔者个人觉得，对于大多数场景来说，布隆过滤器足以解决我们的问题。掘金上有一篇深度分析布谷鸟过滤器的文章，有兴趣的读者可以去了解一下：juejin.im/post/5cfb9c…
认真写文章，用心做分享。
个人网站：yasinshaw.com
公众号：xy 的技术圈
