分类 "数据结构" 下的文章

布隆过滤器 (Bloom Filter) 是 1970 年由布隆提出的. 它可以检索一个元素是否存在于集合中. 它的优点是空间效率高, 查询时间极快, 缺点是有一定的误判率, 而且删除困难.

1. 背景

编程中, 经常会有判断一个元素是否存在一个集合中:

  • 网络爬虫程序: 判断一个地址是否被访问过;
  • 文字处理软件: 检查单词的拼写 (也就是判断它是否存在词典里);
  • 电子邮件黑名单.

其中, 最直接的办法是, 将集合所有元素存储起来, 判断时与集合中的元素比较即可. 链表, 树和哈希表, 都是这样的思路. 随着集合元素的增加, 我们需要更大的存储空间, 也需要花费更长的时间检索, 时间复杂度分别为 O(n) , O(logn) , O(n/k) .

2. 原理

布隆过滤器, 实际上是由一个很长的二进制向量和一系列的随机映射函数构成的. 它的原理是, 当集合新增元素时, 通过 K 个哈希函数将该元素映射为一个位数组中的 K 个点, 把它们置为 1 . 检索时, 只需看这些点是否都是 1 , (大约) 就知道集合中有没有该因素. 如果这些点中有任何一个 0 , 该因素一定不存在; 如果都是 1 , 该元素 可能 存在.

新增元素时, 先用哈希函数 {x, y, z} 计算其哈希值, 再设置到二进制存储空间中:

x(k) = 0000 0000 1010 0010
y(k) = 0000 0001 0000 0001
z(k) = 0100 1001 0000 0000

其中, {x, y, z} 为哈希函数.

原二进制存储空间:
^---------------^---------------^---------------^---------------^
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
v---------------v---------------v---------------v---------------v

新增元素 k:
^---------------^---------------^---------------^---------------^
| 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 1 |
v---------------v---------------v---------------v---------------v
      ^           ^           ^   ^       ^               ^   ^
      |           |           |   x       x               x   |
      |           |           y                               y
      z           z           z

当然, 我们不能保证, 不存在另一个元素 k' , 使得哈希函数 {x, y, z} 的计算结果跟上图相同.

以检测一个可疑电子邮件地址是否存在黑名单为例: 布隆过滤器绝对不会漏掉任何一个存在黑名单的电子邮箱地址, 但它可能将不在黑名单中的电子邮箱误判. 补救方法是建立一个白名单, 将可能误判的电子邮箱地址保存起来.

3. 优点

  1. 存储空间, 插入时间, 查询时间均为常数 O(k);
  2. K 个哈希函数之间并无关联, 方便硬件并行实现;
  3. 不需要存储原始元素, 有利于数据保密.

4. 缺点

  1. 存在一定的误判率: 这个很容易理解, 因为不能保证不同元素通过哈希函数的计算后, 得到不同的哈希值.
  2. 删除元素困难: 这个也不难理解, 多个元素计算后, 可能会共用同一个 1 , 如果删除元素将其置 0 , 会导致其他元素出错.

引用维基百科的解释:

另外,一般情况下不能从布隆过滤器中删除元素。我们很容易想到把位数组变成整数数组,每插入一个元素相应的计数器加1, 这样删除元素时将计数器减掉就可以了。然而要保证安全地删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面。这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。

False positives 概率推导: https://www.cnblogs.com/liyulong1982/p/6013002.html

5. 实现

网上有个 Golang 版, 有时间的话写个 PHP 版, 不过 PHP 处理二进制真心不爽...