环球ug官方网:Redis详解(十三)------ Redis布隆过滤器

admin 5个月前 (06-03) 科技 33 0

  本篇博客我们主先容若何用Redis实现布隆过滤器,然则在先容布隆过滤器之前,我们首先先容一下,为啥要使用布隆过滤器。

1、布隆过滤器使用场景

  好比有如下几个需求:

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

  解决办法一:将10亿个号码存入数据库中,举行数据库查询,准确性有了,然则速率会对照慢。

  解决办法二:将10亿号码放入内存中,好比Redis缓存中,这里我们算一下占用内存大小:10亿*8字节=8GB,通过内存查询,准确性和速率都有了,然则约莫8gb的内存空间,挺虚耗内存空间的。

  ②、接触过爬虫的,应该有这么一个需求,需要爬虫的网站千千万万,对于一个新的网站url,我们若何判断这个url我们是否已经爬过了?

  解决办法照样上面的两种,很显然,都不太好。

  ③、同理另有垃圾邮箱的过滤。

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

2、布隆过滤器简介

  带着上面的几个疑问,我们来看看到底什么是布隆过滤器。

  布隆过滤器:一种数据结构,是由一串很长的二进制向量组成,可以将其看成一个二进制数组。既然是二进制,那么内里存放的不是0,就是1,然则初始默认值都是0。

  如下所示:

  

  ①、添加数据

  先容观点的时刻,我们说可以将布隆过滤器看成一个容器,那么若何向布隆过滤器中添加一个数据呢?

  如下图所示:当要向布隆过滤器中添加一个元素key时,我们通过多个hash函数,算出一个值,然后将这个值所在的方格置为1。

  好比,下图hash1(key)=1,那么在第2个格子将0变为1(数组是从0最先计数的),hash2(key)=7,那么将第8个格子置位1,依次类推。

  

&NBsp;

  ②、判断数据是否存在?

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

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

  反过来说,若是通过哈希函数算出来的值,对应的地方都是1,那么我们能够一定的得出:这个数据一定存在于这个布隆过滤器中吗?

  谜底是否认的,由于多个差其余数据通过hash函数算出来的结果是会有重复的,以是会存在某个位置是其余数据通过hash函数置为的1。

  我们可以获得一个结论:布隆过滤器可以判断某个数据一定不存在,然则无法判断一定存在

  ③、布隆过滤器优瑕玷

  优点:优点很明显,二进制组成的数组,占用内存少少,而且插入和查询速率都足够快。

  瑕玷:随着数据的增添,误判率会增添;另有无法判断数据一定存在;另外另有一个主要瑕玷,无法删除数据。

3、Redis实现布隆过滤器

①、bitmaps

  我们知道计算机是以二进制位作为底层存储的基础单元,一个字节即是8位。

  好比“big”字符串是由三个字符组成的,这三个字符对应的ASCII码分为是98、105、103,对应的二进制存储如下:

  

 

 

  在Redis中,Bitmaps 提供了一套下令用来操作类似上面字符串中的每一个位。

  一、设置值

setbit key offset value

  环球ug官方网:Redis详解(十三)------ Redis布隆过滤器 第1张

 

   我们知道"b"的二进制示意为0110 0010,我们将第7位(从0最先)设置为1,那0110 0011 示意的就是字符“c”,以是最后的字符 “big”变成了“cig”。

  二、获取值

gitbit key offset

  环球ug官方网:Redis详解(十三)------ Redis布隆过滤器 第2张

   三、获取位图指定局限值为1的个数

bitcount key [start end]

  若是不指定,那就是获取所有值为1的个数。

  注重:start和end指定的是字节的个数,而不是位数组下标。

  环球ug官方网:Redis详解(十三)------ Redis布隆过滤器 第3张

②、Redisson

  Redis 实现布隆过滤器的底层就是通过 bitmap 这种数据结构,至于若何实现,这里就不重复造轮子了,先容业界对照好用的一个客户端具——Redisson。

  Redisson 是用于在 JAVa 程序中操作 Redis 的库,行使Redisson 我们可以在程序中轻松地使用 Redis。

  下面我们就通过 Redisson 来组织布隆过滤器。

 1 package com.ys.rediscluster.bloomfilter.redisson;
 2 
 3 import org.redisson.Redisson;
 4 import org.redisson.api.RBloomFilter;
 5 import org.redisson.api.RedissonClient;
 6 import org.redisson.config.Config;
 7 
 8 public class RedissonBloomFilter {
 9 
10     public static void main(String[] args) {
11         Config config = new Config();
12         config.useSingleServer().setAddress("redis://192.168.14.104:6379");
13         config.useSingleServer().setPassword("123");
14         //组织Redisson
15         RedissonClient redisson = Redisson.create(config);
16 
17         RBloomFilter<String> bloomFilter = redisson.getBloomFilter("phoneList");
18         //初始化布隆过滤器:预计元素为100000000L,误差率为3%
19         bloomFilter.tryInit(100000000L,0.03);
20         //将号码10086插入到布隆过滤器中
21         bloomFilter.add("10086");
22 
23         //判断下面号码是否在布隆过滤器中
24         System.out.println(bloomFilter.contains("123456"));//false
25         System.out.println(bloomFilter.contains("10086"));//true
26     }
27 }

  这是单节点的Redis实现方式,若是数据量对照大,期望的误差率又很低,那单节点所提供的内存是无法知足的,这时刻可以使用分布式布隆过滤器,同样也可以用 Redisson 来实现,这里我就不做代码演示了,人人有兴趣可以试试。

4、guava 工具

  最后提一下不用Redis若何来实现布隆过滤器。

  guava 工具包信赖人人都用过,这是谷歌公司提供的,内里也提供了布隆过滤器的实现。

 1 package com.ys.rediscluster.bloomfilter;
 2 
 3 import com.Google.common.base.Charsets;
 4 import com.google.common.hash.BloomFilter;
 5 import com.google.common.hash.Funnel;
 6 import com.google.common.hash.Funnels;
 7 
 8 public class GuavABLoomFilter {
 9     public static void main(String[] args) {
10         BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8),100000,0.01);
11 
12         bloomFilter.put("10086");
13 
14         System.out.println(bloomFilter.mightContain("123456"));
15         System.out.println(bloomFilter.mightContain("10086"));
16     }
17 }

 

,

Allbet

www.kaiwenpower.com欢迎进入欧博平台(Allbet Gaming),欧博平台开放欧博(Allbet)开户、欧博(Allbet)代理开户、欧博(Allbet)电脑客户端、欧博(Allbet)APP下载等业务。

皇冠体育声明:该文看法仅代表作者自己,与本平台无关。转载请注明:环球ug官方网:Redis详解(十三)------ Redis布隆过滤器

文章归档

站点信息

  • 文章总数:653
  • 页面总数:0
  • 分类总数:8
  • 标签总数:1192
  • 评论总数:233
  • 浏览总数:19902