查询利器-bloom-filter详解

2024-05-13 05:58

本文主要是介绍查询利器-bloom-filter详解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难。本文着重于在实现Bloom Filter的时候会使用到的一些技巧。

布隆过滤器的原理不难理解。相对于一个精简的HashMap的数据结构,存入数据的时候,不存入数据本身,只保存其Hash的值。可以用于判断该数据是否存在。其本质是用Hash对数据进行"有损压缩"的位图索引。详细参见。

Bloom_filter

 

错误率

如果用来存放Hash值的槽位足够多,那么碰撞的概率就会比较小。但是所占用的空间就会比较大。所以当分配空间的时候,需要通过你能容忍的错误率和需要存放的Key的数量来指定。如果所需存储的Key数量是n,错误率是p,所需要的槽位是m。有计算槽位的公式  m=nlnp(ln2)2.  ,也有计算概率的公式  p=(1e(m/nln2)n/m)(m/nln2)  。这些公式当然不是我推导出来的,想来也不太难,就不赘述推导过程了。下面这张图可以很好的表示n和m取不同的值的时候,p的值。

Bloom_filter

根据这张图。我们可以计算出所需要的内存使用量。如果把错误率控制在1%以下的话。

保存key数 占用空间
1万 64KB
10万 1MB
100万 16MB
1000万 256MB
1亿 <4GB

 

可见占用的空间在key的数量在百万级别还是很划算的,但到了上亿的级别就不那么划算了。

Bloom Filter的插入和查询都是常数级别的,所以最大的问题就是占用内存过大。而初次分配内存的时候,如果没有能够确认槽位的个数。如果分配过多会导致内存浪费,太少就会倒是错误率过高。下面提到的两个改进方案可以分别解决这两个问题。

折叠

折叠是指当你初始化一个Bloom Filter的时候,可以分配足够大的槽位,等到Key导入完毕后,可以对使用的槽位进行合并操作。具体方法是将槽位切成两半,一边完全叠加到另一边上。减少内存的使用量。检查key的代码要做稍许改变。例:

 

通过这个操作,可以使实际使用的内存量减半。多执行几次,能减少更多。

动态扩展

通过折叠操作,可以解决分配过大的问题,但是如果一开始分配过小,就需要扩展槽位才行。如何扩展呢?只要按原尺寸再建立一个Bloom Filter数组。原来的那个保存起来,不再写入。有新的写请求的时候,就将数据写入到新的那个Bloom Filter数组里面去。等到新的也写满了,就再建立一个,以此类推。查询的时候,就需要遍历每一个Bloom Filter数组才行。但因为查询一个Bloom Filter数组的速度很快,查询一组Bloom Filter数组也不会太影响性能。使用这种手段可以是Bloom Filter的大小可以轻易的扩展。但这样做有个的缺陷,就是错误率会随着数组的增加而上升,因为实际的数组长度并没有增加。

d-bloom-filter

通过上面的两个方法,就可以解决BloomFilter的分配内存的问题。但无论哪种方法都有自己局限性,折叠每次只能减半,不是很精确。动态增加的方法会造成错误率增加。最好还是能预先估计到这个BloomFilter的容量。

这篇关于查询利器-bloom-filter详解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

springboot security快速使用示例详解

《springbootsecurity快速使用示例详解》:本文主要介绍springbootsecurity快速使用示例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝... 目录创www.chinasem.cn建spring boot项目生成脚手架配置依赖接口示例代码项目结构启用s

Python中随机休眠技术原理与应用详解

《Python中随机休眠技术原理与应用详解》在编程中,让程序暂停执行特定时间是常见需求,当需要引入不确定性时,随机休眠就成为关键技巧,下面我们就来看看Python中随机休眠技术的具体实现与应用吧... 目录引言一、实现原理与基础方法1.1 核心函数解析1.2 基础实现模板1.3 整数版实现二、典型应用场景2

一文详解SpringBoot响应压缩功能的配置与优化

《一文详解SpringBoot响应压缩功能的配置与优化》SpringBoot的响应压缩功能基于智能协商机制,需同时满足很多条件,本文主要为大家详细介绍了SpringBoot响应压缩功能的配置与优化,需... 目录一、核心工作机制1.1 自动协商触发条件1.2 压缩处理流程二、配置方案详解2.1 基础YAML

Python实现无痛修改第三方库源码的方法详解

《Python实现无痛修改第三方库源码的方法详解》很多时候,我们下载的第三方库是不会有需求不满足的情况,但也有极少的情况,第三方库没有兼顾到需求,本文将介绍几个修改源码的操作,大家可以根据需求进行选择... 目录需求不符合模拟示例 1. 修改源文件2. 继承修改3. 猴子补丁4. 追踪局部变量需求不符合很

java中反射(Reflection)机制举例详解

《java中反射(Reflection)机制举例详解》Java中的反射机制是指Java程序在运行期间可以获取到一个对象的全部信息,:本文主要介绍java中反射(Reflection)机制的相关资料... 目录一、什么是反射?二、反射的用途三、获取Class对象四、Class类型的对象使用场景1五、Class

golang 日志log与logrus示例详解

《golang日志log与logrus示例详解》log是Go语言标准库中一个简单的日志库,本文给大家介绍golang日志log与logrus示例详解,感兴趣的朋友一起看看吧... 目录一、Go 标准库 log 详解1. 功能特点2. 常用函数3. 示例代码4. 优势和局限二、第三方库 logrus 详解1.

一文详解如何从零构建Spring Boot Starter并实现整合

《一文详解如何从零构建SpringBootStarter并实现整合》SpringBoot是一个开源的Java基础框架,用于创建独立、生产级的基于Spring框架的应用程序,:本文主要介绍如何从... 目录一、Spring Boot Starter的核心价值二、Starter项目创建全流程2.1 项目初始化(

Spring Boot3虚拟线程的使用步骤详解

《SpringBoot3虚拟线程的使用步骤详解》虚拟线程是Java19中引入的一个新特性,旨在通过简化线程管理来提升应用程序的并发性能,:本文主要介绍SpringBoot3虚拟线程的使用步骤,... 目录问题根源分析解决方案验证验证实验实验1:未启用keep-alive实验2:启用keep-alive扩展建

Java异常架构Exception(异常)详解

《Java异常架构Exception(异常)详解》:本文主要介绍Java异常架构Exception(异常),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. Exception 类的概述Exception的分类2. 受检异常(Checked Exception)

C#基础之委托详解(Delegate)

《C#基础之委托详解(Delegate)》:本文主要介绍C#基础之委托(Delegate),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 委托定义2. 委托实例化3. 多播委托(Multicast Delegates)4. 委托的用途事件处理回调函数LINQ