Bloom Filter是一种空间效率很高的随机数据结构,它利用位数组很简洁地表示一个集合,并能判断一个元素是否属于这个集合。
其结构很简单,就是一个包含m位的位数组,初始值全部为0,示意如下:
为了表达$S=\{x_1, x_2,…,x_n\}$这样一个n个元素的集合,Bloom Filter使用k个相互独立的哈希函数(Hash Function),它们分别将集合中的每个元素映射到$\{1,…,m\}$的范围中。对任意一个元素x,第i个哈希函数映射的位置$h_i(x)$就会被置为1(1≤i≤k)
<aside> 💡 简单点说,对于任意一个元素x,对其使用k个hash函数,得到hash值h1,h2..hk,将布隆过滤器中h1~hk对应的位置置为1
</aside>
上图,yyj的hash值为16和26,只需要将数组的16和26位设置为1。
判断一个元素是否存在,同样计算k次hash值,判断对应位置是否全部为1即可
如果判断一个元素不存在,则一定不存在;如果判断存在,实际上不一定存在。
<aside> 💡 能提供“一定不存在”,但只能提供“可能存在”
</aside>
因为,例如字符串s1的hash值是5、16,字符串s2的hash值是16和26,字符串s3的hash值是5和26;当s1和s2存在于布隆过滤器中时,s3即使不存在,也会被误认为存在。
具体的数学计算过程可以参考wiki百科的介绍中的过程,m代表bit数组的大小,k代表hash函数的个数,n代表bloom filter中元素的数量,最终假阳性率约为:
$$ p=(1-e^{-kn/m})^k $$
最佳hash函数的个数为
$$ k=-\log_2p=\frac{m}{n}\ln2 $$
此时,可以得到最低的false positive为$p=(1-e^{-\ln2})^{m\ln2\over n}$