13-布隆过滤器

布隆过滤器

• 普通过滤器
  • 若数据集是有一定范围，则可以制定判断是否在该范围内（bitMap标记、大小于号范围判定），从而判定是否在数据集中，bitMap标记性能差，大小与号编程复杂
  • 若数据集是非数字，将所有数据的某个属性都放在一个集合中（hyperloglog、set、list）中，若集合中有则说明该元素包含在在数据集中，hyperloglog有一定不可控的误差，其他性能差、内存开销大
• 布隆过滤器：利用极少内存，快速的判断是否在数据集中，有一定可控的错误率，但是能保证在数据集中的数据一定能准确判定出在，不再数据集中的数据不一定准确判定出是否在（存在哈希碰撞）

原理

实现思路

过滤器存储位置	思路	优点	缺点
本地（程序内）	使用BitSet类进行位操作	速度快	容量受限，多应用过滤器同步问题
单机Redis	基于bitmap实现，利用pipeline、setbit、getbit命令实现	解决了多应用过滤器同步问题	速度较慢，容量受限512MB
集群Redis	将单个超大的过滤器分片成多个bitmap实现	解决容量受限问题	速度较慢，编码复杂

工具类中的过滤器

使用谷歌的工具类中的过滤器，仅是本地过滤器，需要引入相关jar包，需要引入相关jar包，从maven官网中查找Guava并下载

static class Person {
  int id;
  String name;

  public Person(int id, String name) {
    this.id = id;
    this.name = name;
  }
}

public static void main(String[] args) {
  /**
   *第一个参数是Funnel接口的实例：
   *    非复合类型可以直接使用Funnels静态方法中获取提供好的Funnel接口实例
   *      比如：Funnels.stringFunnel(Charset.defaultCharset)  //字符串需指定字符编码
   *    复合类型需要手动实现这个接口，并重写funnel()方法
   *      作用：是将具体的对象类型分解为原生字段值
   *          第一个参数是源对象，用于拆解的原材料，即获取属性
   *          第二个参数是分解器，调用分解器的putXxx()方法进行分解
   * 第二个参数是预存的数据数量
   * 第三个参数是容忍的错误率
   */
  BloomFilter<Person> filter = BloomFilter.create(new Funnel<Person>() {
    @Override
    public void funnel(Person person, PrimitiveSink primitiveSink) {
      primitiveSink
          .putInt(person.id)
          .putString(person.name, Charset.defaultCharset());  //字符串需指定字符编码
    }
  }, 100, 0.001);  //指定预存100个，容忍错误率为0.001

  for (int i = 0; i < 100; i++) {
    filter.put(new Person(i, String.valueOf(i))); //预备数据
  }

  boolean one = filter.mightContain(new Person(-1, String.valueOf(-1)));  //查询数据
  System.out.println(one);
  boolean two = filter.mightContain(new Person(1, String.valueOf(1)));  //查询数据
  System.out.println(two);
}