当前位置:   article > 正文

大厂面试官问我:布隆过滤器有不能扩容和删除的缺陷,有没有可以替代的数据结构呢?【后端八股文二:布隆过滤器八股文合集】

大厂面试官问我:布隆过滤器有不能扩容和删除的缺陷,有没有可以替代的数据结构呢?【后端八股文二:布隆过滤器八股文合集】

往期内容:

面试官问我: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数组发生哈希冲突怎么办?

布隆过滤器本质上就是哈希函数 + 位图
减少误判的两种方法:① 增加哈希函数的数量;② 增加位图(位数组)的长度

布隆过滤器如何实现?/ 让你设计布隆过滤器,你会怎么设计?/ 布隆过滤器如何计算?
  1. 初始化一个全 0 的位数组
  2. 定义 k 个独立的哈希函数
  3. 对于每个要插入的元素:

使用 k 个哈希函数计算出 k 个索引

将位数组中对应的 k 个位置设为 1

     4. 查询元素时:

使用 k 个哈希函数计算出 k 个索引

检查位数组中对应的 k 个位置是否全为 1,如果有一个为 0 则表示元素不存在

布隆过滤器如何评估大小?/ 考虑过对于上亿的数据布隆过滤器的数据量会很大吗?

布隆过滤器的主要参数包括:位数组长度m、哈希函数个数k、预计要插入的元素个数n

其中p为预期的最大误判率(一般为: 0.1%或更低 )

  1. m = -(n * ln(p)) / (ln(2)^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

公众号私信回复“免费资料”可免费获取简历模板以及技术亮点合集等免费资料

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/煮酒与君饮/article/detail/788320
推荐阅读
相关标签
  

闽ICP备14008679号