查询利器-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

相关文章

一文详解Java异常处理你都了解哪些知识

《一文详解Java异常处理你都了解哪些知识》:本文主要介绍Java异常处理的相关资料,包括异常的分类、捕获和处理异常的语法、常见的异常类型以及自定义异常的实现,文中通过代码介绍的非常详细,需要的朋... 目录前言一、什么是异常二、异常的分类2.1 受检异常2.2 非受检异常三、异常处理的语法3.1 try-

Java中的@SneakyThrows注解用法详解

《Java中的@SneakyThrows注解用法详解》:本文主要介绍Java中的@SneakyThrows注解用法的相关资料,Lombok的@SneakyThrows注解简化了Java方法中的异常... 目录前言一、@SneakyThrows 简介1.1 什么是 Lombok?二、@SneakyThrows

Java中字符串转时间与时间转字符串的操作详解

《Java中字符串转时间与时间转字符串的操作详解》Java的java.time包提供了强大的日期和时间处理功能,通过DateTimeFormatter可以轻松地在日期时间对象和字符串之间进行转换,下面... 目录一、字符串转时间(一)使用预定义格式(二)自定义格式二、时间转字符串(一)使用预定义格式(二)自

Redis Pipeline(管道) 详解

《RedisPipeline(管道)详解》Pipeline管道是Redis提供的一种批量执行命令的机制,通过将多个命令一次性发送到服务器并统一接收响应,减少网络往返次数(RTT),显著提升执行效率... 目录Redis Pipeline 详解1. Pipeline 的核心概念2. 工作原理与性能提升3. 核

Python正则表达式语法及re模块中的常用函数详解

《Python正则表达式语法及re模块中的常用函数详解》这篇文章主要给大家介绍了关于Python正则表达式语法及re模块中常用函数的相关资料,正则表达式是一种强大的字符串处理工具,可以用于匹配、切分、... 目录概念、作用和步骤语法re模块中的常用函数总结 概念、作用和步骤概念: 本身也是一个字符串,其中

Nginx location匹配模式与规则详解

《Nginxlocation匹配模式与规则详解》:本文主要介绍Nginxlocation匹配模式与规则,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、环境二、匹配模式1. 精准模式2. 前缀模式(不继续匹配正则)3. 前缀模式(继续匹配正则)4. 正则模式(大

Android实现在线预览office文档的示例详解

《Android实现在线预览office文档的示例详解》在移动端展示在线Office文档(如Word、Excel、PPT)是一项常见需求,这篇文章为大家重点介绍了两种方案的实现方法,希望对大家有一定的... 目录一、项目概述二、相关技术知识三、实现思路3.1 方案一:WebView + Office Onl

Java实现优雅日期处理的方案详解

《Java实现优雅日期处理的方案详解》在我们的日常工作中,需要经常处理各种格式,各种类似的的日期或者时间,下面我们就来看看如何使用java处理这样的日期问题吧,感兴趣的小伙伴可以跟随小编一起学习一下... 目录前言一、日期的坑1.1 日期格式化陷阱1.2 时区转换二、优雅方案的进阶之路2.1 线程安全重构2

Java中的JSONObject详解

《Java中的JSONObject详解》:本文主要介绍Java中的JSONObject详解,需要的朋友可以参考下... Java中的jsONObject详解一、引言在Java开发中,处理JSON数据是一种常见的需求。JSONObject是处理JSON对象的一个非常有用的类,它提供了一系列的API来操作J

HTML5中的Microdata与历史记录管理详解

《HTML5中的Microdata与历史记录管理详解》Microdata作为HTML5新增的一个特性,它允许开发者在HTML文档中添加更多的语义信息,以便于搜索引擎和浏览器更好地理解页面内容,本文将探... 目录html5中的Mijscrodata与历史记录管理背景简介html5中的Microdata使用M