Jamzy Wang

life is a struggle,be willing to do,be happy to bear~~~

Bloom Filter详解

2014-07-22 18:09

原创声明:本作品采用知识共享署名-非商业性使用 3.0 版本许可协议进行许可,欢迎转载,演绎,但是必须保留本文的署名(包含链接),且不得用于商业目的。

布隆过滤器(Bloom Filter)是1970年由布隆提出的, “a space-efficient probabilistic data structure”。它实际上是一个很长的二进制矢量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难。

如果想判断一个元素是不是在一个集合里,一般想到的是将集合中所有元素保存起来,然后通过比较确定。链表、树、散列表(又叫哈希表,Hash table)等等数据结构都是这种思路。但是随着集合中元素的增加,我们需要的存储空间越来越大。同时检索速度也越来越慢,上述三种结构的检索时间复杂度分别为O(n),O(log n),O(n/k)。

布隆过滤器的原理是,当一个元素被加入集合时,通过K个散列函数将这个元素映射成一个位数组中的K个点,把它们置为1。

此处输入图片的描述(图源)

检索时,我们只要看看这些点是不是都是1就(大约)知道集合中有没有它了:如果这些点有任何一个0,则被检元素一定不在;如果都是1,则被检元素很可能在。这就是布隆过滤器的基本思想。

此处输入图片的描述(图源)

构建布隆过滤器伪代码如下:

1
2
3
4
5
6
7
8
Procedure BloomFilter(set A, hash_functions, integer m)
    filter = allocate m bits initialized to 0
    foreach ai  in A:
		foreach hash function hj:
            filter[hj(ai)] = 1
  	end foreach
    end foreach
    return filter

测试某个元素是否在布隆过滤器中伪代码如下:

1
2
3
4
5
6
Procedure MembershipTest (elm, filter, hash_functions)
    foreach hash function hj:
        if filter[hj(elm)] != 1
            return No
    end foreach
    return Yes

那么布隆过滤器的错误率有多高呢?

假设 Hash 函数以等概率条件选择并设置位数组中的某一位,m 是该位数组的大小,k 是 Hash 函数的个数,那么位数组中某一特定的位在进行元素插入时的 Hash 操作中没有被置位的概率是此处输入图片的描述

那么在所有 k 次 Hash 操作后该位都没有被置 “1” 的概率是此处输入图片的描述

如果我们插入了 n 个元素,那么某一位仍然为 “0” 的概率是此处输入图片的描述

因而该位为 “1”的概率是此处输入图片的描述

现在检测某一元素是否在该集合中。这表明某个元素是否在集合中所需的 k 个位置都按照如上的方法设置为 “1”,但是该方法可能会使算法错误的认为某一原本不在集合中的元素却被检测为在该集合中(False Positives),该概率由以下公式确定此处输入图片的描述

其实上述结果是在假定由每个 Hash 计算出需要设置的位(bit)的位置是相互独立为前提计算出来的,不难看出,随着 m (位数组大小)的增加,假正例(False Positives)的概率会下降,同时随着插入元素个数 n 的增加,False Positives的概率又会上升,对于给定的m,n,如何选择Hash函数个数 k 由以下公式确定:

此处输入图片的描述

此时False Positives的概率为此处输入图片的描述

而对于给定的False Positives概率 p,如何选择最优的位数组大小 m 呢,

此处输入图片的描述

上式表明,位数组的大小最好与插入元素的个数成线性关系,对于给定的 m,n,k,假正例概率最大为:

此处输入图片的描述

下图是布隆过滤器假正例概率 p 与位数组大小 m 和集合中插入元素个数 n 的关系图,假定 Hash 函数个数选取最优数目此处输入图片的描述

此处输入图片的描述(图源)

在实际生产中一般是先确定误检率的大小,然后通过公式此处输入图片的描述确定m/n的值,再根据公式此处输入图片的描述确定k的大小。n的值一般是预先得到的(或许预先估计得)集合中元素的个数,比如要判断某个字符串是否在某个字符串的集合中,这个集合的大小是100万,那么n的大小就是100万,根据m/n和n的值就可以确定位数组的大小m。

假设集合大小是30万:

1
2
若要求误差率控制在0.003,那么m/n=15,m=15*300000,k=4;
若要求误差率控制在0.005,那么m/n=16,m=16*300000,k=3

m=15*300000=4500000,也就是说位数组的大小为4500000bit,约0.5625兆,可见空间极其省。

m,n,k和误检率之间的关系如下所示(数据来源 ):

此处输入图片的描述 此处输入图片的描述 此处输入图片的描述

接下来需要考虑的问题是选择哪些哈希函数呢?已有的生产环境中使用的哈希函数主要如下:

  • Cassandra uses Murmur hashes
  • Hadoop includes default implementations of Jenkins and Murmur hashes
  • python-bloomfilter uses cryptographic hashes
  • Plan9 uses a simple hash as proposed in Mitzenmacher 2005
  • Sdroege Bloom filter uses fnv1a (included just because I wanted to show one that uses fnv.)
  • Squid uses MD5(可以使用不同的种子)

下面再来总结一下布隆过滤器的优缺点:

  • 优点

相比于其它的数据结构,布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数(O(k))。另外, 散列函数相互之间没有关系,方便由硬件并行实现。布隆过滤器不需要存储元素本身,在某些对保密要求非常严格的场合有优势。布隆过滤器可以表示全集,其它任何数据结构都不能;k和m相同,使用同一组散列函数的两个布隆过滤器的交并差运算可以使用位操作进行。

  • 缺点

但是布隆过滤器的缺点和优点一样明显。误算率是其中之一。随着存入的元素数量增加,误算率随之增加。但是如果元素数量太少,则使用散列表足矣。另外,一般情况下不能从布隆过滤器中删除元素。我们很容易想到把位数组变成整数数组,每插入一个元素相应的计数器加1,这样删除元素时将计数器减掉就可以了。然而要保证安全地删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面。这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。在降低误算率方面,有不少工作,使得出现了很多布隆过滤器的变种。

Ref

Comments