redis——布隆过滤器

1、 布隆过滤器的定义

定义：由一个初值都为0的bit数组和多个哈希函数构成，用来快速判断集合中是否存在某个元素。

设计思想：本质就是判断具体数据是否存在于一个大的集合内

备注：布隆过滤器是一种类似set的数据结构，只是统计结构在巨量数据线有点小瑕疵，不够完美。

2、 布隆过滤器的用途

高效地插入和查询，占用空间少，返回的结果是不确定性+不够完美。

重点： 一个元素如果判定结果：存在时，元素不一定存在，但是判断结果为不存在时，则一定不存在。

布隆过滤器可以添加元素，但是不能删除元素，由于设计hashcode判断依据，删掉元素会导致误判率增加。

3、 布隆过滤器的原理

布隆过滤器实现原理和数据结构：

原理： 布隆过滤器时一种专门用来解决去重问题的高级数据结构。实质就是一个大型位数组和几个不同的无偏hash函数（无偏表示分布均匀）。由一个初值都为零的bit数组和多个哈希函数构成，用来快速判断某个数据是否存在。但是跟HyperLogLog一样，它也一样有那么一点点不精确，也存在一定的误判概率。

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

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

查询某个变量的时候我们只要看看这些点是不是都是1，就可以大概率知道集合中有没有它了。
如果这些点，有任何一个为零则被查询变量一定不在，如果都是1，则被查询变量很可能存在。因为映射函数本身就是散列函数，散列函数会有碰撞的。

正是基于布隆过滤器的快速检测特性，我们可以在把数据写入数据库时，使用布隆过滤器做个标记。当缓存缺失后，应用查询数据库时，可以通过查询布隆过滤器快速判断数据是否存在。如果不存在，就不用再去数据库中查询了。这样一来，即使发生缓存穿透了，大量请求只会查询Redis和布隆过滤器，而不会积压到数据库，也就不会影响数据库的正常运行。布隆过滤器可以使用Redis实现，本身就能承担较大的并发访问压力。

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

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

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

布隆过滤器使用3个步骤：

1. 初始化bitmap
2. 添加占坑位（向布隆过滤器中添加数据时，为了尽量地址不冲突，会使用多个hash函数对key进行运算，算得一个下标索引值，然后对位数组长度进行取模运算得到一个位置，每个hash函数都会算得一个不同的位置。再把位数组的这几个位置都置为1就完成了add操作）
3. 判断是否存在（向布隆过滤器查询某个key是否存在时，先把这个key通过相同的多个hash函数进行运算，查看对应的位置是否都为1，只要有一个位为0，那么说明布隆过滤器中这个key不存在；如果这几个位置全都是1，那么说明极有可能存在）。

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

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

布隆过滤器可以添加元素，但是不能删除元素，因为删除元素会导致误判率增加。

总结

布隆过滤器在判断输入是否存在时候，如果有就很可能有，无的话就一定无。使用时最好不要让实际元素数量远大于初始化数量，一次给够避免扩容。当实际元素数量超过初始化数量时，应该对布隆过滤器进行重建，重新分配一个size更大的过滤器，再将所有的历史元素批量add进行。