Java集合框架分析(九)——布隆过滤器深入分析及其误判概率计算

本文主要是介绍Java集合框架分析(九)——布隆过滤器深入分析及其误判概率计算,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

         上篇文章简单的介绍了下布隆过滤器,让大家知道了下其原理,现在我们进行下深入分析。

       首先,我们要明确布隆过滤器的几个参数,之前 我们的例子是有一亿的网址要存储,要先建立一个16亿的bit array,然后以每个网址为键值得到8个value值,这里我们就有疑问了,为什么要16亿,为什么要8个value值?那我们不妨把这些都设成未知数,设我们要输入n个元素,生成m个bit位,需要k个hash function得到value值。然后还有我们要分析的一个参数,误报率P(error)。这样一来我们再来看看布隆过滤器的算法。

       首先系统要算出n个元素需要多少个 m bit位并且都设置成0,为了插入一个元素,要用hash算法得到k个value值作为bit array的索引并且将这些索引位置设置成1.若是要查询一个元素是否在表中,还是用Hash算法得到k个value看看这些位置是否全为1.可以知道,如果插入的数据多的时候,可能有一个没有在表中的元素但是得到的k个value索引都是1的情况,这就是误报率P(error)。可以知道,当最初建立的m越大,k越多,P越小。但是如何找到最优的k和m呢?这就需要进行数学计算了。

      假设布隆过滤器中的每个元素都等概率地hash到m个索引位置中的任何一个,则对某一特定bit位在一个元素由某特定hash function插入时没有被置位为1的概率为:

clip_image002[16]

则k个hash function中没有一个对其置位的概率为:

clip_image002[18]

如果插入了n个元素,但都未将其置位的概率,也就是空间未利用的概率为:

clip_image002[20]

则此位被置位的概率为:

clip_image002[22]

 

现在考虑查询阶段,若对应某个要查询的元素的k bits全部置位为1,则可判定其在集合中。因此将某元素误判的概率为:

clip_image002[24]

由于 clip_image002[26],并且 clip_image002[28]  当m很大时趋近于0,所以

clip_image002[30]

 

现在计算对于给定的m和n,k为何值时可以使得误判率最低。设误判率为k的函数为:

clip_image002[32]

设  clip_image002[34] , 则简化为

clip_image002[36],两边取对数

clip_image002[38]  , 两边对k求导

clip_image002[40]

下面求最值

clip_image002[42]

clip_image002[44] clip_image004

clip_image002[44] clip_image006

clip_image002[44] clip_image008

clip_image002[44] clip_image010

clip_image002[44] clip_image012

clip_image002[44] clip_image014

clip_image002[44] clip_image002[52]

因此,即当 clip_image002[54]  时误判率最低,此时误判率为:

clip_image002[56]

     

从上面的推导可以看出,要想创建一个布隆过滤器,我们要输入两个参数,就是n和P(error).之后的所有参数将由系统计算,并由此建立布隆过滤器。

 

系统首先要计算需要的内存大小m bits:

clip_image002[60]

 

再由m,n得到k:

clip_image002[52]

 

至此系统所需的参数已经备齐,接下来add n个元素至布隆过滤器中,再进行查询。

 根据公式,当k最优时:

clip_image002[66]

clip_image004[8]

因此可验证当P=1%时,存储每个元素需要9.6 bits:

clip_image002[70] 

回到之前的k的定义:

clip_image002[76]   从而使得P(error)最小时,我们注意到:

clip_image002[78] 中的 clip_image002[80]  ,即

clip_image002[82]

此概率为某bit位在插入n个元素后未被置位的概率。因此,想保持错误率低,布隆过滤器的空间使用率需为50%。

      把我们之前的例子套进去,还是一亿个网址,若采用布隆过滤器,取k=8。因为n为1亿,所以总共需要 clip_image002[12] 被置位为1,又因为在保证误判率低且k和m选取合适时,空间利用率为50%,所以总空间为:

clip_image002[14]

如果用哈希表存储,每个网址对应成一个8byte的信息指纹,在保证效率的情况下哈希表的存储效率最好不超过50%。此时每个元素占8 bytes,总空间为:

