Redis布隆过滤器原理及应用场景「建议收藏」

Redis布隆过滤器原理及应用场景「建议收藏」1、布隆过滤器是什么?(判断某个key一定不存在)本质上布隆过滤器是一种数据结构,比较巧妙的概率型数据结构特点是高效地插入和查询,可以用来告诉你“某样东西一定不存在或者可能存在”。相比于传统的List、Set、Map等数据结构,它更高效、占用空间更少,但是缺点是其返回的结果是概率性的,而不是确切的。使用:1.布隆过滤器在NoSQL数据库领域中应用的非常广泛2….

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

Jetbrains全系列IDE稳定放心使用

1、布隆过滤器是什么?(判断某个key一定不存在)

  1. 本质上布隆过滤器是一种数据结构,比较巧妙的概率型数据结构

  2. 特点是高效地插入和查询,可以用来告诉你 “某样东西一定不存在或者可能存在”。

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

使用:

1. 布隆过滤器在NoSQL数据库领域中应用的非常广泛

2. 当用户来查询某一个row时,可以先通过内存中的布隆过滤器过滤掉大量不存在的row请求,然后去再磁盘进行查询

3. 布隆过滤器说某个值不存在时,那肯定就是不存在,可以显著降低数据库IO请求数量

2、应用场景

1)场景1(给用户推荐新闻)

  1. 当用户看过的新闻,肯定会被过滤掉,对于没有看多的新闻,可能会过滤极少的一部分(误判)。

  2. 这样可以完全保证推送给用户的新闻都是无重复的。

2)场景2(爬虫url去重)

  1. 在爬虫系统中,我们需要对url去重,已经爬取的页面不再爬取

  2. 当url高达几千万时,如果一个集合去装下这些URL地址非常浪费空间

  3. 使用布隆过滤器可以大幅降低去重存储消耗,只不过也会使爬虫系统错过少量页面

3、布隆过滤器原理

  1. 每个布隆过滤器对应到Redis的数据结构是一个大型的数组和几个不一样的无偏hash函数

  2. 如下图:f、g、h就是这样的hash函数(无偏差指让hash映射到数组的位置比较随机)

添加:值到布隆过滤器

  • 1)向布隆过滤器添加key,会使用 f、g、h hash函数对key算出一个整数索引,然后对长度取余

  • 2)每个hash函数都会算出一个不同的位置,把算出的位置都设置成1就完成了布隆过滤器添加过程

查询:布隆过滤器值

  • 1)当查询某个key时,先用hash函数算出一个整数索引,然后对长度取余

  • 2)当你有一个不为1时肯定不存在这个key,当全部都为1时可能有这个key

  • 3)这样内存中的布隆过滤器过滤掉大量不存在的row请求,然后去再磁盘进行查询,减少IO操作

删除:不支持

  • 1)目前我们知道布隆过滤器可以支持 add 和 isExist 操作

  • 2)如何解决这个问题,答案是计数删除,但是计数删除需要存储一个数值,而不是原先的 bit 位,会增大占用的内存大小。

  • 3)增加一个值就是将对应索引槽上存储的值加一,删除则是减一,判断是否存在则是看值是否大于0。

在这里插入图片描述

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

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

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

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

(0)
blank

相关推荐

  • MySQL数据查询之单表查询

    单表查询简单查询-创建表DROPTABLEIFEXISTS`person`;CREATETABLE`person`(`id`int(11)NOTNULLAUTO_IN

  • 写java代码的软件_新手编写java代码使用什么软件

    写java代码的软件_新手编写java代码使用什么软件新手编写java代码常用的编辑器有:1、eclipseEclipse是一个开放源代码的、基于Java的可扩展开发平台。就其本身而言,它只是一个框架和一组服务,用于通过插件组件构建开发环境。幸运的是,Eclipse附带了一个标准的插件集,包括Java开发工具(JavaDevelopmentKit,JDK)。(视频教程推荐:java视频)2、notepad++Notepad++是在微软视窗环境…

  • adventureworksdw2008r2_world library

    adventureworksdw2008r2_world libraryAdventureWorksDatabases2008下载地址:RECOMMENDEDDOWNLOADAdventureWorks2012_Database.zipexample,37158K,uploadedAug29,2012-232028downloadsOTHERAVAILABLEDOWNLOADSAdventure…

  • 如何判断一个网址是否安全_域名和dns的区别

    如何判断一个网址是否安全_域名和dns的区别前言近几年,互联网发生着翻天覆地的变化,尤其是我们一直习以为常的HTTP协议,在逐渐的被HTTPS协议所取代,在浏览器、搜索引擎、CA机构、大型互联网企业的共同促进下,互联网迎来了“HTTPS加密时代”,HTTPS将在未来的几年内全面取代HTTP成为传输协议的主流。读完本文,希望你能明白: HTTP通信存在什么问题 HTTPS如何改进HTTP存在那些问题 HTTP…

    2022年10月16日
  • vs2015注册码[通俗易懂]

    vs2015注册码[通俗易懂]VisualStudioProfessional2015简体中文版(专业版)KEY:HMGNV-WCYXV-X7G9W-YCX63-B98R2VisualStudioEnterprise2015简体中文版(企业版)KEY:HM6NR-QXX7C-DFW2Y-8B82K-WTYJV专业版:HMGNV-WCYXV-X7G9W-YCX63-B98R2企业版:HM6NR-QXX7C-DFW2Y…

  • 自己动手写操作系统在线阅读_如何理解写作是一个整体系统

    自己动手写操作系统在线阅读_如何理解写作是一个整体系统最近开始看《自己动手写操作系统》,虽然很早以前就读过一点点,但一直没有机会动手实践。本着光说不练假把式的原则,今天动手实践了开头的一部分。(说得这么正经其实你就是看了一点点吧!囧)废话不多说,在这里做一个小小的总结。实验环境:操作系统:win7旗舰版64位 汇编编译器:NASM 2.12.02虚拟机:VirtualPC_2007软盘/虚拟软盘写引导扇区工具:Flopp

发表回复

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

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