大厂面试官问我:布隆过滤器有不能扩容和删除的缺陷,有没有可以替代的数据结构呢?【后端八股文二:布隆过滤器八股文合集】
往期内容:
面试官问我:Redis处理点赞,如果瞬时涌入大量用户点赞(千万级),应当如何进行处理?【后端八股文(1)】-CSDN博客
本文为【布隆过滤器八股文合集】初版,后续还会进行优化更新,欢迎大家评论交流~
大家第一眼看到这个标题,不知道心中是否有答案了?在面试当中,面试官经常对项目亮点进行深挖,来考察你对这个项目亮点的理解以及思考!这个时候,你如果可以回答出面试官的问题,甚至是主动说出自己的思考,那在面试中是大大加分的~
布隆过滤器
具体实现
(1)使用开源的谷歌开源工具类Guava
Spring Boot(七十四):集成Guava 库实现布隆过滤器(Bloom Filter)_guava bloomfilter.create 设置-CSDN博客
(2) 开源Redisson的RBloomFilter
(3) Redis官方提供布隆过滤器插件
(4) Redis提供的bitMap,需要自己实现
各自的缺点:
Guava存储在机器当中,只适合单机,不适合分布式环境当中;
Redis插件需要复杂的配置和高成本支持;
Redis的bitMap需要额外自己去实现;
Redisson 连接Redis即可使用
底层原理?/布隆过滤器如何判断那个字段在缓存中的呢?
一种数据结构,用于判断一个元素是否在一个集合中。它是一种概率型算法,能够快速判断一个元素是否在一个集合中,但不能保证 100% 准确。
布隆过滤器通常用于大数据场景中,例如垃圾邮件过滤、网络爬虫中的 URL 去重等。它的优点是快速判断一个元素是否在集合中,时间复杂度为 O(1),空间复杂度为 O(n),可以满足高并发场景的需求。
原理(一个元素多个哈希函数)
将一个元素通过多个哈希函数计算得到多个哈希值,然后将这些哈希值对应到一个长度为 m 的位数组上,将位数组中对应位置置为 1。当判断一个元素是否在集合中时,需要再次计算多个哈希值,然后判断位数组中对应位置是否为 1,如果都为 1 则认为元素在集合中,否则认为元素不在集合中。
或者
①初始化:首先,布隆过滤器会初始化一个位数组,所有位都被设置为0。
②添加元素:当要将一个元素加入到布隆过滤器中时,将该元素通过多个哈希函数计算出多个哈希值,然后将位数组中对应的位置设置为1。
③查询元素:当要查询一个元素是否存在于布隆过滤器中时,将该元素通过相同的哈希函数计算出多个哈希值,然后检查对应的位数组位置是否都为1。如果所有位置都为1,则该元素可能存在于布隆过滤器中;如果存在任何一个位置为0,则该元素一定不存在于布隆过滤器
会发生错误,可能把不存在的认为存在,但是不会把存在的认为不存在。
为什么需要多个hash函数,有多少个bitmap实现的?/ 为什么布隆过滤器为什么要有5个特殊值? 布隆过滤器只有一个特殊值可以吗?
为了降低布隆过滤器的误判率
优点
1. 空间效率高:布隆过滤器只需要使用一个位数组和多个哈希函数来表示集合,相比使用传统的哈希表或者树等数据结构,布隆过滤器的空间占用更小。
2. 查询效率高:布隆过滤器通过多个哈希函数将元素映射到多个位置,所以查询一个元素只需要进行几次位操作,时间复杂度较低。
3. 可扩展性好:布隆过滤器支持动态添加元素,可以根据需要进行扩展。
布隆过滤器有什么缺点?
1、误判:可能将某个不存在的元素判断为存在
“布隆过滤器说某个元素存在,则大概率在。布隆过滤器说某个元素不在,则一定不在”
2、无法删除: 不支持元素的删除:由于多个元素可能映射到同一个位,所以无法准确地删除一个元素,只能通过重新构建布隆过滤器来实现。
布隆过滤器的元素能否删除?
不能,因为删除一个元素会影响其他元素的判断结果
布隆过滤器怎么删除key?
(1)重新构建布隆过滤器( Scalable Bloom Filter 原理 )
流程如下:
① 创建一个新的空布隆过滤器
② 将原布隆过滤器中的所有元素(除了要删除的元素)重新添加到新的布隆过滤器中
③ 用新的布隆过滤器替换原有的布隆过滤器
(2)使用计数器
在原有基础上,加上计数器,当元素加入时,计数器加一,反之,计数器减一。当计数器为零时,key被删除。
布隆过滤器如何提高容错能力?/ 怎么降低误判率 / 布隆过滤器的01数组发生哈希冲突怎么办?
布隆过滤器本质上就是哈希函数 + 位图
减少误判的两种方法:① 增加哈希函数的数量;② 增加位图(位数组)的长度
布隆过滤器如何实现?/ 让你设计布隆过滤器,你会怎么设计?/ 布隆过滤器如何计算?
- 初始化一个全 0 的位数组
- 定义 k 个独立的哈希函数
- 对于每个要插入的元素:
使用 k 个哈希函数计算出 k 个索引
将位数组中对应的 k 个位置设为 1
4. 查询元素时:
使用 k 个哈希函数计算出 k 个索引
检查位数组中对应的 k 个位置是否全为 1,如果有一个为 0 则表示元素不存在
布隆过滤器如何评估大小?/ 考虑过对于上亿的数据布隆过滤器的数据量会很大吗?
布隆过滤器的主要参数包括:位数组长度m、哈希函数个数k、预计要插入的元素个数n
其中p为预期的最大误判率(一般为: 0.1%或更低 )
m = -(n * ln(p)) / (ln(2)^2)
k = (m/n) * ln(2)
以1亿为例,
m = -(100,000,000 * ln(0.001)) / (ln(2)^2) ≈ 479,430,000
即需要一个长度为约 4.79 亿比特的位数组
计算哈希函数的数量:
k = (m/n) * ln(2) ≈ 7
所以需要使用 7 个相互独立的哈希函数
已知1 字节 = 8 比特
那么位数组所需的存储空间为:
479,430,000 / 8 = 59,928,750 字节
再转换为 GB:
59,928,750 / (1024 * 1024 * 1024) = 55.85 GB
综上所述,对于存储 1 亿个元素,允许 0.1% 最大误判率的布隆过滤器,需要约 55.85 GB 的存储空间。
千万级数据用布隆过滤器初始化的时候 redis 太慢了,有没有什么好方法?
(1)分批初始化
将大量数据分批次进行初始化,每次初始化一部分
这样可以减轻 Redis 单次操作的压力
可以考虑利用多线程或异步任务的方式来加速
(2)使用本地内存初始化
先在本地内存中构建好布隆过滤器
然后一次性将整个布隆过滤器数据同步到 Redis 中
这样可以利用内存的高速计算能力来加速初始化
(3)采用分布式架构
将布隆过滤器拆分到多个 Redis 实例中
每个实例负责部分数据的初始化和查询
这样可以利用分布式计算的优势来提升性能
布隆过滤器在异常情况下,也会出现缓存击穿,怎么考虑的?
使用多级缓存结构:
除了布隆过滤器,还可以使用其他缓存手段,形成多级缓存
当布隆过滤器判断数据不存在时,可以尝试访问其他缓存层
实现布隆过滤器(1.增量数据怎么放入布隆过滤器;2.怎么合并两个布隆过滤器)?
(1)当有新的数据需要加入时,可以采用以下方法:
创建一个新的、更大的布隆过滤器。
将原有的布隆过滤器中的所有数据 hash 并设置到新的布隆过滤器中。
再将新的数据 hash 并设置到新的布隆过滤器中。
(2)合并两个布隆过滤器的具体做法
确保两个布隆过滤器的大小(位数组长度)相同。
对两个布隆过滤器的对应位进行逻辑或操作(OR),得到合并后的新布隆过滤器。
布隆过滤器的缺陷(不能扩容和删除),目前有没有能够利用到的数据结构来做一个替代呢?
(1)可扩容:
Scalable Bloom Filter (SBF):(动态扩容原理)重新计算新的布隆过滤器,将旧的过滤器迁移至新的
(2)可删除:
Counting Bloom Filter (CBF):(计数布隆过滤器)插入的时候,会将该位对应的值+1,删除则减一
场景题:有千万级数据,如何判断一个整数是否存在?
使用布隆过滤器
场景题:10亿数据,5亿内存,如何查找重复元素?
布隆过滤器
场景题:大数据量的情况下如何进行去重?
布隆过滤器
场景题:布隆过滤器使用一年后和一年前相比有什么不同?
元素个数增加,导致误判率上升
需要调整参数来重新控制误判率
内存占用显著增加,可能影响系统性能
---------------------------------------------------------------------------------------------------------------
更多精彩内容以及一手消息请关注公众号:绝命Coding
公众号私信回复“免费资料”可免费获取简历模板以及技术亮点合集等免费资料
相关文章:

