huihttp 2021-11-27 17:05 采纳率: 0%
浏览 9
已结题

布隆过滤器为什么不用多个数组

问题遇到的现象和发生背景

很多帖子解释时都使用的一下这张图

img


也就是三个hash函数算出来的结果都存到了一个数组中,这样不就存在一个问题,假如我的数组只有12kb = 12 *1024 *8 = 98304 个bit位数,极端情况下第一个hashcode不冲突的情况下 9w多个字符串就把所有位都设置成了1,这时候 布隆过滤器不就失效了吗? 所有key 过来都会得到true的结果
而且图中蓝色的hashcode1结果 影响到了红色的hashcode2函数结果

问题相关代码,请勿粘贴截图
运行结果及报错内容
我的解答思路和尝试过的方法

但是我们如果使用三个数组,三个hash函数算出的结果存到三个数组中,这样一个字符串过来是否存在需要判断三个数组都满足,这时候hash碰撞概率就是 3W3w3w = 9w亿 ,而把这些槽位都占满的情况 除非是三个hash函数同时都不碰撞,那这三个函数实现肯定有问题。

我想要达到的结果

三个函数存到三个数组,以减少三个hash函数的互相影响

img

  • 写回答

0条回答 默认 最新

    报告相同问题?

    问题事件

    • 系统已结题 12月5日
    • 修改了问题 11月27日
    • 修改了问题 11月27日
    • 创建了问题 11月27日