深圳做网上商城网站,百度app下载安装,专门做本子的网站,天津哪里有做网站的往期内容#xff1a; 面试官问我#xff1a;Redis处理点赞#xff0c;如果瞬时涌入大量用户点赞#xff08;千万级#xff09;#xff0c;应当如何进行处理#xff1f;【后端八股文#xff08;1#xff09;】-CSDN博客 本文为【布隆过滤器八股文合集】初版#xff0c… 往期内容 面试官问我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
公众号私信回复“免费资料”可免费获取简历模板以及技术亮点合集等免费资料
