redis中使用bloomfilter判断元素是否存在

一 bloomfiler的作用

1.1 bloomfilter的作用

由一个初始值为0的bit数组组成，和多个hash函数构成，用来判断集合中是否存在某个元素。

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

本质：判断一个数据是否存在一个大的集合中。有，可能有，无则一定没有

1.2 bloomfilter的原理

 1.3 使用场景

一般情况下，先查询缓存redis是否有该条数据，缓存中没有时，再查询数据库。当数据库也不存在该条数据时，每次查询都要访问数据库，这就是缓存穿透。缓存透带来的问题是，当有大量请求查询数据库不存在的数据时，就会给数据库带来压力，甚至会拖垮数据库。

可以使用布隆过滤器解决缓存穿透的问题。

1.4 hash值存储计算

散列函数的输入和输出并不是唯一的对应关系，如果两个散列值相同，两个输入值是相同的，也可能不是不同的。被称为hash碰撞。

public class Hset {public static void main(String[] args) {Set<Integer> st=new HashSet<>();int hcode=0;for(int k=0;k<200000;k++){hcode=new Object().hashCode();if(st.contains(hcode)){System.out.println("hash冲突:"+k);}st.add(hcode);}}

结果

 1.5 使用过滤器的步骤

1.初始化bitmap

默认为长度为m的值为0的bit位数组。

2.添加占坑位

为了尽量地址不发生冲突，会使用多个hash函数对key进行运算，算得一个下标索引值，然后对位数组长度进行取模运算得到一个位置，每个hash函数都会算得一个不同的位置，再把位数组的这个几个位置都设置为1，完成add操作。即 对字符串进行多次hash（key）-》取模运算-得到坑位。

3.判断是否存在

查询时，先把这个key通过相同的多个hash函数进行运算，查看对应的位置是否为1；只要有一个位为0，那么说明布隆过滤器中的这个key不存在。如果这几个位置全都是1，那么说明可能存在。