Java利用布隆过滤器实现快速检查元素是否存在

Java布隆过滤器检查元素是否存在 Java布隆过滤器 Java 检查元素是否存在 2022-11-13 18:11:19 541人浏览薄情痞子

Python 官方文档：入门教程 => 点击学习

摘要

目录Guava BloomFilter基本概念应用场景优缺点实现原理示例结束语Guava BloomFilter 布隆过滤器是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以

Guava BloomFilter

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

基本概念

当需要判断某个元素是否在某个数据集中时，一般会怎么做？

将数据集封装成集合，比如List、Set等
通过集合提供的api判断该元素是否存在于集合

这样的实现比较简单，同时通过现有的jdk都能很快达到目的，但是设想一下，如果上面说到的集合数据量非常的大，这样不仅会耗费较大的存储空间，同时在集合中检索元素的时间复杂度也会随之增加。那么有没比较好的方法去实现判断元素是否存在这样的情形呢？

也就是布隆过滤器。

通过一系列的Hash函数将元素映射到一个位阵列（Bit Array）中的多个点位上，判断元素是否存在，则是判断所有点位是不是都为1。然而，位阵列上都为1并不一定能够保证该元素一定存在，也有可能是其他元素Hash后落在了该点位上，这就是布隆过滤器的误判。

因此通过布隆过滤器我们可以确定：

元素可能在集合中
元素一定不在集合中

应用场景

网页爬虫时忽略已经判定的URL路径

邮箱通过设置过滤垃圾邮件

集合重复元素的判别，有效判断元素不在集合中

防止数据缓存时的缓存穿透问题

优缺点

优点

相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。
布隆过滤器存储空间和插入/查询时间都是常数。
Hash函数相互之间没有关系，方便由硬件并行实现。
布隆过滤器不需要存储元素本身，对保密要求非常严格的场合有优势。
布隆过滤器可以表示全集，其它任何数据结构都不能。

缺点

元素存在的误判
一般情况下不支持元素（位阵列）的删除

实现原理

核心其实是元素如何存储？如何判断元素是否存在？核心方法就两个，一个“存”一个检查，里面涉及到了算法相关知识，感兴趣可以深入研究下其实现原理与思想。

put 将元素放入过滤器中，但不是存储

        public <T> boolean put(@ParametricNullness T object, Funnel<? super T> funnel, int numHashFunctions, LockFreeBitArray bits) {
            long bitSize = bits.bitSize(); // 位数组，可以通过Redis来实现分布式的布隆过滤器
            long hash64 = Hashing.murmur3_128().hashObject(object, funnel).asLong(); //通过funnel将对象转换成基本类型并计算64位hash
            int hash1 = (int)hash64; // 取低32位
            int hash2 = (int)(hash64 >>> 32); // 取高32位
            boolean bitsChanged = false;
            // 
            for(int i = 1; i <= numHashFunctions; ++i) {
                int combinedHash = hash1 + i * hash2;
                if (combinedHash < 0) {
                    combinedHash = ~combinedHash;
                }

                bitsChanged |= bits.set((long)combinedHash % bitSize);
            }

            return bitsChanged;
        }

mightContain 与put相似，计算的过程相同，不同的是值的判断

        public <T> boolean mightContain(@ParametricNullness T object, Funnel<? super T> funnel, int numHashFunctions, LockFreeBitArray bits) {
            long bitSize = bits.bitSize();
            long hash64 = Hashing.murmur3_128().hashObject(object, funnel).asLong();
            int hash1 = (int)hash64;
            int hash2 = (int)(hash64 >>> 32);

            for(int i = 1; i <= numHashFunctions; ++i) {
                int combinedHash = hash1 + i * hash2;
                if (combinedHash < 0) {
                    combinedHash = ~combinedHash;
                }

                if (!bits.get((long)combinedHash % bitSize)) {
                    return false;
                }
            }

            return true;
        }

我们可以简单第理解其实现原理？比如现在有一个容器，我们定义为String[] bitArray = new String[26]作为位阵列，现在有一堆由小写英文组成的元素，我们假定Hash算法为a-z到1~26的映射。

现在有一个元素abc，hash后为1110000000...，保存到bitArray ：1110000000...
现在有一个元素cde, hash后为0011100000...，保存到bitArray ：1111100000...
现在又有一个新的元素ade，hash后同样为100110000...，很明显会认为该元素存在，这就是FFP

为什么判断元素一定不在集合中呢？很显然，如果一个元素存在，则该元素hash后的bit数组必须全部都是1，反之则不存在

示例

    @Test
    public void match(){
        BloomFilter filter = BloomFilter.create(Funnels.stringFunnel(Charset.defaultCharset()),10000,0.2);
        List<String> ids = new ArrayList<>();

        IntStream.rangeClosed(1,10000).forEach(index->{
            String id = UUID.randomUUID().toString();
            ids.add(id);
            filter.put( id );
        });

        ids.forEach(id->{
            // 正常情况下全部失败，但是会有 20%的返回true
            System.out.println( id + ":" + filter.mightContain( id+1 ));
        });
    }

流程很简单：