布隆过滤器：集合去重

电玩女神 2022-02-25 00:16 267阅读 0赞

## 简介 ##

布隆过滤器（Bloom Filter）实际上是一个很长的二进制向量和一系列随机映射函数。

布隆过滤器可以用于检索一个元素是否在一个集合中。

## 原理 ##

当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个位数组中的K个点，把它们置为1。检索时，我们只要看看这些点是不是都是1：如果这些点有任何一个0，则被检元素一定不在；如果都是1，则被检元素很可能在集合中（获得在这个集合中的概率）。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMwMDc5MDA_size_16_color_FFFFFF_t_70_pic_center]

### False positives 概率推导 ###

BloomFilter有以下参数:

1.  m 位数组的长度
2.  n 加入其中元素的数量
3.  k 哈希函数的个数
4.  f False Positive

假设 Hash 函数以等概率条件选择并设置 Bit Array 中的某一位，那么位数组中某一特定的位在进行元素插入时的 Hash 操作中没有被置位的概率是：

1 − 1 m 1-\{1\\over m\} 1−m1

那么在所有 k 次 Hash 操作后该位都没有被置 “1” 的概率是：

( 1 − 1 m ) k (1-\{1\\over m\})^k (1−m1)k

该位为 "1"的概率是：

1 − ( 1 − 1 m ) k 1-(1-\{1\\over m\})^k 1−(1−m1)k

现在检测某一元素是否在该集合中。标明某个元素是否在集合中所需的 k 个位置都按照如上的方法设置为 “1”，但是该方法可能会使算法错误的认为某一原本不在集合中的元素却被检测为在该集合中（False Positives），该概率由以下公式确定：

\[ 1 − ( 1 − 1 m ) k n \] k ≈ ( 1 − e k n m ) k \[1-(1-\{1\\over m\})^\{kn\}\]^\{k\} \\approx (1-e^\{kn\\over m\})^k \[1−(1−m1)kn\]k≈(1−emkn)k

在给定m和n时，能够使f最小化的k值为：

m n l n 2 ≈ 0.7 m n \{m\\over n\}ln2\\approx 0.7\{m\\over n\} nmln2≈0.7nm

此时给出的f为：

1 2 k ≈ 0.618 5 m n \{1\\over 2\}^k\\approx 0.6185^\{m\\over n\} 21k≈0.6185nm

根据这个公式也能得到，在另外三个数给定的情况下，第四个数嘶多少。

## 优缺点 ##

### 优点 ###

相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。

布隆过滤器存储空间和插入/查询时间都是常数。另外, Hash 函数相互之间没有关系，方便由硬件并行实现。布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。

布隆过滤器可以表示全集，其它任何数据结构都不能；

k 和 m 相同，使用同一组 Hash 函数的两个布隆过滤器的交并差运算可以使用位操作进行。

### 缺点 ###

误算率（False Positive）。随着存入的元素数量增加，误算率随之增加。但是如果元素数量太少，则使用散列表足矣。

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

## 典型的应用场景 ##

某些存储系统的设计中，会存在空查询缺陷：当查询一个不存在的key时，需要访问慢设备，导致效率低下。

比如一个前端页面的缓存系统，可能这样设计：先查询某个页面在本地是否存在，如果存在就直接返回，如果不存在，就从后端获取。但是当频繁从缓存系统查询一个页面时，缓存系统将会频繁请求后端，把压力导入后端。

这是只要增加一个bloom算法的服务，后端插入一个key时，在这个服务中设置一次  
需要查询后端时，先判断key在后端是否存在，这样就能避免后端的压力。

### 实际用例 ###

Google Chrome浏览器使用了布隆过滤器加速安全浏览服务。

Google 著名的分布式数据库 Bigtable 使用了布隆过滤器来查找不存在的行或列，以减少磁盘查找的IO次数。

## 参考文献 ##

1.  [大数据量下的集合过滤—Bloom Filter][Bloom Filter]
2.  [Bloom Filters by Example][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMwMDc5MDA_size_16_color_FFFFFF_t_70_pic_center]: /images/20220225/1ff34a9ccf284c26b211a997fb56a86f.png
[Bloom Filter]: https://www.cnblogs.com/z941030/p/9218356.html
[Bloom Filters by Example]: https://llimllib.github.io/bloomfilter-tutorial/zh_CN/