要判断一个元素是不是在一个集合里，比较容易想到的方法是用数组，链表这样的数据结构把元素保存起来，然后依次比较来确定。

但是随着集合的变大，上面的这种方法就面临几个问题，首先比较的速度随着数据量的增加而变慢，其次存储集合的空间也越来越大。

为了解决上面的问题，就引入了布隆过滤器（Bloom Filter）

布隆过滤器原理

布隆过滤器的原理就是当一个元素被加入到集合的时候，用K个Hash函数将元素映射到一个位图中的K个点，并且把这个点的值设置为1，在每次检索的时候我们看一下这个点是不是都是1就知道集合中有没有这个元素了。

这样说可能比较抽象，举个例子：

我们假设K是2，有Hash1和Hash2两个哈希函数

Hash1 = n%3
Hash2 = n%8

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

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

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

n = 7

分别用Hash1和Hash2计算n哈希后的值

Hash1  ->  1
Hash2  ->  7

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

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

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

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

n = 13
Hash1  ->  1
Hash2  ->  5

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

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是不是恶意链接等等。 以太坊大量的用到了布隆过滤器，用来定位查找日志等。

本文作者清源，欢迎关注清源的博客，不定期分享一些区块链底层技术文章。