布隆过滤器误判怎么办为什么会_最牛一篇布隆过滤器详解

前言

我们之前讲了Redis的缓存雪崩、穿透、击穿。在文章里我们说了解决缓存穿透的办法之一，就是

布隆过滤器

，但是上次并没有讲如何使用布隆过滤器。

作为暖男的老哥，给你们补上，请叫我

IT老暖男

。

什么是布隆过滤器

布隆过滤器(Bloom Filter)，是1970年，由一个叫布隆的小伙子提出的，距今已经五十年了，和老哥一样老。

它实际上是一个很长的二进制向量和一系列随机映射函数，二进制大家应该都清楚，存储的数据不是0就是1，默认是0。

主要用于判断一个元素是否在一个集合中，0代表

不存在

某个数据，1代表

存在

某个数据。

懂了吗？作为

暖男

的老哥在给你们画张图来帮助理解：

布隆过滤器用途

• 解决Redis缓存穿透(今天重点讲解)
• 在爬虫时，对爬虫网址进行过滤，已经存在布隆中的网址，不在爬取。
• 垃圾邮件过滤，对每一个发送邮件的地址进行判断是否在布隆的黑名单中，如果在就判断为垃圾邮件。

以上只是简单的用途举例，大家可以举一反三，灵活运用在工作中。

布隆过滤器原理

存入过程

布隆过滤器上面说了，就是一个二进制数据的集合。当一个数据加入这个集合时，经历如下洗礼(这里有缺点，下面会讲)：

• 通过K个哈希函数计算该数据，返回K个计算出的hash值
• 这些K个hash值映射到对应的K个二进制的数组下标
• 将K个下标对应的二进制数据改成1。

例如，第一个哈希函数返回x，第二个第三个哈希函数返回y与z，那么：X、Y、Z对应的二进制改成1。

如图所示：

查询过程

布隆过滤器主要作用就是查询一个数据，在不在这个二进制的集合中，查询过程如下：

• 通过K个哈希函数计算该数据，对应计算出的K个hash值
• 通过hash值找到对应的二进制的数组下标
• 判断：如果存在一处位置的二进制数据是0，那么该数据不存在。如果都是1，该数据存在集合中。(这里有缺点，下面会讲)

删除过程

一般不能删除布隆过滤器里的数据，这是一个缺点之一，我们下面会分析。

布隆过滤器的优缺点

优点

• 由于存储的是二进制数据，所以占用的空间很小
• 它的插入和查询速度是非常快的，时间复杂度是O(K)，可以联想一下HashMap的过程
• 保密性很好，因为本身不存储任何原始数据，只有二进制数据

缺点

这就要回到我们上面所说的那些缺点了。

添加数据是通过计算数据的hash值，那么很有可能存在这种情况：两个不同的数据计算得到相同的hash值。

例如图中的“

你好

”和“

hello

”，假如最终算出hash值相同，那么他们会将同一个下标的二进制数据改为1。

这个时候，你就不知道下标为2的二进制，到底是代表“

你好

”还是“

hello

”。

由此得出如下缺点：

一、存在误判

假如上面的图没有存"

hello

"，只存了"

你好

"，那么用"

hello

"来查询的时候，会判断"

hello

"存在集合中。

因为“

你好

”和“

hello

”的hash值是相同的，通过相同的hash值，找到的二进制数据也是一样的，都是1。

二、删除困难

到这里我不说大家应该也明白为什么吧，作为你们的

暖男老哥

，还是讲一下吧。

还是用上面的举例，因为“

你好

”和“

hello

”的hash值相同，对应的数组下标也是一样的。

这时候老哥想去删除“

你好

”，将下标为2里的二进制数据，由1改成了0。

那么我们是不是连“

hello

”都一起删了呀。(0代表有这个数据，1代表没有这个数据)

到这里是不是对布隆过滤器已经明白了，都说了我是暖男。

实现布隆过滤器

有很多种实现方式，其中一种就是

Guava

提供的实现方式。

一、引入Guava pom配置

二、代码实现

这里我们顺便测一下它的误判率。

运行结果：

10万数据里有947个误判，约等于0.01%，也就是我们代码里设置的误判率：fpp = 0.01。

深入分析代码

核心

BloomFilter.create

方法

这里有四个参数：

• funnel

  ：数据类型(一般是调用Funnels工具类中的)

• expectedInsertions

  ：期望插入的值的个数

• fpp

  ：误判率(默认值为0.03)

• strategy

  ：哈希算法

我们重点讲一下

fpp

参数

fpp误判率

情景一：

fpp = 0.01

• 误判个数：947

  

• 占内存大小：9585058位数

  

情景二：

fpp = 0.03

(默认参数)

• 误判个数：3033

  

• 占内存大小：7298440位数

  

情景总结

• 误判率可以通过

  fpp

  参数进行调节
• fpp越小，需要的内存空间就越大：0.01需要900多万位数，0.03需要700多万位数。
• fpp越小，集合添加数据时，就需要更多的hash函数运算更多的hash值，去存储到对应的数组下标里。(忘了去看上面的布隆过滤存入数据的过程)

上面的

numBits

，表示存一百万个int类型数字，需要的位数为7298440，700多万位。理论上存一百万个数，一个int是4字节32位，需要481000000=3200万位。如果使用HashMap去存，按HashMap50%的存储效率，需要6400万位。可以看出BloomFilter的存储空间很小，只有HashMap的1/10左右

上面的

numHashFunctions

表示需要几个hash函数运算，去映射不同的下标存这些数字是否存在(0 or 1)。

解决Redis缓存穿透

上面使用Guava实现的布隆过滤器是把数据放在了本地内存中。分布式的场景中就不合适了，无法共享内存。

我们还可以用Redis来实现布隆过滤器，这里使用Redis封装好的客户端工具Redisson。

其底层是使用数据结构bitMap，大家就把它理解成上面说的二进制结构，由于篇幅原因，bitmap不在这篇文章里讲，我们之后写一篇文章介绍。

代码实现

pom配置：

java代码：

由于Guava那个版本，我们已经很详细的讲了布隆过滤器的那些参数，这里就不重复赘述了。

给个[在看]，是对IT老哥最大的支持