bloom filter

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

设集合S={x1,x2,x3,....xn} 有n个元素， bloom filter使用一个 m 位的数组BF 来表示集合S。初始化时，BF所有位都为0， bloom filter 使用 k 个相互独立的hash函数h1，h2，h3，...,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，解得