bloom filter

bloom filter 对于查询某个元素key是否存在于某个元素集合s中很有用，当不要求零错误率时bloom filter在海量数据查询中性能很好。

bloom filter 由3各部分组成：元素集合key，k个hash函数，一个长度为m的位数组。位数组中的元素值为0或者1.bloom filter只支持插入和查询操作，不支持删除操纵。

插入：

每个hash函数都对要插入的key进行hash计算，将计算结果对应的位数组位置为1.例如：

key=foo；

hash1(foo)=3;

hash2(foo)=8;

hash3(foo)=13.

再把位数组的第3,8,13位置为1，如果原来是就是1则保持1，如果原来是0则改为1.

查询：

对要查询的key进行hash计算，再看位数组对应的位是否为1，如果全部为1则key可能在集合中，如果有1个或者多个数组位为0，则key不在集合中。

key=foo1;

hash1(foo1)=2;

hash2(foo1)=6;

hash(foo1)=9.

然后查看位数组的第2,6,9,位是否为1，如果全部为1，则foo1可能在集合中。