❶ 布隆过滤器
布隆过滤器 （英语：Bloom Filter）是 1970 年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。主要用于判断一个元素是否在一个集合中。
通常我们会遇到很多要判断一个元素是否在某个集合中的业务场景，一般想到的是将集合中所有元素保存起来，然后通过比较确定。链表、树、散列表（又叫哈希表，Hash table）等等数据结构都是这种思路。但是随着集合中元素的增加，我们需要的存储空间也会呈现线性增长，最终达到瓶颈。同时检索速度也越来越慢，上述三种结构的检索时间复杂度分别为，，。
这个时候，布隆过滤器（Bloom Filter）就应运而生。
了解布隆过滤器原理之前，先回顾下 Hash 函数原理。
哈希函数的概念是：将任意大小的输入数据转换成特定大小的输出数据的函数，转换后的数据称为哈希值或哈希编码，也叫散列值。下面是一幅示意图：
所有散列函数都有如下基本特性：
但是用 hash表存储大数据量时，空间效率还是很低，当只有一个 hash 函数时，还很容易发生哈希碰撞。
BloomFilter 是由一个固定大小的二进制向量或者位图（bitmap）和一系列映射函数组成的。
在初始状态时，对于长度为 m 的位数组，它的所有位都被置为0，如下图所示：
[图片上传失败...(image-303c04-1595324887187)]
当有变量被加入集合时，通过 K 个映射函数将这个变量映射成位图中的 K 个点，把它们置为 1（假定有两个变量都通过 3 个映射函数）。
查询某个变量的时候我们只要看看这些点是不是都是 1 就可以大概率知道集合中有没有它了
为什么说是可能存在，而不是一定存在呢？那是因为映射函数本身就是散列函数，散列函数是会有碰撞的。
布隆过滤器的误判是指多个输入经过哈希之后在相同的bit位置1了，这样就无法判断究竟是哪个输入产生的，因此误判的根源在于相同的 bit 位被多次映射且置 1。
这种情况也造成了布隆过滤器的删除问题，因为布隆过滤器的每一个 bit 并不是独占的，很有可能多个元素共享了某一位。如果我们直接删除这一位的话，会影响其他的元素。(比如上图中的第 3 位)
相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数 ，另外，散列函数相互之间没有关系，方便由硬件并行实现。布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。
布隆过滤器可以表示全集，其它任何数据结构都不能；
但是布隆过滤器的缺点和优点一样明显。误算率是其中之一。随着存入的元素数量增加，误算率随之增加。但是如果元素数量太少，则使用散列表足矣。
另外，一般情况下不能从布隆过滤器中删除元素。我们很容易想到把位数组变成整数数组，每插入一个元素相应的计数器加 1, 这样删除元素时将计数器减掉就可以了。然而要保证安全地删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面。这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。
在降低误算率方面，有不少工作，使得出现了很多布隆过滤器的变种。
在程序的世界中，布隆过滤器是程序员的一把利器，利用它可以快速地解决项目中一些比较棘手的问题。
如网页 URL 去重、垃圾邮件识别、大集合中重复元素的判断和缓存穿透等问题。
布隆过滤器的典型应用有：
知道了布隆过滤器的原理和使用场景，我们可以自己实现一个简单的布隆过滤器
分布式环境中，布隆过滤器肯定还需要考虑是可以共享的资源，这时候我们会想到 Redis，是的，Redis 也实现了布隆过滤器。
当然我们也可以把布隆过滤器通过 bloomFilter.writeTo() 写入一个文件，放入OSS、S3这类对象存储中。
Redis 提供的 bitMap 可以实现布隆过滤器，但是需要自己设计映射函数和一些细节，这和我们自定义没啥区别。
Redis 官方提供的布隆过滤器到了 Redis 4.0 提供了插件功能之后才正式登场。布隆过滤器作为一个插件加载到 Redis Server 中，给 Redis 提供了强大的布隆去重功能。
在已安装 Redis 的前提下，安装 RedisBloom，有两种方式
直接编译进行安装
使用Docker进行安装
使用
布隆过滤器基本指令：
我们只有这几个参数，肯定不会有误判，当元素逐渐增多时，就会有一定的误判了，这里就不做这个实验了。
上面使用的布隆过滤器只是默认参数的布隆过滤器，它在我们第一次 add 的时候自动创建。
Redis 还提供了自定义参数的布隆过滤器，bf.reserve 过滤器名 error_rate initial_size
但是这个操作需要在 add 之前显式创建。如果对应的 key 已经存在，bf.reserve 会报错
我是一名 Javaer，肯定还要用 Java 来实现的，Java 的 Redis 客户端比较多，有些还没有提供指令扩展机制，笔者已知的 Redisson 和 lettuce 是可以使用布隆过滤器的，我们这里用 Redisson
为了解决布隆过滤器不能删除元素的问题，布谷鸟过滤器横空出世。论文《Cuckoo Filter：Better Than Bloom》作者将布谷鸟过滤器和布隆过滤器进行了深入的对比。相比布谷鸟过滤器而言布隆过滤器有以下不足：查询性能弱、空间利用效率低、不支持反向操作（删除）以及不支持计数。
❷ 布隆过滤器(Bloom Filter)的原理和实现
看下下面几个问题
通常的做法有如下几种思路：
在继续介绍布隆过滤器的原理时，先讲解下关于哈希函数的预备知识。
可以明显的看到，原始数据经过哈希函数的映射后称为了一个个的哈希编码，数据得到压缩。哈希函数是实现哈希表和布隆过滤器的基础。
布隆过滤器（Bloom Filter）的核心实现是一个超大的位数组和几个哈希函数。假设位数组的长度为m，哈希函数的个数为k
❸ 借助Redis Bitmap实现简单的布隆过滤器
在之前的 一篇文章 中，我们已经深入理解了布隆过滤器的基本原理，并且了解到它在缓存系统中有较多的应用。Redis提供的Bitmap正好能够作为布隆过滤器所需要的位数组的基础，本文先简要介绍Bitmap，然后给出基于它的布隆过滤器实现。
Bitmap在Redis中并不是一个单独的数据类型，而是由字符串类型（Redis内部称Simple Dynamic String，SDS）之上定义的与比特相关的操作实现的，此时SDS就被当做位数组了。下面是在redis-cli中使用getbit和setbit指令的操作示例。
Redis的Bitmap是自动扩容的，亦即get/set到高位时，就会主动填充0。此外，还有bitcount指令用于计算特定字节范围内1的个数，bitop指令用来执行位运算（支持and、or、xor和not）。相应的用法可以查询Redis官方文档等。
下面我们基于Redis（Codis）实现布隆过滤器RedisBloomFilter。根据之前讲解布隆过滤器的文章，要初始化一个布隆过滤器的话，需要两个参数：预估的元素数量，以及可接受的最大误差（即假阳性率）。另外，我们也需要传入Jodis的连接池实例JedisResourcePool，以方便在Redis上操作。RedisBloomFilter类的成员和构造方法如下所示。
为了区分出布隆过滤器对应的Key，在原始Key的前面都加上"bf:"前缀。Bitmap长度bitmapLength和哈希函数个数numHashFunctions则利用Guava版实现中的方法来计算。
然后，我们需要计算一个元素被k个哈希函数散列后，对应到Bitmap的哪些比特上。这里仍然借鉴了Guava的BloomFilterStrategies实现，采用MurmurHash和双重哈希进行散列。为了应用简单，假设所有元素固定为字符串类型，不用泛型。
然后我们就可以通过Jedis的setbit()和getbit()方法来实现向布隆过滤器中插入元素与查询元素是否存在的逻辑了。一个元素会对应多个比特，为了提高效率，流水线就派上用场了。另外，setbit指令不会重置对应Key的过期时间戳。
完毕，写个简单的单元测试吧。假设现在用布隆过滤器来存储已读帖子的ID，Key中包含用户ID和时间。每天预估的每用户最大阅读量是3000篇，最大误差3%。
观察输出。