布隆过滤器详解

作者:匿名更新于： 2021-10-25 21:35:40

　　在前面的文章里，小编谈到了解决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专题