bloom filter有可能把不属于这个集合的元素误认为属于这个集合（false positive），因此它不适合零错误的应用场合。而在能容忍低错误率的场合下，bloom filter通过极少的错误换取了存储空间的极大节省。
bloom filter 使用位数组表示集合。初始状态时，bloom filter是一个包含m位的位数组，每一个位置都为0.
initial state
为了表达S={x1,x2,...,xn} 这样一个n个元素的集合，bloom filter使用k个相互独立的hash function，他们分别将集合中的每个元素映射到{1,...,m}的范围中。对任意一个元素x，第i个哈希函数映射的位置hi(x)就被置为1（1<=i<=k）.注意，如果一个位置多次被置为1，那么只有一次会起作用，后面几次将没有任何效果。在下图中，k=3，且有两个哈希函数选中同一个位置（从左边数第五位）.
image.png
在判断y是否属于这个集合时，我们对y应用k次哈希函数，如果所有hi(y)的位置都是1（1<=i<=k）,那么我们就认为y是集合中的元素，否则认为y不是集合中的元素。下图中y1就不是集合中的元素。y2有可能属于这个集合，或者刚好是一个false positive。
example
image.png
image.png
image.png
image.png
image.png
image.png
网友评论