布隆过滤器

原创文章，转载请注明原文章地址，谢谢！

缓存穿透

• 缓存存在

  
  

• 缓存不存在，数据库存在
  存在两种情况：key过期；新增缓存

  
  
• 数据库不存在，缓存穿透

要避免持续从数据库查不存在的数据（保护数据库），怎么做？
方案：缓存空数据。但是如果每次请求的都是不同的key，该方案依然不行，且redis会占用大量内存。
缓存穿透：不断请求大量不存在的值

面试题：如何在海量元素中（例如10亿无序、不定长、不重复）快速判断一个元素是否存在？

如何减少哈希碰撞？
方案：增加位图长度。消耗内存空间，不能无限增加；优化哈希算法（多次计算）

布隆过滤器

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

• 如果布隆过滤器判断元素在集合中存在，不一定存在；
• 如果布隆过滤器判断不存在，一定不存在。
• 如果元素存在，布隆过滤器一定判断存在；
• 如果元素不存在，布隆过滤器可能判断存在。

布隆过滤器的本质

• 位数组（二进制向量）
• 一系列随机映射函数

BloomFilter原理

布隆过滤器的原理是，当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个位数组中的K个点，把它们置为1。检索时，只要看看这些点是不是都是1就（大约）知道集合中有没有它了，果这些点有任何一个0，则被检元素一定不在，如果都是1，则被检元素很可能在。Bloom Filter跟单哈希函数Bit-Map不同之处在于，Bloom Filter使用了k个哈希函数，每个字符串跟k个bit对应，从而降低了冲突的概率。

bloom filter之所以能做到在时间和空间上的效率比较高，是因为牺牲了判断的准确率、删除的便利性。

• 存在误判，可能要查到的元素并没有在容器中，但是hash之后得到的k个位置上值都是1。如果bloom filter中存储的是黑名单，那么可以通过建立一个白名单来存储可能会误判的元素。
• 删除困难。一个放入容器的元素映射到bit数组的k个位置上是1，删除的时候不能简单的直接置为0，可能会影响其他元素的判断。可以采用Counting Bloom Filter

public class BloomFilterDemo {

    private static final int insertions = 1000000;

    public static void main(String[] args) {
        //初始化一个存储String数据的布隆过滤器，初始化大小为100w
        BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), insertions);
        //用于存放所有实际存在的key，可以取出使用
        List<String> list = new ArrayList<>(insertions);
        //用于存放所有实际存在的key，判断key是否存在
        Set<String> set = new HashSet<>(insertions);
        //向三个容器初始化100w个随机且唯一的字符串
        for (int i = 0; i < insertions; i++) {
            String uuid = UUID.randomUUID().toString();
            bloomFilter.put(uuid);
            list.add(uuid);
            set.add(uuid);
        }
        //正确判断的次数
        int right = 0;
        //错误判断的次数
        int wrong = 0;
        for (int i = 0; i < 10000; i++) {
            //可以被100整除的时候，取一个存在的数。否则就随机生成一个UUID，0-10000之间，可以被100整除的数有100个
            String data = i % 100 == 0 ? list.get(i / 100) : UUID.randomUUID().toString();
            if (bloomFilter.mightContain(data)) {
                if (set.contains(data)) {
                    //判断存在实际存在的时候，命中
                    right++;
                    continue;
                }
                //判断存在实际不存在的时候，错误
                wrong++;
            }
        }
        NumberFormat percentFormat = NumberFormat.getPercentInstance();
        //最大小数位数
        percentFormat.setMaximumFractionDigits(2);
        float percent = (float) wrong / 9900;
        float bingo = (float) (9900 - wrong) / 9900;
        System.out.println("在100w个元素中，判断100个实际存在的元素，布隆过滤器认为存在的：" + right);
        System.out.println("在100w个元素中，判断9900个实际不存在的元素，误认为存在的：" + wrong + "，命中率：" +
                percentFormat.format(bingo) + "，误判率：" + percentFormat.format(percent));
    }
}

博客内容仅供自已学习以及学习过程的记录，如有侵权，请联系我删除，谢谢！