Bloom Filter是由Bloom在1970年提出的一种多哈希函数映射的快速查找算法。

通常应用在一些需要快速判断某个元素是否属于集合，但是并不严格要求100%正确的场合。

基于一种概率数据结构来实现，是一个有趣且强大的算法

一 . 实例

为了说明Bloom Filter存在的重要意义，举一个实例，也是为什么我要学习Boomfilter的起因：

假设我们要写一个爬虫程序。由于网络间的链接错综复杂，蜘蛛在网络间爬行很可能会形成“环”，爬虫就会进入一个无限怪圈，找不到出路，程序出现崩溃。

所以为了避免形成“环”，就需要知道蜘蛛已经访问过那些URL，也就是如何判重。

给一个URL，怎样知道蜘蛛是否已经访问过呢？按照我们的常识，就会有如下几种方案：

  1. 将访问过的URL保存到数据库，数据库管理系统可以为你去重。

  2. 用Set将访问过的URL保存起来。那只需接近O(1)的代价就可以查到一个URL是否被访问过了。

  3. URL经过MD5或SHA-1等单向哈希后再保存到Set或数据库。

  4. Bit-Map方法。建立一个BitSet，将每个URL经过一个哈希函数映射到某一位。

方法1~3都是将访问过的URL完整保存，方法4则只标记URL的一个映射位。

以上方法在数据量较小的情况下都能完美解决问题，但是当数据量变得非常庞大时问题就来了。

方法1的缺点：数据量变得非常庞大后关系型数据库查询的效率会变得很低。而且每来一个URL就启动一次数据库查询是不是太小题大做了？

方法2的缺点：太消耗内存。随着URL的增多，占用的内存会越来越多。就算只有1亿个URL，每个URL只算50个字符，至少需要5GB内存，还不包括Set数据结构中的内存浪费。

方法3的缺点：由于字符串经过MD5处理后的信息摘要长度只有128Bit，SHA-1处理后也只有160Bit，因此方法3比方法2节省了好几倍的内存。

方法4的缺点：消耗内存是相对较少的，但缺点是单一哈希函数发生冲突的概率太高。

若要降低冲突发生的概率到1%，有种办法就是就要将BitSet的长度设置为URL个数的100倍。

假设一亿条URL，就得把BitSet长度设为100亿，过于稀疏也是很费内存的

实质上上面的算法都忽略了一个重要的隐含条件：允许小概率的出错，不一定要100%准确！

也就是说少量url实际上没有没网络爬虫访问，而将它们错判为已访问的代价是很小的——大不了少抓几个网页呗。

二 . Bloom Filter 算法原理

废话说到这里，下面引入本篇的主角——Bloom Filter。其实上面方法4的思想已经很接近Bloom Filter了。

方法四的致命缺点是冲突概率高，为了降低冲突的概念，Bloom Filter使用了多个哈希函数，而不是一个。

为什么可以降低呢？我们知道Hash函数有一定几率出现冲突，概率假设为 p1，我们知道p1是一个很小的几率，但是在数据量大之后冲突就会变多，也就是上面第四种方法的问题。

BoomFilter使用 多个Hash函数 分别冲突概率为 p2 p3 p4 p5 … pn ，我们知道不同 Hash函数处理同一个字符串彼此独立，所以冲突概率通过乘法公式得到为: p1p2p3p4p5p6…pn，是相当相当小的了。

Bloom Filter算法如下：

预操作

创建一个m位BitSet（C++自带，Python为bitarray），先将所有位初始化为0，然后选择k个不同的哈希函数。第i个哈希函数对字符串str哈希的结果记为h（i，str），且h（i，str）的范围是0到m-1 。

Add操作

下面是每个字符串处理的过程，首先是将字符串str“记录”到BitSet中的过程：

对于字符串str，分别计算h（1，str），h（2，str）…… h（k，str）。然后将BitSet的第h（1，str）、h（2，str）…… h（k，str）位设为1。

很简单吧？这样就将字符串str映射到BitSet中的k个二进制位了。

CHeck操作

根据上图，我们对每个字符串采用同样的算法。

