判断某个元素是否已经存在于一个大的集合（亿级）中，并容许少量的误报的情况下使用。
初始化 m 位的位数组，被 0 填充。定义 k 个不同的 hash 函数，每个 hash 函数将一个输入元素映射到位数组的一个位上，一个确定的输入则有 k 个索引。
将 k 个索引对应的位置全部置 1
算出输入元素的 k 个索引，查询这 k 个对应位置的状态，如果都为 1，则认为元素在 set 中。
事实上，如果 k 个对应的索引位都为 1，有可能该元素并不在集合中，也就是 false positive. 不会出现 fase nagitave 的情况，也就是只要有一位 为 0，则该元素一定不存在。
加入的元素很难删除，不知道会不会影响到其它元素。可以把位数组改为整数数组，加入元素时对应位的整数加 1，删除元素时将其减 1 （Counting Bloom Filter）. 单是单凭此过滤器无法确认要删除的元素是否真的在集合中。
假阳性，比如检测乙肝时结果呈阳性，但实际上是阴性，也就是误报。
假阴性，如果一个人是乙肝患者，检查结果却是阴性，就是假阴性，也就是漏报。
此算法如果所有 hash 的结果对应的索引位均为 0 则此元素一定不在集合中，所以这个算法不会出现 false negative （漏报）的情况。
那么出现误报，也就是元素不在集合中，却得出了相反的结论的概率是多少。
假设 hash 函数的结果落在每一个 m 的位上的概率是相等的，对应一个输入，某索引位没有命中的概率是
$1-\frac{1}{m}$
假设有 k 个 hash 函数，都没有命中的概率是
$(1-\frac{1}{m})^k$
如果有 n 个元素，那么某一位一直都没有命中的概率就是
$(1-\frac{1}{m})^{kn}$
这一位命中的概率则是
$1-(1-\frac{1}{m})^{kn}$
如果对一个特定的元素存在误报，那么这个元素的经过 hash 函数所得到的k个索引全部都是1，概率也就是
$\left(1-\left[1-\frac{1}{m}\right]^{kn}\right)^k \approx \left( 1-e^{-kn/m} \right)^k$
这个算法假设了每一索引位的概率是独立的，所以结果并不完全准确但是可以作为近似值。从这个结果可以看出来，增加 m 的值将会降低误报率，增加 n 的值则会增加误报。
好的 hash 函数应该以尽可能相待的概率将输入映射到每个位上
$k = \frac{m}{n} \ln 2$
也就是
$2^{-k} \approx {0.6185}^{m/n}$
如果有 m 位数组，n 个元素，FP 的概率为 p，k 使用的是上述计算出的最佳值
$p = \left( 1-e^{-(m/n\ln 2) n/m} \right)^{(m/n\ln 2)}$
可以简化成
$\ln p = -\frac{m}{n} \left(\ln 2\right)^2$
结果是
$m=-\frac{n\ln p}{(\ln 2)^2}$
对于一个给定的 FP 概率 p, 数组 m 的长度和元素个数 n 应该成正比。上述公式在 m, n 趋于无穷时也同样适用，FP 的概率在 m, n, k 都接近无穷时
$\left( 1-e^{-k(n+0.5)/(m-1)} \right)^k$