布隆过滤器

布隆过滤器（Bloom Filter）是 1970 年由布隆提出的，是一种非常节省空间的概率数据结构，运行速度快，占用内存小。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。主要用于判断一个元素是否在一个集合中。主要是解决大规模数据下不需要精确过滤的场景，如检查垃圾邮件地址，爬虫URL地址去重，解决缓存穿透问题等。

优点

• 存储空间和插入 / 查询时间都是常数O(k)
• 支持海量数据场景下高效率判断元素是否存在
• 存储空间小，不存储数据本身，而是存储hash结果取模运算后的位标记

缺点

• 无法删除，因为可能多个元素通过哈希后，可能会产生hash碰撞，映射到布隆过滤器的同一个位置。删除该位置后，可能影响其他元素
• 误判，由于存在hash碰撞，不同的元素经过哈希后可能映射到同一个位置，一旦产生碰撞，会被误判存在
• 碰撞概率，让随着元素越来越大，在容量限制下，布隆过滤器被使用的位置就会越来越多，误判的几率也会越来越大

特点

根据布隆过滤器的特点可以知道

• 判断如果某个元素存在，由于存在误判，这个元素不一定是存在的
• 判断如果某个元素不存在，那这个元素一定不存在

原理

结构

布隆过滤器底层就是一个二进制的位数组，在初始状态，所有位置的位都是0

添加

• 使用哈希函数对元素进行哈希计算得到索引值，将索引值对应的数组下标所在的值设置为1
• 如果是多个哈希函数则进行上述同样的操作

查询

• 对要查询的元素同样使用哈希函数进行计算，如果存在多个哈希函数则得到多个索引值
• 判断这些索引值对应的数组下标的值是否都为1，如果是，则判断这个元素为存在。如果这些下标的值只要有一个是0，那么判断这个元素为不存在

• <dependency>
      <groupId>com.example</groupId>
      <artifactId>damai-bloom-filter-framework</artifactId>
      <version>${revision}</version>
  </dependency>

• @Data
  @ConfigurationProperties(prefix = BloomFilterProperties.PREFIX)
  public class BloomFilterProperties {
  
      public static final String PREFIX = "bloom-filter";
      /**
      * 布隆过滤器名字
      */
      private String name;
      /**
      * 布隆过滤器的容量
      */
      private Long expectedInsertions = 20000L;
      /**
      * 布隆过滤器碰撞率
      */
      private Double falseProbability = 0.01D;
  }

• @EnableConfigurationProperties(BloomFilterProperties.class)
  public class BloomFilterAutoConfiguration {
      
      /**
       * 布隆过滤器
       */
      @Bean
      public BloomFilterHandler rBloomFilterUtil(RedissonClient redissonClient, BloomFilterProperties bloomFilterProperties) {
          return new BloomFilterHandler(redissonClient, bloomFilterProperties);
      }
  }

• public class BloomFilterHandler {
      
      private final RBloomFilter<String> cachePenetrationBloomFilter;
      
      public BloomFilterHandler(RedissonClient redissonClient, BloomFilterProperties bloomFilterProperties){
          RBloomFilter<String> cachePenetrationBloomFilter = redissonClient.getBloomFilter(bloomFilterProperties.getName());
          cachePenetrationBloomFilter.tryInit(bloomFilterProperties.getExpectedInsertions(), bloomFilterProperties.getFalseProbability());
          this.cachePenetrationBloomFilter = cachePenetrationBloomFilter;
      }
      
      public boolean add(String data) {
          return cachePenetrationBloomFilter.add(data);
      }
      
      public boolean contains(String data) {
          return cachePenetrationBloomFilter.contains(data);
      }
      
      public long getExpectedInsertions() {
          return cachePenetrationBloomFilter.getExpectedInsertions();
      }
      
      public double getFalseProbability() {
          return cachePenetrationBloomFilter.getFalseProbability();
      }
      
      public long getSize() {
          return cachePenetrationBloomFilter.getSize();
      }
      
      public int getHashIterations() {
          return cachePenetrationBloomFilter.getHashIterations();
      }
      
      public long count() {
          return cachePenetrationBloomFilter.count();
      }
  }