Question

BloomFilter（布隆过滤器）是由Bloom在1970年提出的一种多哈希函数映射的快速查找算法。BloomFilter是一种空间效率很高的随机数据结构，它利用位数组很简洁地表示一个集合，并能判断一个元素是否属于这个集合。BloomFilter的这种高效是有一定代价的：在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合（false positive）。因此，BloomFilter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下，BloomFilter通过极少的错误换取了存储空间的极大节省。

15.2.1　BloomFilter原理

上一节内存去重方案中的第三种实现方式Bit-Map方法，已经非常接近BloomFilter算法的思想，可是由于使用单一哈希函数，导致误判率很高，为了降低冲突，BloomFilter使用了多个哈希函数。下面讲解一下BloomFilter的实现原理：创建一个m位的位数组，先将所有位初始化为0。然后选择k个不同的哈希函数。第i个哈希函数对字符串str哈希的结果记为h（i，str），且h（i，str）的范围是0到m-1。如图15-1所示，将一个字符串经过k个哈希函数映射到m位数组中。

图15-1　哈希映射

从图中我们可以看到，字符串经过哈希函数映射成介于0到m-1之间的数字，并将m位位数组中下标等于这个数字的那一位置为1，这样就将字符串映射到位数组中的k个二进制位了。

如何判断字符串是否存在过呢？只需要将新的字符串也经过h（1，str），h（2，str），h（3，str），...，h（k，str）哈希映射，检查每一个映射所对应m位位数组的值是否为1。若其中任何一位不为1则可以判定str一定没有被记录过。但是若一个字符串对应的任何一位全为1，实际上是不能100%的肯定该字符串被BloomFilter记录过，这就是所说的低错误率。

以上即BloomFilter的原理，那如何选择BloomFilter参数呢？

首先哈希函数的选择对性能的影响应该是很大的，一个好的哈希函数要能近似等概率地将字符串映射到各个位。选择k个不同的哈希函数比较麻烦，一种常用的方法是选择一个哈希函数，然后送入k个不同的参数。

接下来我们要选取k、m、n的取值。哈希函数个数k、位数组大小m、加入的字符串数量n的关系，如表15-1所示。

表15-1　m、n、k关系表

表15-1所示的是m、n、k不同的取值所对应的漏失概率，即不存在的字符串有一定概率被误判为已经存在。m表示多少个位，也就是使用内存的大小，n表示去重字符串的数量，k表示哈希函数的个数。例如申请了256M内存，即1<<31，因此m=2^31，约21.5亿。将k设置为7，并查询表中k=7的那一列。当漏失率为8.56e-05时，m/n值为23。所以n=21.5/23=0.93（亿），表示漏失概率为8.56e-05时，256M内存可满足0.93亿条字符串的去重。如果大家想对m、n、k之间的关系有更深入的了解，推荐一篇非常有名的文献：http://pages.cs.wisc.edu/~cao/papers/summary-cache/node8.htm l。

15.2.2　Python实现BloomFilter

了解清楚原理之后，下面开始用Python来实现BloomFilter算法。在GitHub中有一个开源项目python-bloomfilter，这个项目不仅仅实现了BloomFilter，还实现了一个大小可动态扩展的ScalableBloomFilter。

1.安装python-bloomfilter

从https://github.com/qiyeboy/python-bloomfilter 中下载源码，进入源码目录，使用Python setup.py install即可完成安装。

2.示例

使用BloomFilter创建一个容量为1000，漏失率为0.001的布隆过滤器

  from pybloom import BloomFilter
  f = BloomFilter(capacity=1000, error_rate=0.001)
  print  [f.add(x) for x in range(10)]
  print 11 in f
  print 4 in f

输出结果为：

  [False, False, False, False, False, False, False, False, False, False]
  False
  True

如果你不想静态指定容量，可以使用python-bloomfilter中可动态扩展的ScalableBloomFilter。示例如下：

  from pybloom import ScalableBloomFilter
  sbf = ScalableBloomFilter(mode=ScalableBloomFilter.SMALL_SET_GROWTH)
  count = 10000
  for i in xrange(0, count):
     sbf.add(i)
  print 10001 in sbf
  print 4 in sbf

输出结果为：

  False
  True