下面是检查字符串str是否被BitSet记录过的过程：

  • 对于字符串str，分别计算h（1，str），h（2，str）…… h（k，str）。然后检查BitSet的第h（1，str）、h（2，str）…… h（k，str）位是否为1，若其中任何一位不为1则可以判定str一定没有被记录过。若全部位都是1，则“认为”字符串str存在。

  • 若一个字符串对应的Bit不全为1，则可以肯定该字符串一定没有被Bloom Filter记录过。（这是显然的，因为字符串被记录过，其对应的二进制位肯定全部被设为1了）

  • 但是若一个字符串对应的Bit全为1，实际上是不能100%的肯定该字符串被Bloom Filter记录过的。（因为有可能该字符串的所有位都刚好是被其他字符串所对应）这种将该字符串划分错的情况，称为wrong position。

Delete操作

字符串加入了就被不能删除了，因为删除会影响到其他字符串。实在需要删除字符串的可以使用Counting bloomfilter(CBF)，这是一种基本Bloom Filter的变体，CBF将基本Bloom Filter每一个Bit改为一个计数器，这样就可以实现删除字符串的功能了。

Bloom Filter跟单哈希函数Bit-Map不同之处在于：Bloom Filter使用了k个哈希函数，每个字符串跟k个bit对应。从而降低了冲突的概率。

三. Bloom Filter 优化

考虑到BoomFilter上面的指标，总结一下有以下几个

m ： BitSet 位数

n ： 插入字符串个数

k ：hash函数个数

当然，哈希函数也是影响的重要因素

从表格来看 m/n越大越准，k越大越准。

但是具体怎么设计呢？

哈希函数选择

  • 哈希函数的选择对性能的影响应该是很大的，一个好的哈希函数要能近似等概率的将字符串映射到各个Bit。

  • 选择k个不同的哈希函数比较麻烦，一种简单的方法是选择一个哈希函数，然后送入k个不同的参数。

参数设计

相信大家对于 Bloom Filter 的工作原理都有了一个基本的了解，现在我们来看看在Bloom Filter 中涉及到的一些参数指标：

  • 欲插入Bloom Filter中的元素数目: n
  • Bloom Filter误判率: P(true)
  • BitArray数组的大小: m
  • Hash Function的数目: k

欲插入Bloom Filter中的元素数目 n 是我们在实际应用中可以提前获取或预估的；Bloom Filter的误判率 P(true) 则是我们提前设定的可以接受的容错率。所以在设计Bloom Filter过程中，最关键的参数就是BitArray数组的大小 m 和 Hash Function的数目 k，下面将给出这两个关键参数的设定依据、方法

误判率 P(true)

向Bloom Filter插入一个元素时，其一个Hash Function会将BitArray中的某Bit置为1，故对于任一Bit而言，其被置为1的概率 P 1 = 1 m P{1}=\frac{1}{m} P1=m1​，那么其依然是0的概率 $ P0=1−P1=1−\frac{1}{m}$；易知插入一个元素时，其 k 个Hash Function 都未将该Bit置为1的概率 P 0 1 = ( 1 − 1 m ) k P{0}^1=(1−\frac{1}m)^k P01=(1−m1​)k。则向Bloom Filter 插入全部n个元素后，该Bit依然为0的概率即为 P 0 n = ( 1 − 1 m ) k n P{0}^n=(1−\frac{1}m)^{kn} P0n=(1−m1​)kn，反之，该Bit为1的概率则为 P 1 n = 1 − P 0 n = 1 − ( 1 − 1 m ) k n P{1}^n=1−P{0}^n=1−(1−\frac{1}m)^{kn} P1n=1−P0n=1−(1−m1​)kn

由前文可知，判定一个元素存在于Bloom Filter，要求k个Hash Function的哈希值对应的Bit的值均为1。据此，我们可以计算出其误判率 P(true)：

P ( t r u e ) = ( P 1 n ) k = [ 1 − ( 1 − 1 m ) k n ] k P(true)=(P{1}^n)^k=[1−(1−\frac{1}m)^{kn}]^k P(true)=(P1n)k=[1−(1−m1​)kn]k

根据基本极限

