从微信订阅号 “IT老哥” 摘抄记录而来
原文: https://mp.weixin.qq.com/s?__biz=MzU0NDA2MjY5Ng==&mid=100006094&idx=1&sn=bbc8e698a7b08c4f310e10a3ffd63e3c&chksm=7b00b5494c773c5fd7c06f5e166f20ea720f0c483bfce1b22f70f5613239c1242543f28c805e&mpshare=1&scene=1&srcid=1021gbVvug6heD3kx8H8h4WI&sharer_sharetime=1603246019870&sharer_shareid=56c3f6ec391692c417e3832de28177ce&key=9853f5dfd5cd58d61241e2a6d8359cebb7f0af516d7809449e76b4c8a89c91b2d7aa2f4beb950e7ece4c88b989f8f374e5264918b5e434978bd7811b770119d5fd4b7a0b61d38ef16a50de8a979afacedaf4e655db051be3b17fafbb1726405aed80f8d35b42a8b96937949791b1386f281fae505a8ed076990738e16ee404c5&ascene=1&uin=MTAwMjkyMTA4MA%3D%3D&devicetype=Windows+10+x64&version=6300002f&lang=zh_CN&exportkey=Acfs4MxuZSgYBenjkBy9PQc%3D&pass_ticket=xn2WAU3eUCM077NVeGvqCo%2FMXFxNiz1WHcPeD1B2fqXIwDVOP0GHJdcTgw1TzDQI&wx_header=0

怎么使？
一、引入Guava pom配置

<dependency>
  <groupId>com.google.guava</groupId>
  <artifactId>guava</artifactId>
  <version>29.0-jre</version>
</dependency>

二、代码实现

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;

public class BloomFilterCase {

  /**
   * 预计要插入多少数据
   */
  private static int size = 1000000;

  /**
   * 期望的误判率
   */
  private static double fpp = 0.01;

  /**
   * 布隆过滤器
   */
  private static BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, fpp);


  public static void main(String[] args) {
    // 插入10万样本数据
    for (int i = 0; i < size; i++) {
      bloomFilter.put(i);
    }

    // 用另外十万测试数据，测试误判率
    int count = 0;
    for (int i = size; i < size + 100000; i++) {
      if (bloomFilter.mightContain(i)) {
        count++;
        System.out.println(i + "误判了");
      }
    }
    System.out.println("总共的误判数:" + count);
  }
}

运行结果：

image.png

10万数据里有947个误判，约等于0.01%，也就是我们代码里设置的误判率：fpp = 0.01。

深入分析代码

核心BloomFilter.create方法

@VisibleForTesting
  static <T> BloomFilter<T> create(
      Funnel<? super T> funnel, long expectedInsertions, double fpp, Strategy strategy) {
    。。。。
}

这里有四个参数：

funnel：数据类型(一般是调用Funnels工具类中的)

expectedInsertions：期望插入的值的个数

fpp：误判率(默认值为0.03)

strategy：哈希算法

我们重点讲一下fpp参数

fpp误判率
情景一：fpp = 0.01
误判个数：947

image.png

占内存大小：9585058位数

image.png

情景二：fpp = 0.03（默认参数）
误判个数：3033

image.png

占内存大小：7298440位数

image.png

情景总结

误判率可以通过fpp参数进行调节

fpp越小，需要的内存空间就越大：0.01需要900多万位数，0.03需要700多万位数。

fpp越小，集合添加数据时，就需要更多的hash函数运算更多的hash值，去存储到对应的数组下标里。（忘了去看上面的布隆过滤存入数据的过程）

上面的numBits，表示存一百万个int类型数字，需要的位数为7298440，700多万位。理论上存一百万个数，一个int是4字节32位，需要481000000=3200万位。如果使用HashMap去存，按HashMap50%的存储效率，需要6400万位。可以看出BloomFilter的存储空间很小，只有HashMap的1/10左右

上面的numHashFunctions表示需要几个hash函数运算，去映射不同的下标存这些数字是否存在（0 or 1）。

解决Redis缓存雪崩

上面使用Guava实现的布隆过滤器是把数据放在了本地内存中。分布式的场景中就不合适了，无法共享内存。

我们还可以用Redis来实现布隆过滤器，这里使用Redis封装好的客户端工具Redisson。

其底层是使用数据结构bitMap，大家就把它理解成上面说的二进制结构，由于篇幅原因，bitmap不在这篇文章里讲，我们之后写一篇文章介绍。

代码实现

<dependency>
  <groupId>org.redisson</groupId>
  <artifactId>redisson-spring-boot-starter</artifactId>
  <version>3.13.4</version>
</dependency>


public class RedissonBloomFilter {

  public static void main(String[] args) {
    Config config = new Config();
    config.useSingleServer().setAddress("redis://127.0.0.1:6379");
    config.useSingleServer().setPassword("1234");
    //构造Redisson
    RedissonClient redisson = Redisson.create(config);

    RBloomFilter<String> bloomFilter = redisson.getBloomFilter("phoneList");
    //初始化布隆过滤器：预计元素为100000000L,误差率为3%
    bloomFilter.tryInit(100000000L,0.03);
    //将号码10086插入到布隆过滤器中
    bloomFilter.add("10086");

    //判断下面号码是否在布隆过滤器中
    //输出false
    System.out.println(bloomFilter.contains("123456"));
    //输出true
    System.out.println(bloomFilter.contains("10086"));
  }
}