小伙伴们大家好，今天介绍BloomFilter布隆过滤器。相信大家对BloomFilter一定不陌生，但是可能只是知道名字，并不知道原理而且没有动手去放到自己的项目中。

今天带大家一套打通BloomFilter，如有补充，欢迎评论或者私信！！

1. 案例

现在有50亿个用户id，给你10万个用户id，如何判断这10万个用户id是否存在于这50亿个中。

此时，或许你有两种解决方案

数据库查询：用数据库查询要想实现这么多数据快速查询有点困难数据预存放到内存中：50亿*8字节大约40G，内存占用太大了

那咋实现呢？

2. 什么是BloomFilter

布隆过滤器（英语：Bloom Filter）是 1970 年由布隆提出的。

它实际上是一个很长的二进制数组+一系列随机hash算法映射函数，主要用于判断一个元素是否在集合中。

通常我们会遇到很多要判断一个元素是否在某个集合中的业务场景，一般想到的是将集合中所有元素保存起来，然后通过比较确定。 链表、树、散列表（又叫哈希表，Hash table）等等数据结构都是这种思路。

但是随着集合中元素的增加，我们需要的存储空间也会呈现线性增长，最终达到瓶颈。同时检索速度也越来越慢，上述三种结构的检索时间复杂度分别为O(n),O(logn),O(1)。这个时候，布隆过滤器（Bloom Filter）就应运而生。

一句话就是由一个初值都为0的bit数组和多个哈希函数构成，用来快速判断某一个数据是否存在。本质就是判断具体数据存不存在一个大的集合中。

布隆过滤器是一种类似set的数据结构，只是统计结果不太准确。

3. 在centos7下布隆过滤器2种安装方式3.1 采用docker安装RedisBloom，推荐

Redis 在 4.0 之后有了插件功能（Module），可以使用外部的扩展功能， 可以使用 RedisBloom 作为 Redis 布隆过滤器插件。

docker run -p 6379:6379 --name=redis6379bloom -d redislabs/rebloom

docker exec -it redis6379bloom /bin/bash

redis-cli

3.2 编译安装3.3 布隆过滤器常用操作命令

bf.reserve filter 0.01 100bf.add filter v11bf.exists filter v11bf.exists filter v12复制代码

error_rate：误判率

initial_size：数组初始大小

bf.add key 值bf.exists key 值bf.madd 一次添加多个元素bf.mexists 一次查询多个元素是否存在4. BloomFilter特点高效的插入和查询，占用空间少，返回的结果是不确定性的一个元素如果判断结果为存在的时候元素不一定存在，但是判断结果为不存在的时候则一定不存在布隆过滤器可以添加元素，但是不能删除元素。因为删掉元素会导致误判率增加误判只会发生在过滤器没有添加过的元素，对于添加过的元素不会发生误判

有，可能有

无，一定无，可以保证的是，如果布隆过滤器判断一个元素不在一个集合中，那这个元素一定不会在集合中

5. BloomFilter原理5.1 Java中的传统hash

哈希函数的概念是：将任意大小的输入数据转换成特定大小的输出数据的函数，转换后的数据称为哈希值或哈希编码，也叫散列值

如果两个散列值是不相同的（根据同一函数）那么这两个散列值的原始输入也是不相同的。 这个特性是散列函数具有确定性的结果，具有这种性质的散列函数称为单向散列函数。

散列函数的输入和输出不是唯一对应关系的，如果两个散列值相同，两个输入值很可能是相同的，但也可能不同， 这种情况称为“散列碰撞（collision）”。

用 hash表存储大数据量时，空间效率还是很低，当只有一个 hash 函数时，还很容易发生哈希碰撞。

5.2 Java中的哈希碰撞实例

案例一：

案例二：

5.3 初探布隆过滤器实现原理和数据结构

布隆过滤器(Bloom Filter) 是一种专门用来解决去重问题的高级数据结构。

实质就是一个大型位数组和几个不同的无偏hash函数(无偏表示分布均匀)。由一个初值都为零的bit数组和多个个哈希函数构成，用来快速判断某个数据是否存在。

但是跟 HyperLogLog(juejin.cn/post/719106…) 一样，它也一样有那么一点点不精确，也存在一定的误判概率。

添加key时

使用多个hash函数对key进行hash运算得到一个整数索引值，对位数组长度进行取模运算得到一个位置， 每个hash函数都会得到一个不同的位置，将这几个位置都置1就完成了add操作。

查询key时

只要有其中一位是零就表示这个key不存在，但如果都是1，则不一定存在对应的key。

结论：

有，是可能有

无，是肯定无

5.4 进一步探索

当有变量被加入集合时，通过N个映射函数将这个变量映射成位图中的N个点， 把它们置为 1（假定有两个变量都通过 3 个映射函数）。

