专栏首页兜兜毛毛布隆过滤器

布隆过滤器

什么是布隆过滤器

本质上布隆过滤器是一种数据结构,比较巧妙的概率型数据结构(probabilistic data structure),特点是高效地插入和查询,可以用来告诉你 “某样东西一定不存在或者可能存在”。

相比于传统的 List、Set、Map 等数据结构,它更高效、占用空间更少,但是缺点是其返回的结果是概率性的,而不是确切的。

实现原理

与HashMap比较想象,不同之处在于布隆过滤器是存储的Bit位数组,内容值只有1 与 0 非常显著的减少了存储大小。所以布隆过滤器只能判断是否匹配,而无法获取对应匹配值。

了解HashMap数据结构的同学都应该知道HashMap会有概率发生碰撞,在发生碰撞时会生成链表或红黑树来解决,那布隆过滤器是如何解决这个问题的呢?

布隆过滤器数据结构

上图边表示分别存储A、B、C三个值,与下边数组的连接线分别表示不同的Hash值地址。通过过一个写入的值计算多个Hash地址,这样就可以尽量减少碰撞的可能,但绝对无法做到绝对不碰撞。

只能通过增加计算Hash的条数或增加数组长度来减少碰撞可能。

布隆过滤器如何支持删除

根据上边了解到的信息,我们知道因布隆过滤器是使用bit位数组存储的,如果支持删除操作的话,可能会影响其他值的匹配。那么我们还有其他方式来使布隆过滤器支持删除吗?

我们可以改变一下数据结构,将数组改为计数形式就可以实现,用空间来换功能。

适用场景

  1. 利用布隆过滤器减少磁盘 IO 或者网络请求,因为一旦一个值必定不存在的话,我们可以不用进行后续昂贵的查询请求。(缓存穿透)

我的博客即将同步至腾讯云+社区,邀请大家一同入驻:https://cloud.tencent.com/developer/support-plan?invite_code=1ro14ignkt5pb

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【DB笔试面试569】在Oracle中,SQL如何优化?SQL优化的关注点有哪些?

    随着数据库中数据量的增长,系统的响应速度就成为目前系统需要解决的最主要的问题之一。系统优化中一个很重要的方面就是SQL语句的优化。对于大量数据,劣质SQL语句和...

    小麦苗DBA宝典
  • 排序-真的了解快速排序了吗,请解答下题

    我们分析上面的示例,其实比较的就是下一个区间起始值是否在上一个区间的范围内,依次比较,直到匹配失败,就把这个已经匹配过的最小值和最大值放入一个新的区间。

    阿伟
  • 2019GEOJSON标准格式学习

    最近做的项目需要详细了解geojson,因此查了一些资料,现在整理一份标准格式的记录,要理解本文需要首先了解json的基本知识,这里不过多展开,可以去参考w3s...

    蛰虫始航
  • 学Python,从列表推导到zip()函数,这五种技巧应知应会

    在本文中,作者介绍了 5 种方法,也许在入门阶段时,我们还不太了解它们,但在实战中这 5 个技巧非常实用。

    CDA数据分析师
  • 详解 React 16 的 Diff 策略

    这是我 Deep In React 系列的第二篇文章,如果还没有读过的强烈建议你先读第一篇:详谈 React Fiber 架构(1)。

    Nealyang
  • 还担心面试官问闭包?

    为什么我们需要理解并且掌握闭包,且不说大道理,就问你要不要成为JavaScript高手?不要?那你要不要面试找工作嘛。。。

    Nealyang
  • Ajax 知识入门从这里开始【简约版,后期重新归纳整理】

    Ajax(Asynchronous JavaScript and XML) 异步的 JavaScript 和 XML

    BWH_Steven
  • 【转】Linux内存管理(最透彻的一篇)

    摘要:本章首先以应用程序开发者的角度审视Linux的进程内存管理,在此基础上逐步深入到内核中讨论系统物理内存管理和内核内存的使用方法。力求从外到内、水到渠成地引...

    用户3033338
  • 【Miscalculation UVALive - 6833 】【模拟】

    题目讲的是给你一个串,里面是加法、乘法混合运算(个人赛中误看成是加减乘除混合运算),有两种算法,一种是乘法优先运算,另一种是依次从左向右运算(不管它是否乘在前还...

    _DIY
  • Linux内存管理(最透彻的一篇)【转】

    转自:https://www.cnblogs.com/ralap7/p/9184773.html

    用户3033338

扫码关注云+社区

领取腾讯云代金券