下载安卓APP箭头
箭头给我发消息

客服QQ:3315713922

布隆过滤器详解

作者:匿名     来源: Python点击数:1360发布时间: 2021-10-25 21:35:40

标签: Python学习Redis布隆过滤器

大神带你学编程,欢迎选课

  在前面的文章里,小编谈到了解决Redis缓存穿透的方法之一,即布隆过滤器,接下来的文章里,小编就来讲讲如何使用布隆过滤器。

  先来看看布隆过滤器是什么?

  布隆过滤器(BloomFilter)实际上是一个长的二元向量和一系列随机映射函数。大家应该都知道,存储的数据不是0就是1,默认是0。主要用于判断一个元素是否在一个集合中。0代表没有数据,1代表有数据。

  你明白吗?以下为大家画一张图来帮助理解:  

 

  布隆过滤器的用途:

  1.解决Redis缓存穿透(今天重点解释)

  2.爬虫时,过滤爬虫网站,布隆中已经存在网站,而不是爬行。

  3.对垃圾邮件进行过滤,判断每个发送邮件的地址是否在布隆的黑名单中,如果是,判断为垃圾邮件。

  上述只是一个简单的例子,大家可以举一反三,灵活运用到工作中。

  布隆过滤原理:

  存储过程

  前面说过,布隆过滤器是二进制数据的集合。将一组数据加入到这个集合中,进行如下的洗礼(以下是缺点):

  使用K个哈希函数计算数据,返回计算K个hash值。

  这些khash值映射到相应的k二进制数组下标。

  把K数下标的对应二进制数据改为1。

  举例来说,第一个哈希函数返回x,第二个哈希函数返回y和z,然后:X,Y,Z对应的二进制改为1。

  如图: 

  查询过程

  Bloom过滤器的主要功能是查询数据,查询过程如下:

  K个hash值是通过K个哈希函数计算出来的。

  通过hash值找到相应的二进制数组下标。

  判断:如果一个位置的二进制数据为0,则该数据不存在。如果都是1,数据就存在于集合中。(下面将讨论这些缺点)

  删除过程

  通常不能删除布隆过滤器中的数据,这是一个缺点,我们将在下面进行分析。

  布隆过滤器的优缺点:

  优点

  因为存储的是二进制数据,所以占用的空间很小。

  它的插入和查询速度非常快,时间复杂,可以联想到HashMap的过程。

  保密性很好,因为它不存储任何原始数据,只有二进制数据。

  缺点

  这将回到我们上面提到的缺点。

  添加数据是通过计算数据的hash值来计算的,所以很有可能两个不同的数据计算得到相同的hash值。  

  比如图中的你好和hello,如果最终计算出相同的hash值,那么他们就会把同一个下标的二进制数据改为1。

  此时,你不知道下标为2的二进制是代表你好还是hello。

  得出以下缺点:

  第一,有误判。

  如图中没有"hello",只有"hello",那么当查询"hello"时,就可以知道该集合中存在"hello"。

  因为你和hello的hash值是一样的,所以用同样的hash值找到的二进制数据也是一样的。

  第二,删除困难。

  来这儿我不说大家也应该明白为什么吧,作为你们暖男老哥,还是说说吧。

  或者以上例子,因为你好和hello的hash值是一样的,相应的数组下标也是一样的。

  此时老哥想删除你好,把下标为2里的二进制数据从1改为0。

  那我们是不是连hello都一起删了啊?(0代表有这个数据,1代表没有这个数据)

  在这里明白布隆过滤器了吗?

  实现布隆过滤器:

  实现方式有很多种,其中之一就是Guava提供的。

  引入Guavapom配置。  

  实现代码

  以下顺便测量一下它的误判率.  

  小编的分享就到这里了,希望上面的介绍有帮到大家。

    >>>>>>点击进入Python专题

赞(11)
踩(0)
分享到:
华为认证网络工程师 HCIE直播课视频教程