Redis深入学习（六）：Redis布隆过滤器

短命女 2022-08-29 09:40 120阅读 0赞

### 文章目录 ###

*  一、布隆过滤器使用场景
 *  二、布隆过滤器简介
 *  三、Redis实现布隆过滤器
 *  四、Redisson
 *  五、guava 工具

# 一、布隆过滤器使用场景 #

比如有如下几个需求：

1、原本有10亿个号码，现在又来了10万个号码，要快速准确判断这10万个号码是否在10亿个号码库中？

*  解决办法一：将10亿个号码存入数据库中，进行数据库查询，准确性有了，但是速度会比较慢。
 *  解决办法二：将10亿号码放入内存中，比如`Redis`缓存中，这里我们算一下占用内存大小：10亿\*8字节=8`GB`，通过内存查询，准确性和速度都有了，但是大约8`GB`的内存空间，挺浪费内存空间的。

2、接触过爬虫的，应该有这么一个需求，需要爬虫的网站千千万万，对于一个新的网站`url`，我们如何判断这个`url`我们是否已经爬过了？

*  解决办法还是上面的两种，很显然，都不太好。

3、同理还有垃圾邮箱的过滤。

那么对于类似这种，大数据量集合，如何准确快速的判断某个数据是否在大数据量集合中，并且不占用内存，布隆过滤器应运而生了。

# 二、布隆过滤器简介 #

布隆过滤器：一种数据结构，是由一串很长的二进制向量组成，可以将其看成一个二进制数组。既然是二进制，那么里面存放的不是0，就是1，但是初始默认值都是0。  
![在这里插入图片描述][9519f3883dba48988e745085728219ab.png]  
**① 添加数据**

介绍概念的时候，我们说可以将布隆过滤器看成一个容器，那么如何向布隆过滤器中添加一个数据呢？

如下图所示：当要向布隆过滤器中添加一个元素`key`时，我们通过多个`hash`函数，算出一个值，然后将这个值所在的方格置为1。比如，下图`hash1(key)=7`，那么在第8个格子将0变为1（数组是从0开始计数的），`hash2(key)=15`，那么将第16个格子置位1，依次类推。  
![在这里插入图片描述][30c3a1a7d26249faa602797cccae02f5.png]  
**② 判断数据是否存在？**

*知道了如何向布隆过滤器中添加一个数据，那么新来一个数据，我们如何判断其是否存在于这个布隆过滤器中呢？*

很简单，我们只需要将这个新的数据通过上面自定义的几个哈希函数，分别算出各个值，然后看其对应的地方是否都是1，如果存在一个不是1的情况，那么我们可以说，该新数据一定不存在于这个布隆过滤器中。

*反过来说，如果通过哈希函数算出来的值，对应的地方都是1，那么我们能够肯定的得出：这个数据一定存在于这个布隆过滤器中吗？*

答案是否定的，因为多个不同的数据通过hash函数算出来的结果是会有重复的，所以会存在某个位置是别的数据通过hash函数置为的1。  
　　  
**③ 布隆过滤器优缺点**

*  优点：优点很明显，二进制组成的数组，占用内存极少，并且插入和查询速度都足够快。
 *  缺点：随着数据的增加，误判率会增加；还有无法判断数据一定存在；另外还有一个重要缺点，无法删除数据。

# 三、Redis实现布隆过滤器 #

**① bitmaps**

我们知道计算机是以二进制位作为底层存储的基础单位，一个字节等于8位。比如`big`字符串是由三个字符组成的，这三个字符对应的`ASCII`码分为是98、105、103，对应的二进制存储如下：  
![在这里插入图片描述][a8cc44261e774b5b9871e5a427b10d8e.png]  
在`Redis`中，`Bitmaps`提供了一套命令用来操作类似上面字符串中的每一个位。

**① 设置值**：setbit key offset value  
![在这里插入图片描述][728d8ec09f494767a5ca969f3cc1ec1c.png]  
我们知道`b`的二进制表示为0110 0010，我们将第7位（从0开始）设置为1，那0110 0011 表示的就是字符`c`，所以最后的字符`big`变成了`cig`。

**② 获取值**：gitbit key offset  
![在这里插入图片描述][178688b6069a4c698d08d930f102396e.png]  
**③ 获取位图指定范围值为1的个数**：bitcount key \[start end\]

如果不指定，那就是获取全部值为1的个数。（注意：start和end指定的是字节的个数，而不是位数组下标。）  
![在这里插入图片描述][1b199dd4f78b40419b535519396a388a.png]

# 四、Redisson #

`Redis`实现布隆过滤器的底层就是通过`bitmap`这种数据结构，至于如何实现，这里就不重复造轮子了，介绍业界比较好用的一个客户端工具——`Redisson`。

`Redisson`是用于在`Java`程序中操作`Redis`的库，利用`Redisson`我们可以在程序中轻松地使用`Redis`。

下面我们就通过`Redisson`来构造布隆过滤器。

import org.redisson.Redisson;
    import org.redisson.api.RBloomFilter;
    import org.redisson.api.RedissonClient;
    import org.redisson.config.Config;
    
    public class RedissonBloomFilter { 
    
        public static void main(String[] args) { 
            Config config = new Config();
            config.useSingleServer().setAddress("redis://192.168.14.104:6379");
            config.useSingleServer().setPassword("123");
            //构造Redisson
            RedissonClient redisson = Redisson.create(config);
    
            RBloomFilter<String> bloomFilter = redisson.getBloomFilter("phoneList");
            //初始化布隆过滤器：预计元素为100000000L,误差率为3%
            bloomFilter.tryInit(100000000L,0.03);
            //将号码10086插入到布隆过滤器中
            bloomFilter.add("10086");
    
            //判断下面号码是否在布隆过滤器中
            System.out.println(bloomFilter.contains("123456"));//false
            System.out.println(bloomFilter.contains("10086"));//true
        }
    }

# 五、guava 工具 #

最后提一下不用`Redis`如何来实现布隆过滤器。`guava`工具包相信大家都用过，这是谷歌公司提供的，里面也提供了布隆过滤器的实现。

import com.google.common.base.Charsets;
    import com.google.common.hash.BloomFilter;
    import com.google.common.hash.Funnel;
    import com.google.common.hash.Funnels;
    
    public class GuavaBloomFilter { 
        public static void main(String[] args) { 
            BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8),100000,0.01);
    
            bloomFilter.put("10086");
    
            System.out.println(bloomFilter.mightContain("123456"));
            System.out.println(bloomFilter.mightContain("10086"));
        }
    }

[9519f3883dba48988e745085728219ab.png]: /images/20220829/ad6a78440c7c46fd83fbec3894be4920.png
[30c3a1a7d26249faa602797cccae02f5.png]: /images/20220829/2a35fdaecd6b47cdbadbb68660ab0e37.png
[a8cc44261e774b5b9871e5a427b10d8e.png]: /images/20220829/7238cf7ecacf4fa4a2eb5257540481bc.png
[728d8ec09f494767a5ca969f3cc1ec1c.png]: /images/20220829/8b408d92bd99421fa57ff35703a3d94b.png
[178688b6069a4c698d08d930f102396e.png]: /images/20220829/05357727b7c64d3a8ea686a8bf751998.png
[1b199dd4f78b40419b535519396a388a.png]: /images/20220829/b6cac6966c22448fb3c6feab077d8031.png