大厂面试官问我:布隆过滤器有不能扩容和删除的缺陷,有没有可以替代的数据结构呢?【后端八股文二:布隆过滤器八股文合集】
往期内容: 面试官问我:Redis处理点赞,如果瞬时涌入大量用户点赞(千万级),应当如何进行处理?【后端八股文(1)】-CSDN博客 本文为【布隆过滤器八股文合集】初版,…...

PHP米表域名出售管理源码带后台
源码介绍 html5米表源码PHP域名销售程序安装方法: 本站已测试,各项功能正常,功能易用,不复杂,非常适合个人米表使用 1、所有文件传至网站目录 2、浏览器执行http://你的访问网址/install 3、输入mysql帐号及密码信息,提交安装 源码截图 源码下载 …...

【开发12年码农教你】Android端简单易用的SPI框架-——-SPA
Service(priority 1) public class APrinterService implements IPrinterService { Override public void print() { System.out.println(“this is a printer service.”); } } 复制代码 B模块 —— BPrinterService Service(path“b_printer”, priority 2) public class…...

以太坊==MetaMask获取测试币最新网址
估算分数https://community.infura.io/t/unable-to-receive-sepolia-eth-from-faucet/7715 Gitcoin Passport 水龙头地址,填入自己的测试地址 水龙头项目地址 GitHub - pk910/PoWFaucet: Modularized faucet for EVM chains with different protection methods (…...
军用FPGA软件 Verilog语言的编码准测之触发器、锁存器
军用FPGA软件 Verilog语言的编码准测之触发器、锁存器 语言 :Verilg HDL EDA工具:ISE、Vivado、Quartus II 军用FPGA软件 Verilog语言的编码准测之触发器、锁存器一、引言二、基本编程规范之触发器强制准则1---禁止在同一个 always 语句中混合使用有复位…...

