博客主页：🏆看看是李XX还是李歘歘 🏆

🌺每天不定期分享一些包括但不限于计算机基础、算法、后端开发相关的知识点，以及职场小菜鸡的生活。🌺

💗点关注不迷路，总有一些📖知识点📖是你想要的💗

⛽️今天的内容是    布隆过滤器(BloomFilter)原理和实现      ⛽️💻💻💻

定义

布隆过滤器是一种比较巧妙的概率型数据结构（probabilistic data structure），特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”。实际上是一个很长的二进制向量和一系列随机映射函数，二进制存储的数据是0或1，默认是0。0代表不存在某个数据，1代表存在某个数据。

用途

主要用于处理数据的过滤，减少磁盘 IO 或者网络请求。例如：网页URL 去重（网址进行过滤，已经存在布隆中的网址，不在读取；）、垃圾邮件识别（垃圾邮件过滤，发送方地址命中布隆过滤器的黑名单，则认定为垃圾邮件。）、黑名单、查询加速【比如基于KV结构的数据】、集合元素重复的判断、解决Redis缓存穿透问题；等场景。

原理

背景：通常判断某个元素是否存在，会用HashMap，将值映射到 HashMap 的 Key，然后可以在 O(1) 的时间复杂度内返回结果，效率高。但是 HashMap 的实现也有缺点，例如存储容量占比高，考虑到负载因子的存在，通常空间是不能被用满的，但是值很多，例如上亿的时候，那 HashMap 占据的内存大小就会非常大了。或者数据集存储在远程服务器上，本地服务接受输入，而数据集非常大不可能一次性读进内存构建 HashMap 的时候，也会存在问题。

布隆过滤器的实现原理：通过K个散列函数将一个元素映射成位数组中的K个点，把它们置为1。检索时，我们只要看看K个点是不是都是1，就知道集合中有没有它了：如果这些点有任何一个0，则被检元素一定不在；如果都是1，则被检元素很可能存在。

因为每个点并不是只有一个元素会占用，这个点的值可能会被其他元素覆盖，如果K个点中有一个点为0，说明这个元素一定没有映射，如果都是1，可能是其他元素刚刚好将这个元素的K个点都置为1了。

实现

存入

布隆过滤器是一个二进制数据的集合。存入过程如下：

1. 通过K个哈希函数计算该数据，返回K个计算出的hash值
2. 这些K个hash值映射到对应的K个二进制的数组下标
3. 将K个下标对应的二进制数据改成1。

查询

布隆过滤器主要作用就是查询一个数据是否在这个二进制的集合中。查询过程如下：

1. 通过K个哈希函数计算该数据，对应计算出的K个hash值
2. 通过hash值找到对应的二进制的数组下标
3. 判断：如果存在一处位置的二进制数据是0，那么该数据不存在。如果都是1，该数据可能存在集合中。

优点

1. 由于存储的是二进制数据，所以占用的空间很小；
2. 它的插入和查询速度是非常快的，时间复杂度是O（K）；
3. 保密性很好，因为本身不存储任何原始数据，只有二进制数据。

缺点

1. 概率型数据结构，可能不准确，只能确定某元素一定不存在或者可能存在，不能确定某元素真的存在
2. 删除困难，由于映射的K个点中可能出现多个元素共用的情况，删除的过程中，这几个点的变化可能会涉及其他值的变化，所以不易删除（不是不能）

Counting Bloom Filter 的原理：

Counting Bloom Filter 的出现，解决了BloomFilter删除困难的问题，它将标准 Bloom Filter 位数组的每一位扩展为一个小的计数器（Counter），在插入元素时给对应的 k （k 为哈希函数个数）个 Counter 的值分别加 1，删除元素时给对应的 k 个 Counter 的值分别减 1。Counting Bloom Filter 通过多占用几倍的存储空间的代价， 给 Bloom Filter 增加了删除操作。基本原理是不是很简单？看下图就能明白它和 Bloom Filter 的区别在哪。

补充

如何选择哈希函数个数和布隆过滤器长度？

1. 布隆过滤器长度小，所有的 bit 位很快会被置为 1，那么查询任何值都会返回“可能存在”，起不到过滤的目的了。布隆过滤器的长度会直接影响误报率，布隆过滤器越长其误报率越小。
2. 哈希函数的个数需要权衡，个数越多则布隆过滤器 bit 位置位 1 的速度越快，且布隆过滤器的效率越低；但是如果太少的话，那我们的误报率会变高。

哈希函数个数和布隆过滤器长度有个公式可以计算，包括Counting Bloom Filter中计数器大小的选择也有公式