概述
布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构，特点是高效地插入和查询，查询时可以用来判断 “一定不存在或者可能存在”，它是用多个哈希函数，将一个数据映射到位图结构中。
原理
当一个元素被加入集合时，通过 K 个散列函数将这个元素映射成一个位图中的 K 个位置，把它们置为 1。查询时，只要查看这些位置是不是都是 1 ，就知道集合中有没有它了：如果这些位置有任何一个 0，则被查询元素一定不存在；如果都是 1，则被查询元素很可能存在。
简单来说就是将一个长度为 m 的位数组的所有元素初始化为 0，用 k 个散列函数对元素进行 k 次散列运算跟 len (m) 取余得到 k 个位置并将 m 中对应位置设置为 1。
如上图，位数组的长度是８，散列函数个数是 3，两个元素ｘ，ｙ。这两个元素都经过三次哈希函数生成三个哈希值，并映射到位数组的不同的位置，并置为1。元素 x 映射到位数组的第０位，第４位，第７位，元素ｙ映射到数组的位数组的第１位，第４位，第６位。
当布隆过滤器保存的元素越多，被置为 1 的 bit 位也会越来越多，元素 z 即便没有存储过，假设哈希函数将z映射到位数组的三个位都被其他值设置为 1 了，对于布隆过滤器的机制来讲，元素 z 这个值也是存在的，也就是说布隆过滤器存在一定的误判率。因此布隆过滤器只能保证一定不存在和可能存在。
误判率
布隆过滤器包含如下四个属性：
- k : 哈希函数个数
- m : 位数组长度
- n : 插入的元素个数
- p : 误判率
若位数组长度太小则会导致所有 bit 位很快都会被置为 1 ，那么检索任意值都会返回“可能存在” ， 起不到过滤的效果。位数组长度越大，则误判率越小。同时，哈希函数的个数也需要考量，哈希函数的个数越大，检索的速度会越慢，误判率也越小，反之，则误判率越高。
为什么就用一个hash函数不行？
其实布隆过滤器底层是用 位图 实现的，而多个hash函数就是为了减少位图的误判率的。具体可往下看
假设布隆过滤器中的hash函数满足simple uniform hashing假设：每个元素都等概率地hash到m个位中的任何一个，与其它元素被hash到哪个位无关。那么
- 1 次hash函数后 某一个bit 被置为1的概率为：
- 1次hash函数后 某一个bit 未被置为1的概率为：
- k次hash函数某一个bit 未被置为1的概率为：
- 如果插入了n个元素，某一个bit 都 未被置为1的概率为：
- 那么这个位被 置为 1的 概率就为：
- 那么查询阶段，若对应某个待查询元素的k 的bit全部置位为1，则可判定其在集合中。因此某元素误判率p为：
p =
显然，当m越大，n减少时，误判率就越低。并且当k越大，误判率p也就越小，也就是说，hash函数越多，误判率越低，但相对检索的速度会越慢。
如图：相同位数组长度的情况下，随着哈希函数的个数的增长，误判率显著的下降。
布隆过滤器的效率和缺点
布隆过滤器的空间复杂度为 O(m) ，插入和查询时间复杂度都是 O(k) 。 存储空间和插入、查询时间都不会随元素增加而增大。 空间、时间效率都很高。
但是布隆过滤器并不支持删除元素，因为多个元素可能哈希到一个布隆过滤器的同一个位置，如果直接删除该位置的元素，则会影响其他元素的判断。因此，就提出了 计数布隆过滤器
计数布隆过滤器
计数过滤器（Counting Bloom Filter）是布隆过滤器的扩展，标准 Bloom Filter 位数组的每一位扩展为一个小的计数器（Counter），在插入元素时给对应的 k （k 为哈希函数个数）个 Counter 的值分别加 1，删除元素时给对应的 k 个 Counter 的值分别减 1。
显然，又引入了另一个问题：更多的资源占用，而且在很多时候会造成极大的空间浪费
使用场景
Redis的缓存穿透
对于一个数据查询，其过程大致如下：
但是当查询的数据既不在缓存中，也不存在数据库中，则没有办法回写缓存，当有类似这样大量的请求访问服务时，数据库的压力就会极大。这就是缓存穿透
因此，引入布隆过滤器，当用户请求时，判断过滤器中是否存在该元素，若不存在该元素，则直接返回不存在。若包含则从缓存中查询数据，若缓存中也没有，则查询数据库并回写到缓存里，最后给前端返回。
尽管布隆过滤器有少量的误判，即可能不存在的数据会判定存在，从而继续查询缓存和数据库，但只要将m和k的值设置相对理想，少量的不存在查询也是可以接受的。
元素删除场景
实际上，元素不仅仅是只有增加，还存在删除元素的场景，比如说商品的删除，删除后数据其实已经不存在了，但是布隆过滤器中还没删除，则会判定其存在。
第一种方案就是使用计数布隆过滤器。
第二种方案，则是通过 定时重新构建布隆过滤器
- 定时任务触发全量商品查询，更新数据;
- 将商品添加到新的布隆过滤器 ;
- 修改商品布隆过滤器的映射（从旧 A 修改成 新 B ）;
- 商品服务根据布隆过滤器的映射，选择新的布隆过滤器 B进行相关的查询操作 ；
- 选择合适的时间点，删除旧的布隆过滤器 A。
在删除商品 到 使用新的布隆过滤器B 之间的这段时间的不存在的查询有可能还会到数据库层面，但这种少量的不存在查询也是可以接受的。
总结
布隆过滤器的空间效率O(m) 和查询时间O(k) 都很优秀，但是存在一定的误判率 （布隆过滤器认为不存在，则一定不存在；布隆过滤器认为存在，则只是可能存在）
bit数组的位数m越大，hash函数的个数k越多，误判率就越低。但也需要控制合适的大小，比如m越大，但存储的数据少，则会引起空间浪费，k的个数越多，则会一定程度降低查存效率
普通布隆过滤器无法删除元素，但可以通过计数布隆过滤器和定时重新构建布隆过滤器两种方案实现删除元素的效果。