lim ⁡ x → ∞ ( 1 − 1 x ) − x = e \lim_{x \to \infty}(1-\frac{1}x)^{−x}=e x→∞lim​(1−x1​)−x=e

可知：

P ( t r u e ) ≈ ( 1 − e − n k m ) k P(true)≈(1−e^{\frac{-nk}m})^k P(true)≈(1−em−nk​)k

从上式可以看出，当BitArray数组的大小m增大 或 欲插入Bloom Filter中的元素数目n 减小时，均可以使得误判率P(true)下降

Hash Function的数目 k

前文已经看到Hash Function数目k的增加可以减小误判率P(true)，但是随着Hash Function数目k的继续增加，反而会使误判率P(true)上升，即误判率是一个关于Hash Function数目k的凸函数。所以当k在极值点时，此时误判率即为最小值

f ( k ) = ( 1 − e − n k m ) k f(k)=(1−e^{\frac{−nk}m})^k f(k)=(1−em−nk​)k

令 a = e n m a=e^{\frac{n}m} a=emn​，则有：

f ( k ) = ( 1 − a − k ) k f(k)=(1−a^−k)^k f(k)=(1−a−k)k

分别对上式两边，先取对数，再对k求一次导，可有：

1 f ( k ) f ( k ) ′ = l n ( 1 − a − k ) + k a − k l n a 1 − a − k \frac{1}{f(k)}f(k)′=ln(1−a^−k)+\frac{ka^{−k}lna}{1−a^−k} f(k)1​f(k)′=ln(1−a−k)+1−a−kka−klna​

易知，当k取极值点时，有 f(k)′=0，故将其带入上式即可求出k

l n ( 1 − a − k ) + k a − k l n a 1 − a − k = 0 ln(1−a^−k)+\frac{ka^{−k}lna}{1−a^−k}=0 ln(1−a−k)+1−a−kka−klna​=0

⇒ ( 1 − a − k ) l n ( 1 − a − k ) = − k a − k l n a ⇒(1−a^{−k})ln(1−a^{−k})=−ka^{−k}lna ⇒(1−a−k)ln(1−a−k)=−ka−klna

⇒ ( 1 − a − k ) l n ( 1 − a − k ) = a − k l n a − k ⇒(1−a^{−k})ln(1−a^{−k})=a^{−k}lna^{−k} ⇒(1−a−k)ln(1−a−k)=a−klna−k

⇒ 1 − a − k = a − k ⇒ 1−a^{−k}=a^{−k} ⇒1−a−k=a−k

⇒ a − k = 1 2 ⇒a^{−k}=\frac{1}2 ⇒a−k=21​

⇒ e − k n m = 1 2 ⇒e^{\frac{−kn}m}=\frac{1}2 ⇒em−kn​=21​

⇒ k = m n l n 2 ≈ 0.7 m n ⇒k=\frac{m}nln2≈0.7\frac{m}n ⇒k=nm​ln2≈0.7nm​

此时，我们即可以利用上式的结果，通过m和n来确定最优的Hash Function数目k

BitArray数组的大小 m

如何确定BitArray数组的大小 m 呢？这里，我们联立 P(true)、k 的公式，即可解出 m

P ( t r u e ) = ( 1 − e − n k m ) k P(true)=(1−e^{\frac{−nk}m})^k P(true)=(1−em−nk​)k

k = m n l n 2 k=\frac{m}nln2 k=nm​ln2

联立后有：

⇒ P ( t r u e ) = ( 1 − e − l n 2 ) m n l n 2 = 1 2 m n l n 2 ≈ 0.618 5 m n ⇒ P(true)=(1−e^{−ln2})^{\frac{m}nln2}=\frac{1}{2}^{\frac{m}nln2}≈0.6185^{\frac{m}n} ⇒P(true)=(1−e−ln2)nm​ln2=21​nm​ln2≈0.6185nm​

对上式求解，可得：

⇒ l n P ( t r u e ) = m n l n 2 l n 1 2 ⇒lnP(true)=\frac{m}nln2ln\frac{1}2 ⇒lnP(true)=nm​ln2ln21​

⇒ m = − n l n P ( t r u e ) ( l n 2 ) 2 ⇒m=−\frac{nlnP(true)}{(ln2)^2} ⇒m=−(ln2)2nlnP(true)​

