最近在看一些Redis的进阶应用,了解到Redis官方在4.0版本通过插件的方式提供了布隆过滤器的实现,之前也恰好在同事口中听到了布隆过滤器这样一个东西,于是花了一点时间去了解一下它的原理。

特性

布隆过滤器(Bloom Filter),常常被应用在一些去重、过滤的场景。如果我们使用普通的集合或哈希表来做这样的事情,因为它们都需要存储具体的元素,那么在存储空间的大小上会随着数据量的增加线性增加,最终成为一个瓶颈。因此对于不需要十分精确的场景,我们就可以使用布隆过滤器,它在空间和效率上,都有着很大的优势。

我认为可以将它理解成一个不精确的Set,我们可以向其中添加元素,并且查找某个元素是否在布隆过滤器中存在,但查找的结果并不一定是准确的,即存在一定误判的可能性。

当我们在布隆过滤器中查找一个元素是否存在时,如果它告诉你是不存在的,那么这个元素是一定不存在的,但如果它告诉你这个元素是存在的,那么他有可能是不存在的。想知道造成误判的原因,我们就需要去了解布隆过滤器的结构。

结构

布隆过滤器由一个很长的位数组和几个哈希函数组成。
bloom filter

我们将数组的长度记为l,哈希函数的个数记为k

添加元素

  1. 将需要添加的元素通过k个哈希函数进行计算,得到k个整数
  2. 将这k个整数对l取模,得到k个位置,将数组的这k个位置的值设置为1

查找元素是否存在

  1. 将需要添加的元素通过k个哈希函数进行计算,得到k个整数
  2. 将这k个整数对l取模,得到k个位置
  3. 如果这k个位置的值都为1,那么这个元素就是可能存在的
  4. 只要这k个位置的值有一个为0,那么这个元素肯定是不存在的

那么为什么如果这k个位置的值都为1,这个元素也有可能是不存在的呢。因为这个位置的1有可能是因为别的元素散列到这个位置被设置成1的。这里就造成了误判。
至于为什么要设置多个哈希函数,就是要尽可能的减少误判的可能性。假设如果只有一个哈希函数,那么哈希冲突的可能性就会比较高,误判可能性也会较大。
布隆过滤器由于一个元素只需要几个bit的空间,相比集合或哈希表就有着巨大的优势。

小结

布隆过滤器对于位数组的长度、哈希函数的个数、误判率都有非常复杂的推导和论证的过程,以达到空间、时间、准确性上的平衡。大致理解了布隆过滤器的原理,我们就可以把它使用在一些合适的应用场景,Redis官方和guava也提供了实现。

计算机科学的很多实践都是在空间、时间、准确性寻求一个最佳的平衡,但是在自己目前的工作中,在业务层面出现性能问题时,很多时候是通过简单粗暴的加内存或加机器来暂时解决一些空间和时间上的问题,这显然不是一个好的方式。