布隆过滤器简介

布隆过滤器简介

16 2019-12-26 21:02:33

## 背景
遇见一道算法题：

从一个未排序的整数数组，找出其中没有出现过的最小的正整数。

要求：时间复杂度为O(n)，使用常数级别的额外空间。

根据题目要求，

1. 时间复杂度为O(n)，说明不允许排序，不允许多重循环，只允许常数次单层循环；
2. 常数级别的额外空间，说明不允许使用HashSet、HashMap这样的容器进行统计；
3. 没说数组长度有多少，猜测是非常长。

犯难了，想不出怎么解，关键是常数额外空间。于是想使用指定长度的布隆过滤器，也算常数额外空间对吧？（当然这个解法并不好使）

说到为何要用布隆过滤器，在之前介绍缓存穿透时提过，现在详细介绍一下。

## 布隆过滤器是什么
### 特性
`Bloom Filter`，布隆过滤器，是一种数据结构，一种占用空间小并能够高效判断集合中是否包含某个元素的数据结构，具有这些特点：

1. 自身是一个Bit数组
2. 除了使用的Hash计算外，能够在O(n)时间复杂度构建针对目标容器的布隆过滤器，并且使用的空间远小于目标容器
3. 除了使用的Hash计算外，能够在O(1)时间复杂度计算目标容器中是否包含某元素
4. 如果布隆过滤器返回元素不存在，那么目标容器中一定不包含该元素
5. 如果布隆过滤器返回元素存在，那么目标容器中有不包括该元素，称之为误判，误判概率很小
6. 不能从布隆过滤器中删除元素

总结：**快 & 占用空间小，同样的空间可以存放更多元素 & 它说没有就真没有**

### 原理
布隆过滤器的原理很简单，就是牺牲准确率降低占用空间（同时也就节约了时间）。

**试想一下如下情况：**
1. 一个集合有一千万元素，每个元素占用空间1Kb，那么要判断元素是否在这个集合中就需要保存整个集合，大约占用10,000,000 * 1Kb约10Gb
2. 使用10G内存用来做一个contains判断有些划不来，怎么办？我们可能会将元素持久化，在判断时进行查询，那么我们增加了耗时降低了空间使用

**如果我们能够牺牲准确率呢？**
1. 我们使用一个大小为一千万的Bit数组，初始状态所有Bit都是0，将这个集合中的每个元素通过哈希算法映射为一个数字，即将Bit数组中的某一位置为1，那么理想情况下我们使用10,000,000 * 1b约10Mb就能够存下整个集合
2. 如果要判断contains，只需要通过同样的哈希函数计算目标元素的哈希值，并在这个Bit数组中对应位查找对应位即可，为1表示元素存在，否则表示不存在
3. 如果有重复元素怎么办？布隆过滤器只用来计算contains，元素重复对这个核心功能没有影响
4. 哈希算法一定存在碰撞，如果冲突了怎么办呢？这也就是布隆过滤器存在误判的原因
	- 如果存在碰撞，至少目标Bit被置为1了，那么contains返回结果为true表示有一定概率存在，这个概率取决于哈希算法的碰撞概率、数组大小和内部元素数量
	- 如果目标Bit为0，那么说明目标元素100%不存在

**如何尽量保证准确率够高？**
1. 降低哈希碰撞可以有效提高准确率，即扩大Bit数组长度，但相对的占用空间就大了
2. 还有一种方法，那就是使用多个哈希函数
	- 使用2个哈希函数，意味着每个元素被分别映射到Bit数组的两个Bit置1，而计算contains也一样，两个Bit任意一个为0表示元素不存在，可以提高准确率，但是多个哈希函数会影响计算效率，同时使用的哈希函数越多，每个元素占用的Bit位就越多，因此使用的哈希函数个数也并不是越多越好的

**构建过程**
![](/img/pic/2019122620581172816_png_503_180_6987)
> 插入元素'geeks'

![](/img/pic/2019122620584291017_png_502_191_6382)
> 插入元素'nerd'

![](/img/pic/2019122620585859318_png_494_180_6814)
> 插入元素'cat'

**为什么不能删除**
因为每一个Bit位都可能受到多个元素的影响。

了解原理后，上述布隆过滤器的特性应该就很好理解。

### 误判率
误判率的计算公式为：

$$\left(1-\left(1-\tfrac{1}{m}\right)^{kn}\right)^k$$

约等于

$$\left(1-e^{-\frac{kn}{m}}\right)^k$$

其中`k`表示哈希函数个数，`m`表示Bit数组大小，`n`表示已插入的不同元素的个数

可见，使用的数组越大误判率越低，插入的元素个数越多越容易发生误判；
一般我们在初始就需要设置好对应的空间大小`m`及哈希函数个数`k`，根据参考资料，函数个数`k = 0.7 * m / n`时误判率最低，这要求我们在决定好空间大小后预估集合内元素数量

![](/img/pic/2019122621012746219_png_800_456_57948)
> 误判率曲线

### 与HashSet的比较
平常我们排重一般用的HashSet，而Java的HashSet底层实现是使用HashMap，我们直接跟HashMap比较。

Bloom Filter的优点：

1. 节约空间，即使HashMap仅保存引用，保存一个元素引用至少也需要32位或64位，还不说一些Entry等额外的存储以及负载因子导致的一些空间占用，因此可以保存更多元素，在绝大多数情况下误差极小
2. 性能稳定，不会因为哈希碰撞导致插入或查询时间增加

HashMap的优点：

1. 可以删除
2. 不存在误差
3. 除了contains外还可以执行很多其他操作

总的来说，用途不同，一定要用在合适的地方。

## 用途
布隆过滤器最适合这样的场景：

1. 计算存在性
2. 数据量过大导致难以在内存中进行计算，需要将集合内元素持久化
3. 持久化后如果一趟请求没有命中，代价比较高
4. 持久化后难以支持高并发下的请求，有可能导致服务宕机
5. 少量误差可以接受

举例来说：

1. 防止缓存穿透
	- 并发量很高时，有大量请求查询不存在的数据，无法命中缓存，请求会直接打到持久化存储，导致存储负载高
	- 使用布隆过滤器可以大量减少对不存在数据的查询穿透
	- 少量误判情况会穿透，但对存储影响已显著减少
2. IO操作预判
	- 在网络/磁盘IO操作代价较大或耗时较高时，可以通过布隆过滤器预先拦截对不存在数据的操作
3. 注册用户名
	- 用户名是否存在？预先通过布隆过滤器筛选或许可以减少查询存储的时间
4. 爬虫
	- 已爬过的网页就跳过
	- 少量遗漏可以接受

## 补充
Google的guava包下有BloomFilter的实现，可以直接使用

## 参考资料
[[布隆过滤器BloomFilter] 举例说明+证明推导_小太阳~-CSDN博客](https://blog.csdn.net/quiet_girl/article/details/88523974)
[Probabilistic Data structures: Bloom filter - By ](https://hackernoon.com/probabilistic-data-structures-bloom-filter-5374112a7832)