Bloom Filter算法实现

Bloom Filter

Bloom Filter是由Bloom在1970年提出的一种快速查找算法，通过多个hash算法来共同判断一个元素（字符串）是否在这个集合内，空间利用效率很高。Bloomfilter中保存了一个n位的bit数组， 当一个元素被加到这个集合时，这个元素的key通过k个hash算法生成k个值，然后将内存数组对应的k个位置置1。判断一个元素是否在集合中，只需要查看Bloomfilter的内存数组k个位置是否全为1。当其中一个不是1时，此元素不在集合中。bloomfilter判断一个元素属于当前集合时，存在一定的误差率e。

误差率e

bloom filter-math详细的推倒了误差率e和集合元素n，bit数组m以及hash算法个数之间的关系。总结如下：

e = (1 - ((1 - 1/ m) ^ kn))^k ~= (1 - e^(-kn/m))^k
k = (m / n) * ln2 //k最优解公式
m>=nlg(1/E)*lge // 当误差率e<E时，m和n的关系
...
e < 0.1: k = 3.321928, m/n = 4.79
e < 0.01: k = 6.643856, m/n = 9.58
e < 0.001: k = 9.965784, m/n = 14.37

实现

Bloom Filter基于简单的加法Hash算法实现了一个Bloom Filter。通过给定误差率e和集合amount生成最优的Bloom filter。