Bloom Filter概念和原理.docx
需积分: 0 123 浏览量
2012-07-26
11:06:33
上传
评论
收藏 72KB DOCX 举报
Bloom Filter 概念和原理
焦萌 2007 年 1 月 27 日
Bloom Filter 是一种空间效率很高的随机数据结构，它利用位数组很简洁地
表示一个集合，并能判断一个元素是否属于这个集合。Bloom Filter 的这种高效
是有一定代价的：在判断一个元素是否属于某个集合时，有可能会把不属于这
个集合的元素误认为属于这个集合（false positive）。因此，Bloom Filter 不适
合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下，Bloom Filter
通过极少的错误换取了存储空间的极大节省。
集合表示和元素查询
下面我们具体来看 Bloom Filter 是如何用位数组表示集合的。初始状态时，
Bloom Filter 是一个包含 m 位的位数组，每一位都置为 0。
为了表达 S={x
1
, x
2
,…,x
n
}这样一个 n 个元素的集合，Bloom Filter 使用 k 个相互
独立的哈希函数（Hash Function），它们分别将集合中的每个元素映射到{1,
…,m}的范围中。对任意一个元素 x，第 i 个哈希函数映射的位置 h
i
(x)就会被置
为 1（1≤i≤k）。注意，如果一个位置多次被置为 1，那么只有第一次会起作用，
后面几次将没有任何效果。在下图中，k=3，且有两个哈希函数选中同一个位置
（从左边数第五位）。
资源评论
