布隆过滤器原理简介视频_布隆过滤器误判怎么办

布隆过滤器原理简介视频_布隆过滤器误判怎么办目录1.布隆过滤器简介2.布隆过滤器的实现思路3.布隆过滤器的公式4.实际应用场景1.布隆过滤器简介布隆过滤器(BloomFilter)是由一个很长的bit数组和一系列哈希函数组成的。本质上是一种数据结构,比较巧妙的概率型数据结构。它的特点是高效地插入和查询,并且根据查询结果可以知道某样东西一定不存在或者可能存在。相比于传统的List、Set、Map等数据结构,它更高效、占用空间更少,但是缺点是其返回的结果是概率性的,而不是确切的,同时布隆过滤器还有一个缺陷就是数据只..

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

目录

 

1.布隆过滤器简介

2. 布隆过滤器的实现思路

3.布隆过滤器的公式

4.实际应用场景 


1.布隆过滤器简介

布隆过滤器(Bloom Filter)是由一个很长的bit数组和一系列哈希函数组成的。本质上是一种数据结构,比较巧妙的概率型数据结构。它的特点是高效地插入和查询,并且根据查询结果可以知道某样东西一定不存在或者可能存在相比于传统的 List、Set、Map 等数据结构,它更高效、占用空间更少,但是缺点是其返回的结果是概率性的,而不是确切的,同时布隆过滤器还有一个缺陷就是数据只能插入不能删除

2. 布隆过滤器的实现思路

①设数据集合A={a1,a2,a3,…,an},含有n个元素作为待操作的集合;

②Bloom Filter用一个长度为m的位向量V表示集合中的元素,位向量初始值全为0;

③k个具有均匀分布特性的散列函数h1,h2,…,hk;

④对于要加入的元素,首先经过k个散列函数%m,产生k个随机数h1,h2,…,hk,使向量V的相应位置h1,h2,…,hk均

置位为1。集合中其他元素也通过类似的操作,将向量V的若干位置为1;

⑤对于新要加入的元素的检查,首先将该元素经过上步中类似的操作,获取k个随机数h1,h2,…,hk,然后查看向量V

的相应位置h1,h2,…,hk上的值,若全为1,则该元素已经在之前的集合中;若至少有一个0存在,表明此元素不在之前

的集合中,为新元素。

特点:

对于已经在集合中的元素,通过⑤中的查找方法,一定可以判定该元素在集合中;对于不在集合中的元素,可能会被误判

在集合中。

3.布隆过滤器的公式

布隆过滤器的大小m公式,其中n为样本个数,p为误判率:

布隆过滤器原理简介视频_布隆过滤器误判怎么办

哈希函数的个数k公式:

布隆过滤器原理简介视频_布隆过滤器误判怎么办

 布隆过滤器真实失误率p公式:

布隆过滤器原理简介视频_布隆过滤器误判怎么办

4.实际应用场景 

背景现在有个100亿个黑名单网页数据,每个网页的URL占用64字节。现在想要实现一种网页过滤系统,可以根据网页的URL判断该网站是否在黑名单上,请设计该系统。

需求可以允许有0.01%以下的判断失误率,并且使用的总空间不要超过200G。

提取关键信息100亿条黑名单数据每条数据占64个字节,万分之一的失误率总空间不要超过200G

分析:如果不考虑不布隆过滤器,那么这里存储100亿条数据就需要 100亿 * 64字节 = 596G 显然超过300G

解题在满足有 100亿条数据 并且允许 万分之一的失误率 的布隆过滤器需要多大的bit数组呢?

  • 设bit数组大小为m,样本数量为n,失误率为p。
  • 由题可知 n = 100亿,p = 0.01%
  • 根据布隆过滤器的大小m公式,求得 m = 19.19n,向上取整为 20n。所以2000亿bit,约为186G。
  • 根据哈希函数的个数k公式,求得 k = 14,即需要14个哈希函数。
  • 通过 上述计算得到的 m = 20n, k = 14 ,根据布隆过滤器真实失误率p公式,求得 p = 0.006%。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/185000.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • matlab学习五,二元函数绘图方法

    matlab学习五,二元函数绘图方法plot3()绘制空间曲线%plot3(x,y,z,S)x,y,z为坐标,S为线型%绘制三维螺旋线x=cos(t)y=sin(t)z=tt=0:0.1:10*pi;x=cos(t);y=sin(t);z=t;plot3(x,y,z,’-r’);xlabel(‘x’);ylabel(‘y’);zlabel(‘z’);title(‘三维螺旋线’);2.绘制空间曲面绘制空间曲面的步骤为:绘制平面网格,计算网格上的函数值,绘制网面首先是绘制平面网格[X,Y]=m.

  • Leetcode 166 Fraction to Recurring Decimal

    Leetcode 166 Fraction to Recurring Decimal

  • 【c#】读写txt文件

    【c#】读写txt文件【c#】读写txt文件

  • android短信验证码方案,Android开发之属于你的短信验证码(一)

    android短信验证码方案,Android开发之属于你的短信验证码(一)不飞则已,一飞冲天;不鸣则已,一鸣惊人———司马迁最近工作又有新需求,要求用户在注册的时候需要通过手机验证码,这样做的目的是防止用户通过一个邮箱来随便的注册,那么好,今天我们就一起来学习一下Android中的短信验证码这一个知识点。如有谬误,欢迎批评指正,如有疑问欢迎留言,谢谢在说这个知识点前,我们首先来了解下聚合数据一、聚合数据介绍聚合数据是一家国内最大的基础数据API提供商,专业…

  • Scalar_scala yield

    Scalar_scala yield掌握implicit的用法是阅读spark源码的基础,也是学习scala其它的开源框架的关键,implicit可分为:隐式参数隐式转换类型隐式调用函数1.隐式参数当我们在定义方法时,可以把最后一个参数列表标记为implicit,表示该组参数是隐式参数。一个方法只会有一个隐式参数列表,置于方法的最后一个参数列表。如果方法有多个隐式参数,只需一个implicit修饰即可。当调用包含隐式参数的方法是…

    2022年10月23日
  • 什么是前端跨域,怎么解决跨域问题

    什么是前端跨域,怎么解决跨域问题什么是跨域?跨域,指的是浏览器不能执行其他网站的脚本。它是由浏览器的同源策略造成的,是浏览器施加的安全限制。所谓同源是指:域名,协议,端口均相同,不明白没关系,举个栗子:http://www.123.com/index.html调用http://www.123.com/server.php(非跨域)http://www.123.com/index.html调用http://www.456.com/server.php(主域名不同:123/456,跨域)http://abc.1

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号