布隆过滤器（Bloom Filter）是由 Bloom 于 1970 年提出的。我们可以把它看作由位数组和一系列哈希函数两部分组成的数据结构。相比于我们平时常用的的 List、Map 、Set 等数据结构，它占用空间更少并且效率更高，但是缺点是其返回的结果是概率性的，而不是非常准确的。理论情况下添加到集合中的元素越多，误报的可能性就越大。并且，存放在布隆过滤器的数据不容易删除。
图1
位数组中的每个元素都只占用 1 bit ，并且每个元素只能是 0 或者 1。这样申请一个 1000w 个元素的位数组只占用 10000000Bit / 8 = 1250000 Byte / 1024 ≈ 1222kb / 1024 ≈ 1M 的空间。
原理介绍
当一个元素加入布隆过滤器中的时候，会进行如下操作：
- 1.使用布隆过滤器中的哈希函数对元素值进行计算，得到哈希值（有几个哈希函数得到几个哈希值）。
- 2.根据得到的哈希值，在位数组中把对应下标的值置为 1。
当我们需要判断一个元素是否存在于布隆过滤器的时候，会进行如下操作：
- 1.对给定元素再次进行相同的哈希计算；
- 2.得到值之后判断位数组中的每个元素是否都为 1，如果值都为 1，那么说明这个值在布隆过滤器中，如果存在一个值不为 1，说明该元素不在布隆过滤器中。
因为不同的字符串可能哈希出来的位置相同(就是我们常说的哈希冲突)，所以布隆过滤器说某个元素存在，小概率会误判。布隆过滤器说某个元素不在，那么这个元素一定不在。
使用场景
一般在亿级以上数据判断给定数据是否存在的场景，推荐使用布隆过滤器，比如避免缓存穿透(判断请求的数据是否有效避免直接绕过缓存请求数据库)、垃圾邮件地址过滤、浏览器检查钓鱼网站等。
开源实现
在实际项目中我们一般不需要手动实现布隆过滤器，比如Guava 中布隆过滤器的实现就很权威。
Guava布隆过滤器
guava提供了一套很方便使用布隆过滤器的方法，下面我们创建了一个最多存放 1500 个整数的布隆过滤器，并且我们可以容忍误判的概率为百分之0.01
// 创建布隆过滤器对象
BloomFilter<Integer> filter = BloomFilter.create(Funnels.integerFunnel(), 1500, 0.01);
// 判断指定元素是否存在
System.out.println(filter.mightContain(1));
System.out.println(filter.mightContain(2));
// 将元素添加进布隆过滤器
filter.put(1);
filter.put(2);
System.out.println(filter.mightContain(1));
System.out.println(filter.mightContain(2));
Guava 提供的布隆过滤器的实现还是很不错的（想要详细了解的可以看一下它的源码实现，大致是采用了murmur3_128哈希算法求得hash值，然后对长度进行求余得到数组hash值），但是它有一个重大的缺陷就是只能单机使用（另外，容量扩展也不容易），而现在互联网一般都是分布式的场景。为了解决这个问题，我们就需要用到 Redis 中的布隆过滤器了。
Redis布隆过滤器
Redis v4.0 之后有了 Module（模块/插件） 功能，Redis Modules 让 Redis 可以使用外部模块扩展其功能 。布隆过滤器就是其中的 Module。详情可以查看 Redis 官方对 Redis Modules 的介绍 ：redis.io/modules
RedisBloom 提供了多种语言的客户端支持，包括：Python、Java、JavaScript 和 PHP。
常用命令：
- 1.BF.ADD：将元素添加到布隆过滤器中，如果该过滤器尚不存在，则创建该过滤器。格式：BF.ADD {key} {item}。
- 2.BF.MADD : 将一个或多个元素添加到“布隆过滤器”中，并创建一个尚不存在的过滤器。该命令的操作方式BF.ADD与之相同，只不过它允许多个输入并返回多个值。格式：BF.MADD {key} [item ...] 。
- 3.BF.EXISTS : 确定元素是否在布隆过滤器中存在。格式：BF.EXISTS {key} {item}。
- 4.BF.MEXISTS ： 确定一个或者多个元素是否在布隆过滤器中存在格式：BF.MEXISTS {key} [item ...]。
另外， BF. RESERVE 命令需要单独介绍一下：
这个命令的格式如下：
- BF. RESERVE {key} {error_rate} {capacity} [EXPANSION expansion]
下面简单介绍一下每个参数的具体含义：
- key：布隆过滤器的名称
- error_rate : 期望的误报率。该值必须介于 0 到 1 之间。例如，对于期望的误报率 0.1％（1000 中为 1），error_rate 应该设置为 0.001。该数字越接近零，则每个项目的内存消耗越大，并且每个操作的 CPU 使用率越高。
- capacity: 过滤器的容量。当实际存储的元素个数超过这个值之后，性能将开始下降。随着过滤器元素数量呈指数增长，性能将线性下降。
- expansion：可选参数，当添加到布隆过滤器中的数据达到初始容量后，布隆过滤器会自动创建一个子过滤器，子过滤器的大小是上一个过滤器大小乘以 expansion；expansion 的默认值是 2，也就是说布隆过滤器扩容默认是 2 倍扩容。
总结
- 相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势，不仅非常节省空间，而且增加和查询元素的时间复杂度都为O(K) (K为哈希函数的个数，一般比较小)；
- 对于开源的布隆过滤器实现，基本都提供了预期添加数量和误判概率配置参数，它们会根据配置的参数计算出最佳的长度和哈希函数数量。所以我们只需提前计划好存入key的数量；
- 缺点是不支持删除，而且需要提前计划好存入key的数量，并且不能动态修改。
- 相比于redis的bitmap，布隆过滤器在规划合理的前提下，绝大多数时候下更节省内存，比如bitmap中数据是 1,100000000被设置为1，那么其实只需要用到2位，但是却需要100000000位内存，而且bitmap仅限于数字类型。
网友评论