此时，我们即可以利用上式的结果，通过P(true)和n来确定最优的BitArray数组的大小 m

Python 代码简单实现

主体

from bitarray import bitarray # 产生BitSet

import mmh3 # 产生Hash函数
 
 
class BloomFilter(set):
 
    def __init__(self, size, hash_count):
        super(BloomFilter, self).__init__()
        self.bit_array = bitarray(size)
        self.bit_array.setall(0)
        self.size = size
        self.hash_count = hash_count
 
    def __len__(self):
        return self.size
 
    def __iter__(self):
        return iter(self.bit_array)
 
    def add(self, item):
        for seed in range(self.hash_count):
            index = mmh3.hash(item, seed) % self.size
            self.bit_array[index] = 1
 
        return self
 
    def __contains__(self, item):
        out = True
        for seed in range(self.hash_count):
            index = mmh3.hash(item, seed) % self.size
            if self.bit_array[index] == 0:
                out = False
 
        return out

测试：

def main():
    bloom = BloomFilter(10000, 20)
    animals = ['dog', 'cat', 'giraffe', 'fly', 'mosquito', 'horse', 'eagle',
               'bird', 'bison', 'boar', 'butterfly', 'ant', 'anaconda', 'bear',
               'chicken', 'dolphin', 'donkey', 'crow', 'crocodile']
    # First insertion of animals into the bloom filter
    for animal in animals:
        bloom.add(animal)
 
    # Membership existence for already inserted animals
    # There should not be any false negatives
    for animal in animals:
        if animal in bloom:
            print('{} is in bloom filter as expected'.format(animal))
        else:
            print('Something is terribly went wrong for {}'.format(animal))
            print('FALSE NEGATIVE!')
 
    # Membership existence for not inserted animals
    # There could be false positives
    other_animals = ['badger', 'cow', 'pig', 'sheep', 'bee', 'wolf', 'fox',
                     'whale', 'shark', 'fish', 'turkey', 'duck', 'dove',
                     'deer', 'elephant', 'frog', 'falcon', 'goat', 'gorilla',
                     'hawk' ]
    for other_animal in other_animals:
        if other_animal in bloom:
            print('{} is not in the bloom, but a false positive'.format(other_animal))
        else:
            print('{} is not in the bloom filter as expected'.format(other_animal))
 
 
if __name__ == '__main__':
    main()

结果：

dog is in bloom filter as expected
cat is in bloom filter as expected
giraffe is in bloom filter as expected
fly is in bloom filter as expected
mosquito is in bloom filter as expected
horse is in bloom filter as expected
eagle is in bloom filter as expected
bird is in bloom filter as expected
bison is in bloom filter as expected
boar is in bloom filter as expected
butterfly is in bloom filter as expected
ant is in bloom filter as expected
anaconda is in bloom filter as expected
bear is in bloom filter as expected
chicken is in bloom filter as expected
dolphin is in bloom filter as expected
donkey is in bloom filter as expected
crow is in bloom filter as expected
crocodile is in bloom filter as expected
badger is not in the bloom filter as expected
cow is not in the bloom filter as expected
pig is not in the bloom filter as expected
sheep is not in the bloom filter as expected
bee is not in the bloom filter as expected
wolf is not in the bloom filter as expected
fox is not in the bloom filter as expected
whale is not in the bloom filter as expected
shark is not in the bloom filter as expected
fish is not in the bloom filter as expected
turkey is not in the bloom filter as expected
duck is not in the bloom filter as expected
dove is not in the bloom filter as expected
deer is not in the bloom filter as expected
elephant is not in the bloom filter as expected
frog is not in the bloom filter as expected
falcon is not in the bloom filter as expected
goat is not in the bloom filter as expected
gorilla is not in the bloom filter as expected
hawk is not in the bloom filter as expected

可以看到 没有任何误判

之后我会尝试用C来实现一个BoomFilter，python在GitHub上有造好的轮子了，我就不重复写了，这位大哥写的很好了～附上链接

链接 https://github.com/jaybaird/python-bloomfilter

希望你有所收获。