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

往期内容：

面试官问我：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%或更低 ）

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

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