布隆过滤器

什么是布隆过滤器

  布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。

实现思想：
  对写入的数据做 H 次 hash 运算定位到数组中的位置，同时将数据改为 1。当有数据查询时也是同样的方式定位到数组中。比如二进制数组长度为10，插入元素A，对A第一次hash过对10取模为1，第二次取模为5，那么将1、5处的值修改为1。当判断A是否存在时，按照写入的计算方式，计算如果值都为1，则A存在，否则A不存在。

public class BloomFilterTest {
    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        int capacity = 10000000;
        BloomFilter<Integer> integerBloomFilter = BloomFilter.create(Funnels.integerFunnel(), capacity, 0.01);
        for (int i = 0; i < capacity; i++) {
            integerBloomFilter.put(i);
        }

        System.out.println(integerBloomFilter.mightContain(99992));
        long end = System.currentTimeMillis();
        System.out.println(end-start);
    }
}

google 的guava的实现：构造方法中有两个比较重要的参数，一个是预计存放多少数据，一个是可以接受的误报率。guava 会通过你预计的数量以及误报率帮你计算出你应当会使用的数组大小 numBits 以及需要计算几次 hash 函数 numHashFunctions

场景

  针对缓存穿透的场景，可以在init的时候将需要缓存的数据放在布隆过滤器中。如果缓存没有命中，先用布隆过滤器判断是否存在，如果不存在，在请求数据库。因为bloomFilter是jdk自带的，只适用单机环境，集群下init数据最好放在redis -BizMap中(最大512M)。

缺点及改进

  布隆过滤器的缺点主要是有一定的误识别率和删除困难，错误识别率可以使用google工具来指定识别率，但是无法达到100%。
  目前我们知道布隆过滤器可以支持 add 和 isExist 操作，那么 delete 操作可以么，答案是不可以，例如上图中的 bit 位 4 被两个值共同覆盖的话，一旦你删除其中一个值例如 “tencent” 而将其置位 0，那么下次判断另一个值例如 “baidu” 是否存在的话，会直接返回 false，而实际上你并没有删除它。
  如何解决这个问题，答案是计数删除。但是计数删除需要存储一个数值，而不是原先的 bit 位，会增大占用的内存大小。这样的话，增加一个值就是将对应索引槽上存储的值加一，删除则是减一，判断是否存在则是看值是否大于0。