布隆过滤器 原理及优缺点分析_布隆过滤器误判怎么办

布隆过滤器 原理及优缺点分析_布隆过滤器误判怎么办用于检索一个元素是否在集合中,其空间和时间上及其优秀!

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

Jetbrains全系列IDE稳定放心使用

布隆过滤器

今天我们来聊一聊布隆过滤器,了解他之前,我们先看一看是干什么用的

img

百度百科解释他可以判断一个元素是否在集合中,后面还说了他的效率呀什么的都很好,那既然如此,我们再想象一下为什么需要它!

img

针对上述问题,如果我们直接任由请求访问数据库,问题1、2 还行,如果是问题3,那数据库大抵要说栓Q了。既然如此,我们结合刚刚看到的 布隆过滤器 正好是用来判断一个元素是否存在集合中。而且它的优点就是 空间效率、查询时间都比别人要好的多。那不得看看他到底是咋好的撒。

别急!先骗一波关注!骗不到也没事,咱也不小心眼,接着往下说;

img

如何实现高效率的判断一个元素在不在集合中呢!有的小伙伴立刻就联想到了 List.contains() 方法。如果光靠这个方法,在数据量较大的情况,还是会存在效率问题

img

根据源码我们可以看到他是挨个遍历的,意味每次都要遍历全量的集合。那既然每次都要遍历整个集合,那有什么办法呢?

把集合长度变短!对!布隆过滤器就是这样干的,那元素怎么放呢?

我们可以把任意一个需要比较的元素,通过函数,生成2个或3个甚至更多个整数。道理大致和 hash 差不多,只不过这里是生成多个整数

我们假如二进制向量的长度为9,散列函数的个数为3的布隆过滤器,针对元素X,三个不同的散列函数分别生成的哈希值为1,4,8。则上图转变为:

img

同理,我们再存一个元素Y,如果散列函数返回 4,6,9 的话,图变为:

img

假设,我们要判断元素Z,此时通过计算哈希返回 1,4,5 的话,发现其中 5 为 0,就可以判断 元素 Z 不存在此容器中。

由此我们可以客观的判断出其优缺点:

优点:

  1. 空间占用极小,因为本身不存储数据而是用比特位表示数据是否存在,某种程度有保密的效果。
  2. 插入与查询时间复杂度均为 O(k),常数级别,k 表示散列函数执行次数
  3. 散列函数之间可以相互独立,可以在硬件指令层加速计算。

缺点:

  1. 误差(假存在性)
  2. 无法删除

布隆过滤器可以 100% 的判断元素不在集合中,但是当集合元素非常多都为1时,此时散列函数凑巧又生成了存在的值,就可以判断为 假性存在(假阳性)

如何解决误差问题

在创建布隆过滤器时我们为了找到合适的 m 和 k ,可以根据预期元素数量 n 与 ε 来推导出最合适的 m 与 k

  • 位数组长度 m
  • 散列函数个数 k
  • 预期元素数量 n
  • 期望误差 ε

img

img

算法实现:

// 计算哈希次数
@VisibleForTesting
static int optimalNumOfHashFunctions(long n, long m) {
    // (m / n) * log(2), but avoid truncation due to division!
    return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
}
 
// 计算位数组长度
@VisibleForTesting
static long optimalNumOfBits(long n, double p) {
    if (p == 0) {
        p = Double.MIN_VALUE;
    }
    return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
}

这样我们就可以科学的确定数组长度、散列个数。

我们来看下一个问题

无法删除!

布隆过滤器判断一个元素存在就是判断对应位置是否为1来确定的,但是如果要删除掉一个元素是不能直接把1改成0的,因为这个位置可能存在其它元素,所以如果要支持删除,那我们应该怎么做呢?

最简单的做法就是加一个计数器,就是说位数组的每个位如果不存在就是0,存在几个元素就存具体的数字,而不仅仅只是存1。那么这就有一个问题,本来存1就是一位就可以满足了,但是如果要存具体的数字比如说2,那就需要2位了,所以带有计数器的布隆过滤器会占用更大的空间

参考资料:

布隆过滤器如何删除

布隆过滤器原理实现

百度百科

最后给点个关注吧 img

关注 『Xiang想』公众号

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

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

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

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

(0)
blank

相关推荐

  • 音视频的数字化原理「建议收藏」

    今天本写了篇dicom医学图像解析的文章,后面听人谈到了音视频,今天我就再从中学物理写下我理解的音视频数字化原理。**音频:**物理上说声音三要素音调,响度,音色,响度直观理解就是声音的大小,声音的高低(高音、低音),音色,又称音品这两个其实都跟频率有关。声音的数字化呢,其实来源于原理的,物理上人能听到声音频率的范围是20hz到20khz,数字化采集声音时一般时按44.1khz采集的,就是1s中采集44100次,然后用16byte2个字节来存,一个采样能存的层级就是-2的8次方到2的8次方-1层,总的就是

  • Xshell 配置上传下载命令 rz sz 以及配置复制和粘贴[通俗易懂]

    Xshell 配置上传下载命令 rz sz 以及配置复制和粘贴[通俗易懂]Xshell 配置上传下载命令 rz sz 以及配置复制和粘贴

  • Javaer 进阶必看的 RocketMQ ,就这篇了

    Javaer 进阶必看的 RocketMQ ,就这篇了

    2020年11月20日
  • Mac OSX下给树莓派安装Raspbian系统

    Mac OSX下给树莓派安装Raspbian系统

  • html网页设计作业成品(用css和div制作网站)

    话不多说,直接上效果图:历史介绍行政区划:地理环境著名景点:美食小吃工艺品联系我们部分项目结构老师要求的十几个页面20几张图片以及一些跳转,使用div+css布局也基本上都有了。然后代码也有注释。也能够容易看得懂部分代码偷个懒,就用notepad打开。不用H-build打开了。哈哈哈另外有同学要是需要源码的话可以联系我呀。大家加油!奥利给!…

  • arouter实现activity跳转原理

    arouter实现activity跳转原理一、思路分析arouter让我们可以非常简单地实现组件间页面跳转,实现的基本思路是1.在对应的activity上加上注解,通过apt技术来自动生成代码,代码能将activity对应路径和class添加到路由表中;2.通过扫描获取所有类,遍历自动执行步骤1中所生成地代码,从而路由表中有了对应地数据,路由表的数据结构为Map<String,Class<?e…

发表回复

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

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