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}$