查询某个变量的时候我们只要看看这些点是不是都是 1， 就可以大概率知道集合中有没有它了。

如果这些点，有任何一个为零则被查询变量一定不在，

如果都是 1，则被查询变量很可能存在，

为什么说是可能存在，而不是一定存在呢？那是因为映射函数本身就是散列函数，散列函数是会有碰撞的。

5.5 布隆过滤器三步骤初始化

布隆过滤器本质上是由长度为 m 的位向量或位列表（仅包含 0 或 1 位值的列表）组成，最初所有的值均设置为 0。

添加

当我们向布隆过滤器中添加数据时，为了尽量地址不冲突，会使用多个 hash 函数对 key 进行运算，算得一个下标索引值，然后对位数组长度进行取模运算得到一个位置，每个 hash 函数都会算得一个不同的位置。

再把位数组的这几个位置都置为 1 就完成了 add 操作。

例如，我们添加一个字符串wmyskxz

判断是否存在

向布隆过滤器查询某个key是否存在时，先把这个 key 通过相同的多个 hash 函数进行运算，查看对应的位置是否都为 1，

只要有一个位为 0，那么说明布隆过滤器中这个 key 不存在；

如果这几个位置全都是 1，那么说明极有可能存在；

因为这些位置的 1 可能是因为其他的 key 存在导致的，也就是前面说过的hash冲突。

就比如我们在 add 了字符串wmyskxz数据之后，很明显下面1/3/5 这几个位置的 1 是因为第一次添加的 wmyskxz 而导致的； 此时我们查询一个没添加过的不存在的字符串inexistent-key，它有可能计算后坑位也是1/3/5 ，这就是误判了......

5.6 关于BloomFilter的误判率，为什么不要删除？

布隆过滤器的误判是指多个输入经过哈希之后在相同的bit位置1了，这样就无法判断究竟是哪个输入产生的， 因此误判的根源在于相同的 bit 位被多次映射且置 1。

这种情况也造成了布隆过滤器的删除问题，因为布隆过滤器的每一个 bit 并不是独占的，很有可能多个元素共享了某一位。

如果我们直接删除这一位的话，会影响其他的元素。

5.7 BloomFilter小总结存在则很可能存在，不存在则一定不存在。使用时最好不要让实际元素数量远大于初始化数量当实际元素数量超过初始化数量时，应该对布隆过滤器进行重建， 重新分配一个 size 更大的过滤器，再将所有的历史元素批量 add 进行6. BloomFilter优缺点

优点：高效的插入和删除，占用空间很少

缺点：

不能删除元素，因为删除元素会导致误判率增大，因为hash冲突，bit数组中同一个位置存放的数据可能是多个key进行hash计算后共有的存在误判：不同的数据可能出来相同的值7. 布谷鸟过滤器

为了解决布隆过滤器不能删除元素的问题，布谷鸟过滤器横空出世。论文《Cuckoo Filter：Better Than Bloom》

作者将布谷鸟过滤器和布隆过滤器进行了深入的对比。相比布谷鸟过滤器而言布隆过滤器有以下不足： 查询性能弱、空间利用效率低、不支持反向操作（删除）以及不支持计数。

8. 实战数据库防止穿库。 Google Bigtable，HBase 和 Cassandra 以及 Postgresql 使用BloomFilter来减少不存在的行或列的磁盘查找。避免代价高昂的磁盘查找会大大提高数据库查询操作的性能。业务场景中判断用户是否阅读过某视频或文章，比如抖音或头条，当然会导致一定的误判，但不会让用户看到重复的内容。缓存宕机、缓存击穿场景，一般判断用户是否在缓存中，如果在则直接返回结果，不在则查询db，如果来一波冷数据，会导致缓存大量击穿，造成雪崩效应，这时候可以用布隆过滤器当缓存的索引，只有在布隆过滤器中，才去查询缓存，如果没查询到，则穿透到db。如果不在布隆器中，则直接返回。WEB拦截器，如果相同请求则拦截，防止重复被攻击。用户第一次请求，将请求参数放入布隆过滤器中，当第二次请求时，先判断请求参数是否被布隆过滤器命中。可以提高缓存命中率。Squid 网页代理缓存服务器在 cache digests 中就使用了布隆过滤器。Google Chrome浏览器使用了布隆过滤器加速安全浏览服务Venti 文档存储系统也采用布隆过滤器来检测先前存储的数据。SPIN 模型检测器也使用布隆过滤器在大规模验证问题时跟踪可达状态空间。

由于BloomFilter最常用的地方适用于解决缓存穿透，因此实战内容放到缓存穿透篇讲述。

以上就是BloomFilter的内容啦，感谢小伙伴的观看，有任何建议都可以联系我！！

作者：JavaLyHn

链接：