布隆过滤器(Bloom Filter)简介

如果在系统中需要判断某个数据是否存在于集合中,一种可能的办法是把每个数据都存在容器中,然后再来查询,例如使用std::map。但有些情况下我们只关心数据存在与否,而并不关心数据本身。这种方法就会造成空间的浪费,影响系统整体的性能。在这种场景下,布隆过滤器则是一种很高效的办法。

布隆过滤器是一种非常节省空间的概率性数据结构。它可以非常快速地告诉你两个结果,“数据有可能存在于集合中”或者“数据一定不存在于集合中”。但布隆过滤器不是万能的,“Everything comes at a price”,为了获得查找的高性能,必须付出一些代价。很明显,布隆过滤器的结果并不那么精准。所以布隆过滤器只适用于那些可以容忍False Positive,但坚决不容忍False Negative的场景。比如,HBase中就使用了bloom filter来优化系统对硬盘的读取[1]

布隆过滤器的数据结构就是一个m位的bit数组。另外有k个不同的hash函数,其中每个函数会将输入的内容映射到bit数组的其中一位上。剩下的事情就很简单了,如果是新插入一条数据,只要把内容传给k个hash函数,得到k个位置,然后将数组中对应位置为1。如果是查询某个数据是否存在,则把数据内容做k个hash,得到对应的bit位,如果bit数组中这些位上的值有一个为0,那么这条数据肯定不存在。如果全部为1,则说明有可能已经存在。

Bloom_filter1

上面是布隆过滤器的示意图,可以看到这个布隆过滤器的bit数组有18位,另外有3个hash函数。

至于是否在实际系统中使用,还是要看对应的场景需求。参考链接中也有实际应用场景的例子[2]


参考

  1. Quora – How are bloom filters used in HBase?
  2. Bloom filter usage
  3. Bloom Filters by Example
  4. What is the advantage to using bloom filters?