Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1023334
  • 博文数量: 242
  • 博客积分: 10209
  • 博客等级: 上将
  • 技术积分: 3028
  • 用 户 组: 普通用户
  • 注册时间: 2008-03-12 09:27
文章分类

全部博文(242)

文章存档

2014年(1)

2013年(1)

2010年(51)

2009年(65)

2008年(124)

我的朋友

分类: C/C++

2010-06-11 15:29:36

看了bloom filter的相关内容,写上来分享一下,也方便自己回顾。

设集合S={x1,x2,x3,....xn} n个元素, bloom filter使用一个 m 位的数组BF 来表示集合S。初始化时,BF所有位都为0 bloom filter 使用 k 个相互独立的hash函数h1h2h3...,hk, 每个hash函数的值域范围都是{1,2,3,...,m}。 在添加一个元素x时, 分别计算h1(x)h2(x).....hk(x)的值,并将BF数组中以这些值为下标对应位 置为1 。 检查一个元素y是否存在时,同样计算h1(y)h2(y)......hk(y)的值,然后检测以这些值为下标的BF数组中对应的位 是否为1,若有一个不为1,就表明y不存在于原集合中,若对应位都为1,说明y可能存在于原集合中。 注意这里所说的可能存在,是因为有一个false positive(假阳性)的概率。假阳性是说,本来 y 是不存在于bloom fiter中的,但是k个hash函数以y为输入产生的输出 在BF数组中
所对应的位都是1 。


在实际工作中,位向量长度的选择 和 hansh函数个数的选择 取决于 我们要在bloom filter中加入多少keys以及我们允许的假阳性概率。


下面我们就用数学的方法分析一下:

假设bloom filter 数组BF长度为m ,要插入的元素有n个, 有k个hash函数,

 当所有元素都插入到bloom filter后,BF 数组 某一位仍为 0 的概率:


(根据高数极限公式


成员查询时假阳性的概率:


对f两端取对数,

g对k求导得:

为求出f的最小值,令上式等于0,解得






阅读(826) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~