误判率也被称为"假阳性率",即判断一个元素在布隆过滤器中但实际上并不在的概率。误判率受到以下两个因素的影响: 1.哈希函数的个数:哈希函数的个数越多,误判率越低。因为随着哈希函数个数的增加,每个元素对应的位数组位置被置为1的概率也会增加,从而提高了判断正确的准确性。 2.位数组的大小:位数组的大小越...
布隆过滤器的误判率是一个概率,它表示在某一次查询时,布隆过滤器可能会出现的误判的概率。通常情况下,布隆过滤器的误判率越低越好,这意味着查询的结果精度越高。 三、如何降低布隆过滤器的误判率 要降低布隆过滤器的误判率,有以下几个办法: 1.当bit数组变长时,将m值增加,这样可以减少碰撞概率,从而降低误判率。
通过上述公式,我们可以计算出布隆过滤器的误判率。可以看到,误判率受三个因素影响:哈希函数的个数k,插入的元素个数n和布隆过滤器的总位数m。当k和m固定时,随着插入元素个数的增加,误判率也会增加。当误判率较大时,可以通过增加哈希函数的个数k或增加布隆过滤器的总位数m来降低误判率。
有误判率存在。 不支持删除。 2.4 适用场景 预防缓存穿透:布隆过滤器快速判断数据是否存在,避免通过查询数据库来判断数据是否存在。 网络爬虫:布隆过滤器可以用来去重已经爬取过的URL。 邮箱的垃圾邮件过滤。 黑白名单。 三、 布隆过滤器原理 3.1 结构 布隆过滤器实现原理就是一个超大位数的数组和多个不同Hash算法函...
业务对错误的容忍程度。比如1000个允许错一个，那么误判概率应该在千分之一内。很多布隆过滤器工具都提供...
实际情况中,布隆过滤器的长度 m 可以根据给定的误判率(FFP)的和期望添加的元素个数 n 的通过如下公式计算: 了解完上述的内容之后,我们可以得出一个结论,当我们搜索一个值的时候,若该值经过 K 个哈希函数运算后的任何一个索引位为 ”0“,那么该值肯定不在集合中。但如果所有哈希索引值均为”1“,则只能说该...
在使用bloom filter时,绕不过的两点是预估数据量n以及期望的误判率fpp, 在实现bloom filter时,绕不过的两点就是hash函数的选取以及bit数组的大小。 对于一个确定的场景,我们预估要存的数据量为n,期望的误判率为fpp,然后需要计算我们需要的Bit数组的大小m,以及hash函数的个数k,并选择hash函数 ...
最后也可以通过自己期待的误判率P和期待添加的个数n,来大致计算出布隆过滤器的位数组的长度: m=−(nInP(In2)2) 上面就是误判率的大致计算方式,同时也提示我们,可以根据自己业务的数据量以及误判率,来调整我们的数组的大小。 布隆过滤器的作用 除了我们前面说的过滤爬虫恶意请求,还可以对一些URL进行去重,过滤海...
最终,某一元素没在集合中,但是被误判在集合中的概率为: 对于实际应用,我们的目标应该是使错判率 ε 最小,即需要使函数: 取到最小值。求最小值的过程略,直接上结论:当 k = (ln2)(m/n)时,错判率最小,因为 k 需要取整数,所以即当 k = [(ln2)(m/n)]时,布隆过滤器有最好的效果。以下是 k 取最...