Bloom Filter
Bloom Filter是由Bloom在1970年提出的一種快速查找算法，通過多個hash算法來共同判斷一個元素（字符串）是否在這個集合內(nèi)砚蓬，空間利用效率很高鸟廓。Bloomfilter中保存了一個n位的bit數(shù)組窗轩， 當(dāng)一個元素被加到這個集合時炮沐，這個元素的key通過k個hash算法生成k個值难咕，然后將內(nèi)存數(shù)組對應(yīng)的k個位置置1泛烙。判斷一個元素是否在集合中理卑，只需要查看Bloomfilter的內(nèi)存數(shù)組k個位置是否全為1。當(dāng)其中一個不是1時蔽氨，此元素不在集合中藐唠。bloomfilter判斷一個元素屬于當(dāng)前集合時，存在一定的誤差率e鹉究。
誤差率e
bloom filter-math詳細(xì)的推倒了誤差率e和集合元素n宇立，bit數(shù)組m以及hash算法個數(shù)之間的關(guān)系∽耘猓總結(jié)如下：
e = (1 - ((1 - 1/ m) ^ kn))^k ~= (1 - e^(-kn/m))^k
k = (m / n) * ln2 //k最優(yōu)解公式
m>=nlg(1/E)*lge // 當(dāng)誤差率e<E時妈嘹，m和n的關(guā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
實現(xiàn)
Bloom Filter基于簡單的加法Hash算法實現(xiàn)了一個Bloom Filter。通過給定誤差率e和集合amount生成最優(yōu)的Bloom filter绍妨。
