什么是布隆过滤器
布隆过滤器(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代表没有这个数据)