首页 > 其他分享 >布隆过滤器

布隆过滤器

时间:2022-09-29 17:02:14浏览次数:52  
标签:hash 二进制 布隆 过滤器 数据 hello

 

什么是布隆过滤器

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

标签:hash,二进制,布隆,过滤器,数据,hello
From: https://www.cnblogs.com/cuipengchong/p/16742169.html

相关文章

  • Asp.Net Core 过滤器
    前言    过滤器,从我们开始开发Asp.Net应用程序开始,就一直伴随在我们左右;Asp.NetCore提供多种类型的过滤器,以满足多种多样的业务应用场景;并且在Asp.NetCore本身......
  • [2core]中间件和过滤器
    概述 最近在尝试做将asp.netwebapi项目转移为asp.netcorewebapi项目的技术试验,今天开始测试认证授权、资源控制、Action与Result控制、以及异常控制的技术变化与请求......
  • 面试题:海量数据处理利器-布隆过滤器
    目录概念原理布隆过滤器的使用场景简单模拟布隆过滤器Guava布隆过滤器Redis布隆过滤器布谷鸟过滤器作者:小牛呼噜噜|https://xiaoniuhululu.com计算机内功、JAVA底层、......
  • VueJs 自定义过滤器使用总结
    在这个教程中,我们将会通过几个例子,了解和学习VueJs的过滤器。我们参考了一些比较完善的过滤器,比如orderBy和filterBy。而且我们可以链式调用过滤器,一个接一个过滤。因此,我......
  • MySQL半同步复制的实现和复制过滤器
    异步:当客户端发送给服务端请求时,在等待服务端响应的时候,客户端可以做其他的事情,这样节约了时间,提高了效率。同步:当客户端发送请求给服务端,在等待服务端响应的请求时,客户......
  • 布隆过滤器
    布隆过滤器面试被问到了海量数据处理相关的问题。然后发现了布隆过滤器这个数据结构,学了一下,结果就是这是acm里面用过的算法。我把布隆过滤器分解为两个模块,也就是多次哈......
  • vue3配置全局过滤器
    vue3配置全局过滤器需要在main.js中配置一下代码//vue3配置全局过滤器app.config.globalProperties.$filters={//formatTime过滤器的名称formatTime(value:s......
  • Qt 事件过滤器
    目录分析代码一、控件安装事件过滤器二、在过滤器中实现事件过滤事件效果总结 分析现在有这样一个场景,界面中有三个按钮,分别实现三个按钮对应槽函数,正......
  • 十分钟理解布隆过滤器
    首先我们要先了解什么是布隆过滤器?布隆过滤器(BloomFilter)是由Bloom于1970年提出的。我们可以把它看作由二进制向量(或者说位数组)和一系列随机映射函数(哈希函数)两部分......
  • 拦截器和过滤器的区别
    拦截器和过滤器的区别1.过滤器是servlet中的对象,拦截器是框架中的对象2.过滤器实现Filter接口的对象,拦截器是实现HandlerInterceptor3.过滤器是用来设置request,respo......