要判断一个元素是不是在一个集合里,比较容易想到的方法是用数组,链表这样的数据结构把元素保存起来,然后依次比较来确定。
  但是随着集合的变大,上面的这种方法就面临几个问题,首先比较的速度随着数据量的增加而变慢,其次存储集合的空间也越来越大。
  为了解决上面的问题,就引入了布隆过滤器(Bloom Filter)

布隆过滤器原理

  布隆过滤器的原理就是当一个元素被加入到集合的时候,用KHash函数将元素映射到一个位图中的K个点,并且把这个点的值设置为1,在每次检索的时候我们看一下这个点是不是都是1就知道集合中有没有这个元素了。
  这样说可能比较抽象,举个例子:

  我们假设K2,有Hash1Hash2两个哈希函数

1
2
Hash1 = n%3
Hash2 = n%8

  然后我们创建一个名叫bitMap长度是20位图

1
bitMap=[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

  这个时候,我们要将7,存入到这个集合中

1
n = 7

  分别用Hash1Hash2计算n哈希后的值

1
2
Hash1  ->  1
Hash2 -> 7

  我们把bitMap对应的值置为1,从0开始

1
bitMap=[0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

  这样下次我们来查找7在不在这个集合的时候就可以用Hash1Hash2计算完以后在bitMap集合中查找对应位置是否都是1,如果都是1则一定在集合中。

  如果再在集合中插入13
  分别用Hash1Hash2计算n哈希后的值

1
2
3
n = 13
Hash1 -> 1
Hash2 -> 5

  我们把bitMap对应的值置为1,从0开始

1
bitMap=[0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

  这个时候我们发现1被映射到了两次,但是并不影响我们在集合[7, 13]中快速找到7或者13。

  但是当插入的数据量大幅提升的时候,甚至bitMap全部被置为1的时候问题就很严重了,误识率就非常高了,这个也是根据不同场景实现布隆过滤器所要考虑的问题。

  尽管有这样的问题,但是仍然不能掩盖布隆过滤器的空间利用率查询时间远超其他算法,插入数据和查询数据的时间复杂度都是O(k)

应用场景

  比较典型的应用场景就是检查垃圾邮箱的地址,比如我建立了一个垃圾邮件的布隆过滤器,当新邮件到来的时候我要快速的判断这封邮件是不是垃圾邮件。
  还可以用来判断一个URL是不是恶意链接等等。
  以太坊大量的用到了布隆过滤器,用来定位查找日志等。