智能汽车 UI 风格独具魅力
智能汽车 UI 风格独具魅力...
javafx例子笔记
文章目录 创建过程javafx独立版报错 Exception in thread "WindowsNativeRunloopThread" java.lang.NoSuchMethodError: <init> javafx是java gui工具。 一般会转换为exe,成为可交互的应用。 那么来个简单的例子吧。 先说明一点,javafx不…...

【ajax基础】回调函数地狱
一:什么是回调函数地狱 在一个回调函数中嵌套另一个回调函数(甚至一直嵌套下去),形成回调函数地狱 回调函数地狱存在问题: 可读性差异常捕获严重耦合性严重 // 1. 获取默认第一个省份的名字axios({url: http://hmaj…...

SparkSQL的分布式执行引擎-Thrift服务:学习总结(第七天)
系列文章目录 SparkSQL的分布式执行引擎 1、启动Thrift服务 2、beeline连接Thrift服务 3、开发工具连接Thrift服务 4、控制台编写SQL代码 文章目录 系列文章目录前言一、SparkSQL的分布式执行引擎(了解)1、启动Thrift服务2、beeline连接Thrift服务3、开发工具连接Thrift服务4、…...

联华集团:IT团队如何实现从成本中心提升至价值中心|OceanBase 《DB大咖说》(十)
OceanBase《DB大咖说》第 10 期,我们邀请到了联华集团的CTO楼杰,来分享他如何思考 IT 业务价值,以及联华华商数据库的升级实践。 楼杰从大学毕业后就进入了联华工作,并一直扎根在近 20 年的,从一名底层的技术员成长为…...

计算机系统基础实训五—CacheLab实验
实验目的与要求 1、让学生更好地应用程序性能的优化方法; 2、让学生更好地理解存储器层次结构在程序运行过程中所起的重要作用; 3、让学生更好地理解高速缓存对程序性能的影响; 实验原理与内容 本实验将帮助您了解缓存对C程序性能的影响…...
PHP框架之CodeIgniter框架
CodeIgniter框架详细说明 CodeIgniter是一个简单而强大的PHP框架,专为快速开发Web应用程序而设计。它遵循MVC(模型-视图-控制器)设计模式,为开发者提供了丰富的功能和灵活性,同时保持代码的轻量级和易于管理。CodeIgn…...

