布隆过滤器五分钟入门

缘起

之前在公司的一场技术分享上,有位大牛讲到了布隆过滤器。虽然之前有所了解,但只是停留在代码实现上,还没有去深入探究它存在的合理性和应用场景上。所以借着这个机会重新捋捋脉络,便有了这篇文章。

原理

维基百科上的描述如下:

A Bloom filter is a space-efficient probabilistic data structure, conceived by Burton Howard Bloom in 1970, that is used to test whether an element is a member of a set. False positive matches are possible, but false negatives are not – in other words, a query returns either "possibly in set" or "definitely not in set". Elements can be added to the set, but not removed (though this can be addressed with a "counting" filter); the more elements that are added to the set, the larger the probability of false positives.

翻译过来就是:布隆过滤器由 Bloom 在 1970 年提出,它是一个非常节省空间的数据结构,且被用来测试一个元素是否在一个集合中。如果它告诉你「不在」,那就一定不在集合中;但如果它告诉你「在」,那也有可能不在。并且你可以向集合中添加更多的元素,但由此会带来更高的误判率。你也不能从集合中删除元素。

算法描述

通常我们去判断一个元素是否在集合中的方法是:将这个元素逐一与集合中的所有元素对比,但这种方法的时间复杂度为 $O(n)$,所以随着元素数量的增长,查询效率会下降。但布隆过滤器则通过 hash 的方法去查找,所以会快很多。

布隆过滤器本质上是一个很长的二进制数组,数组中每一个元素都是 0 或者 1,类似于 STL 中的 bitset,初始值都为 0。向集合中添加元素时,它将待查找的元素经过 k 个哈希函数的映射,得到 k 个值为($v_1$,$v_2$....$v_k$) 的一个向量,对该向量的每一个值所对应的下标的数组元素置为 1。之后在查找某个元素时,也将这个元素经过同样的 k 个哈希函数,并检查是否这些值对应的数组下标都为 1。只要有一个是 0,则该元素肯定不在集合中;如下图,集合 {x,y,z} 经过三个哈希函数分别映射到数组下标 1,3,4,5,11,13,16 位置上,元素 w 映射到下标 4,13,15 位置上,由于 array[15]==0,所以 w 不在集合 {x,y,z} 中。反之,如果都为 1,则该元素有一定的概率 $P$ 在集合中,$1-P$ 的概率不在。因为当集合中元素很多的时候,数组中这 k 个元素可能是由其他元素置位的,导致误判。至于这个概率 $P$ 是多大,跟集合中元素数量 s、数组大小 m 和选取的 k 个哈希函数都有关。

由此可见,这三个因素都归并到了「哈希碰撞」这个问题上。所以布隆过滤器的设计过程很大程度上就是一个好的哈希算法的设计过程。

哈希算法

一个哈希算法由一个哈希数组、哈希函数组成。其思想是将元素经过哈希函数映射到数组中。但元素集合在很多情况下是无限或接近于无限的,而数组空间是有限的。这便必定产生矛盾--即碰撞。从逻辑上说,所有的哈希算法都是无法避免碰撞的(从无限集到有限集的映射),但应该尽可能地减少碰撞。