布隆过滤器

布隆过滤器是偶然听到的一个东西，名字有点吸引我。于是去作了一番了解。

布隆过滤器与散列表、链表性质一样，是一种数据结构。它的应用优点在于节省空间同时提高查找效率。

这里明确一点是布隆过滤器本身是不存值的，所以用它来判断一个值是否存在列表中是一个非常合适的场景。与此同时，它不能判断值一定存在列表中，因为它会出现误判。下面会细说。

布隆过滤器的本质是一张位图(BitMap)，如下

位图

当我们用关键字存值时，需要借用一个工具——哈希函数，哈希函数在散列表上也有应用，这里不谈了。

通过哈希函数，我们可以对一个关键字(Key)，算出一个哈希值，这里的哈希值假设算出上图的下标（1），那么存值的时候我们的布隆过滤器是这样表示的：

存值后的位图

这样意味着1这个位置存了值，如果我们需要检验关键字（Key）是否存在，那么再次通过散列函数算出来下标，如果位图这个位置标记为1，那么说明这个Key是存在的。原理就是如此简单。

实际上，布隆过滤器往往会采用多个散列函数来生成多个下标，例如3个散列函数生成3个下标（1,5,6），那么表达起来就会是这样：

3个散列下标的位图

为什么需要多个散列函数？

其实是为了提高它准确率，因为散列函数很可能对于不同的Key可能会产生相同的散列值，所以设置多个散列函数能让Key留存率高一点，比较后面也许会有其它值把它冲掉，比如另外一个KeyOther，计算出的散列值(2,5,7)。那么存了KeyOther的时候，位图就变为这样了：

存了KeyOther的位图

可以看出5下标被覆盖掉了，这时如果你要判断Key存不存在怎么办？你算出了(1,5,6)，那么如果通过查看（1，5，6）的位置都为1的时候，是不是意味着Key是有可能存在了。注意，这里是有可能存在，也是布隆过滤器为什么会出现误算的原因。

我总结了两点：

1.布隆过滤器不能算出值的必然存在

2.布隆过滤器能算出值的必定不存在

最后思考

位图的长度会影响布隆过滤器的长度

哈希函数的个数会影响布隆过滤器的误报率以及效率

其中的函数关系，靠自我脑补了。

额外知识

支持删除的布隆过滤器：Couting Bloom Filter

哈希算法：FNV

以上均为个人见解，不做任何参考。

参考资料：维基百科