布隆过滤器实现

布隆过滤器就是利用的 bit

整体思想就是 
1个2进制的  bit数组
和多个不同算法的hash
怎么整呢
就是比如 
我有16个bit相当于2个字节  因为1个字节是8位 这个肯定大家都知道
因为bit只能是 0 或者1   在因为布隆过滤器的思想就是判断存过的key是否存在
所以就简单了 就是整一堆2进制bit数组

0 0 0 0    0 0 0 0    这是8位bit    数组肯定有下标 
如果我存的key是  “中国”
上面讲了有多个hash算法 那既然是多个hash算法对 “中国”  hash肯定就得出来的数不一样
比如 hash1算法（中国） =2      hash2算法（中国）=5 
那么存的结果就是
0 0 0 1    0 0 1 0  第二位和第五位就都变成1了  ps我不确定bit数组下标从0开始还是1开始所以就 假设他从1开始
所以在判断中国存在不存在的时候 就根据两次hash算法去对应的下标看是不是1， 如果是0肯定就没有 
如果都是1 也不一定 就有 。   为什么这么说 因为多个hash算法就是为了避免hash碰撞，但是我们学过hashmap都了解hash是肯定会碰撞的 所以 遇到  其他的key刚好和你碰撞了 就会进行误判了  所以 布隆过滤器主要是解决判断这个这个key是否存储过，如果多个hash的结果只要有一个bit位置是0那么这个key肯定就没有布隆过滤器这个可以做的非常好   但是你得业务要是 对误判可以接受那你可以判断他是否有。下面给出本地实现和分布式实现。


ps 布隆过滤器最大的缺点就是 没法删除单独的key为什么 因为你删除了 你肯定就是把bit 设置成0 但是如果hash碰撞了 你设置成0了  就会影响其他的key了所以不能删除
在一个就是误判了 这个是我们可以预料到的。

1.本地布隆过滤器

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>20.0</version>
</dependency>


int expectedInsertions = 1000000; //预期插入多少个需要判断的key
double fpp = 0.01; //错误率 底层估计是 根据错误率去算需要多少位 肯定错误率越低占用内存空间越大，估计还和hash算法有关
BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charset.defaultCharset()), expectedInsertions, fpp);

//存数据
bloomFilter.put("hello");
bloomFilter.put("world");

//判断是否存过数据
bloomFilter.mightContain("hello"); // true
bloomFilter.mightContain("world"); // true
bloomFilter.mightContain("test"); // false

2.分布式环境布隆过滤器

redission的实现
// 获取布隆过滤器对象
RBloomFilter<String> bloomFilter = redisson.getBloomFilter("bloom-filter");
// 初始化布隆过滤器，设置预计元素数量和误判率
bloomFilter.tryInit(10000, 0.03);
// 添加元素
bloomFilter.add("hello");
bloomFilter.add("world");

// 判断元素是否存在
System.out.println(bloomFilter.contains("hello"));
System.out.println(bloomFilter.contains("redis"));

// 清空过滤器
bloomFilter.delete();