clip_image002[10]

 

两者的空间占有率有着明显的差距,布隆过滤器是哈希表的1/8.

 

 

 

 

这篇关于Java集合框架分析(九)——布隆过滤器深入分析及其误判概率计算的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/231885

相关文章

Spring LDAP目录服务的使用示例

《SpringLDAP目录服务的使用示例》本文主要介绍了SpringLDAP目录服务的使用示例... 目录引言一、Spring LDAP基础二、LdapTemplate详解三、LDAP对象映射四、基本LDAP操作4.1 查询操作4.2 添加操作4.3 修改操作4.4 删除操作五、认证与授权六、高级特性与最佳

Spring Shell 命令行实现交互式Shell应用开发

《SpringShell命令行实现交互式Shell应用开发》本文主要介绍了SpringShell命令行实现交互式Shell应用开发,能够帮助开发者快速构建功能丰富的命令行应用程序,具有一定的参考价... 目录引言一、Spring Shell概述二、创建命令类三、命令参数处理四、命令分组与帮助系统五、自定义S

SpringSecurity JWT基于令牌的无状态认证实现

《SpringSecurityJWT基于令牌的无状态认证实现》SpringSecurity中实现基于JWT的无状态认证是一种常见的做法,本文就来介绍一下SpringSecurityJWT基于令牌的无... 目录引言一、JWT基本原理与结构二、Spring Security JWT依赖配置三、JWT令牌生成与

Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码

《Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码》:本文主要介绍Java中日期时间转换的多种方法,包括将Date转换为LocalD... 目录一、Date转LocalDateTime二、Date转LocalDate三、LocalDateTim

如何配置Spring Boot中的Jackson序列化

《如何配置SpringBoot中的Jackson序列化》在开发基于SpringBoot的应用程序时,Jackson是默认的JSON序列化和反序列化工具,本文将详细介绍如何在SpringBoot中配置... 目录配置Spring Boot中的Jackson序列化1. 为什么需要自定义Jackson配置?2.

Java中使用Hutool进行AES加密解密的方法举例

《Java中使用Hutool进行AES加密解密的方法举例》AES是一种对称加密,所谓对称加密就是加密与解密使用的秘钥是一个,下面:本文主要介绍Java中使用Hutool进行AES加密解密的相关资料... 目录前言一、Hutool简介与引入1.1 Hutool简介1.2 引入Hutool二、AES加密解密基础

Python 迭代器和生成器概念及场景分析

《Python迭代器和生成器概念及场景分析》yield是Python中实现惰性计算和协程的核心工具,结合send()、throw()、close()等方法,能够构建高效、灵活的数据流和控制流模型,这... 目录迭代器的介绍自定义迭代器省略的迭代器生产器的介绍yield的普通用法yield的高级用法yidle

Spring Boot项目部署命令java -jar的各种参数及作用详解

《SpringBoot项目部署命令java-jar的各种参数及作用详解》:本文主要介绍SpringBoot项目部署命令java-jar的各种参数及作用的相关资料,包括设置内存大小、垃圾回收... 目录前言一、基础命令结构二、常见的 Java 命令参数1. 设置内存大小2. 配置垃圾回收器3. 配置线程栈大小

SpringBoot实现微信小程序支付功能

《SpringBoot实现微信小程序支付功能》小程序支付功能已成为众多应用的核心需求之一,本文主要介绍了SpringBoot实现微信小程序支付功能,文中通过示例代码介绍的非常详细,对大家的学习或者工作... 目录一、引言二、准备工作(一)微信支付商户平台配置(二)Spring Boot项目搭建(三)配置文件

解决SpringBoot启动报错:Failed to load property source from location 'classpath:/application.yml'

《解决SpringBoot启动报错:Failedtoloadpropertysourcefromlocationclasspath:/application.yml问题》这篇文章主要介绍... 目录在启动SpringBoot项目时报如下错误原因可能是1.yml中语法错误2.yml文件格式是GBK总结在启动S