714. 买卖股票的最佳时机含手续费
714. 买卖股票的最佳时机含手续费 原题链接:完成情况:解题思路:ExplanationSummary 参考代码:_714买卖股票的最佳时机含手续费 错误经验吸取 原题链接: 714. 买卖股票的最佳时机含手续费 https://leetcode.cn/probl…...

Linux系统查看程序内存及CPU占用
文章目录 1.free命令2.top命令3.PS命令3.1 查看内存占用前10位:3.2 查看CPU占用前10位 参考文档 1.free命令 可以通过free命令查看物理内存占用情况 #单位KB free #单位MB free -m #单位GB free -h 2.top命令 输入top命令,会输出定时刷新的程序PID、内…...

数据结构7---图
一、定义 对于图的定义,我们需要明确几个注意的地方:一线性表中我们把数据元素叫元素,树中叫结点,在途中数据元素我们则称之为顶点(Vertex)。 对于图的定义,我们需要明确几个注意的地方: 线性表中我们把数据元素叫元素…...

Excel 如何复制单元格而不换行
1. 打开excle, sheet1右键单击>查看代码>插入>模块 输入代码 Sub CopyText() Updated by NirmalDim xAutoWrapper As ObjectSet xAutoWrapper New DataObject or GetObject("New:{1C3B4210-F441-11CE-B9EA-00AA006B1A69}")xAutoWrapper.SetText ActiveC…...

前端 CSS 经典:mix-blend-mode 属性
前言:这是一个混合属性,作用是将两个颜色混合生成一个新颜色。可以将视频和文字相融合,产生动态文字效果。 效果 实现代码 <!DOCTYPE html> <html lang"en"><head><meta charset"utf-8" />&l…...
OpenCV--滤波器(一)
低通滤波器 代码和笔记 代码和笔记 import cv2 import numpy as np""" 滤波器--用于图像处理的重要工具,它们可以根据图像中像素的邻域信息来修改像素值,以实现去噪、模糊、锐化、边缘检测等效果。低通滤波器(Low-pass Filte…...

MK的前端精华笔记
文章目录 MK的前端精华笔记第一阶段:前端基础入门1、(1)、(2)、 2、3、4、5、6、7、 第二阶段:组件化与移动WebAPP开发1、(1)、(2)、 2、3、4、5、6、7、 第三…...
低代码平台框架:开源选型、实践与应用深度解析
文章目录 1.1 低代码平台的重要性与应用背景2.1 表单建模2.2 流程设计2.3 报表(打印)可视化2.4 代码生成器2.5 系统管理2.6 前端UI开源选型3.1 如何选择合适的开源框架3.2 市场上的主要开源低代码平台对比3.3 开源项目的技术栈与优缺点分析 5.1 成功案例…...

shell脚本--常见案例
1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件: 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统
医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上,开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识,在 vs 2017 平台上,进行 ASP.NET 应用程序和简易网站的开发;初步熟悉开发一…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了: 这一篇我们开始讲: 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下: 一、场景操作步骤 操作步…...

P3 QT项目----记事本(3.8)
3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...
第25节 Node.js 断言测试
Node.js的assert模块主要用于编写程序的单元测试时使用,通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试,通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...
Neo4j 集群管理:原理、技术与最佳实践深度解析
Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

JVM 内存结构 详解
内存结构 运行时数据区: Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器: 线程私有,程序控制流的指示器,分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 每个线程都有一个程序计数…...

搭建DNS域名解析服务器(正向解析资源文件)
正向解析资源文件 1)准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2)服务端安装软件:bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...

免费数学几何作图web平台
光锐软件免费数学工具,maths,数学制图,数学作图,几何作图,几何,AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...

[大语言模型]在个人电脑上部署ollama 并进行管理,最后配置AI程序开发助手.
ollama官网: 下载 https://ollama.com/ 安装 查看可以使用的模型 https://ollama.com/search 例如 https://ollama.com/library/deepseek-r1/tags # deepseek-r1:7bollama pull deepseek-r1:7b改token数量为409622 16384 ollama命令说明 ollama serve #:…...