数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究性能指标
布隆过滤器的性能指标有三个可以权衡：计算或执行时间（对应于散列函数的数量 k）、过滤器的大小（对应于位数 m）和错误概率（对应于误报率）。
f = (1 − p)k )
布隆过滤器 (BF) 引入了容错机制来增强查找性能和空间效率。布隆过滤器要么返回真，要么返回假。因此，布隆过滤器的结果属于以下类别之一：真阳性、假阳性、真阴性、假阴性。布隆过滤器包含的最大数量是假阳性。假阳性和假阴性都会给系统带来开销。布隆过滤器使用数组来存储元素的信息。假阳性的定义如下：如果布隆过滤器在持有元素时返回真。类似地，假阴性的定义如下：布隆过滤器在持有元素时返回假。因此，布隆过滤器属于概率数据结构。
布隆过滤器大小和散列函数数量
我们知道，如果布隆过滤器的大小太小，很快所有位字段都会变成“1”，然后我们的布隆过滤器将对每个输入值返回“假阳性”。因此，布隆过滤器的大小是一个非常重要或需要做出的重要决策。较大的过滤器包含较少的假阳性，较小的过滤器则包含较多的假阳性。
因此，我们可以得出结论，布隆过滤器的大小完全基于“假阳性错误率”。
另一个重要的参数是确定我们将使用的散列函数的数量。我们实现的散列函数越多，布隆过滤器的速度就越慢，并且填充速度越快。但是，如果我们使用的散列函数太少，则可能会因许多假阳性而受到影响。
我们可以根据过滤器的尺寸 m、散列函数的数量 k 和插入的元素数量 n，使用以下公式计算假阳性错误率 p
p≈(1-e(-kn/m))k
我们实际上主要需要确定我们的 m 和 k 将是多少。因此，如果我们自己设置或固定错误容限值 p 和元素数量 n，我们可以使用以下公式来计算这些参数
m=(-n ln p)/(ln 2)2
k=(m/n)*(ln 2)
更新于： 2020年1月3日
261 次查看
广告