李卓宇，夏必胜，马乐荣

(延安大学 数学与计算机科学学院，陕西 延安 716000)

1 布隆过滤器算法

1.1 背景和原理

布隆过滤器(Bloom Filter)是在1970年由布隆(Burton Howard Bloom)提出，是一种紧凑型的、比较巧妙的概率型数据结构，它由一个很长的二进制向量(位向量)和一系列随机均匀分布的散列(哈希)函数组成[1]。用多个散列函数，将一个数据映射到位数组结构中，可以用来高效地插入元素和检索判断“某个元素一定不存在或者可能存在于某个集合当中”。此种方式不仅可以提升查询效率，也可以节省大量的内存空间[2]。

当一个元素被加入元素集合时，通过k个散列函数将这个元素映射成一个位数组中的k个点(特征)，把它们置为1，检索时这些点如果是1，则被检元素可能存在，如果这些点当中有任何一个0，则被检元素一定不在。

基本思路：①设数据集A={a1,a2,…,an}含n个元素，作为待操作的集合；②Bloom Filter用一个长度为m的位向量V={b1,b2,…,bm}表示集合中的元素，位向量的初始值全为0；③获得k个具有均匀分布特性的散列函数；④对于集合中的每一个元素，首先经过k个散列函数产生k个随机数h1,h2,…,hk，使向量V的相应位置{b1,b2,…,bm}均置为1。集合中其他元素也通过该操作将向量V的若干位置为1；⑤对于待查找的元素，首先将该元素经过前四步操作获得k个随机数h1,h2,…,hk，然后检查向量V的相应位置{b1,b2,…,bm}上的值，若全为1，则该元素可能存在于集合中，若至少有一个0存在，则元素不在该集合中，为新元素。步骤过程如图1、图2、图3所示。

图1 位数组m的初始状态

图2 集合A中元素的位置状态