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

布隆过滤器原理简介视频_布隆过滤器误判怎么办目录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)
blank

相关推荐

  • mySQL插入数据自动生成时间

    mySQL插入数据自动生成时间

  • windows程序设计第五版_程序设计中三种基本结构

    windows程序设计第五版_程序设计中三种基本结构WNDCLASS结构参数及其用法WNDCLASS是一个由系统支持的结构,用来储存某一类窗口的信息,如ClassStyle,消息处理函数,Icon,Cursor,背景Brush等。也就是说,CreateWindow只是将某个WNDCLASS定义的窗体变成实例。结构WNDCLASS包含一个窗口类的全部信息,也是Windows编程中使用的基本数据结构之一,应用程序通过定义一个窗口类确定窗口的属性基…

  • SCI论文投稿信(Cover Letter)的写法及模版

    SCI论文投稿信(Cover Letter)的写法及模版一、写法投稿信(CoverLetter)应该简述所投稿件的核心内容、主要发现和意义,拟投期刊,对稿件处理有无特殊要求等(如“nottoreview”list)。另外,请附上主要作者的中文姓名、通讯地址、电话、传真和e-mail地址。此外有的杂志要求推荐几位审稿人及其联系方式。以及谁已经阅读过该文(当然是牛人)。一般来说,杂志通常要求说明你论文研究的意义,以及与这个杂志的相关性,另外还有…

  • Dynamics Crm 2011 Or 2013 IFD 部署一段时间后,CA验证问题[通俗易懂]

    Dynamics Crm 2011 Or 2013 IFD 部署一段时间后,CA验证问题[通俗易懂]以下错误描述摘自博客:http://blog.csdn.net/qzw4549689/article/details/14451257IFD部署一段时间后,大概一年,突然出现从IFD登录页面登录后,再次弹出要求登录的框,多次输入用户名密码仍然无效,查看日志:><TraceRecordxmlns=”http://schemas.micros…

    2022年10月26日
  • Okhttp学习及封装

    Okhttp学习及封装Okhttp1.学习Okhttp2.OkHttp的封装1.学习Okhttp需要导入依赖implementation’com.squareup.okhttp3:okhttp:3.12.1’四个按钮需要写入布局get请求,post请求,下载文件,上传文件别忘了加入SD卡权限,网络权限privatevoidinitView(){get=(Button)…

    2022年10月18日
  • staruml使用教程[通俗易懂]

    最近因为实验需要,得用到uml类图。找了个教程。mark下,便于以后学习。 http://blog.csdn.net/monkey_d_meng/article/details/5995610

发表回复

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

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