如何快速判断一个元素是否存在？

大家好，我是北军。正如标题所说，让我们来看看一个经常听到但今天可能不会用到的技术。GuavaBloomFilter布隆过滤器是一个长二进制向量和一系列随机映射函数。布隆过滤器可用于检索元素是否在集合中。它的优点是空间效率和查询时间都比一般算法好很多，缺点是存在一定的误识别率和删除难度。基本概念当需要判断某个元素是否在某个数据集中时，一般会怎么做？将数据集封装成一个集合比较简单，比如List、Set等，通过集合提供的API来判断元素是否存在于集合中。同时，现有的JDK可以快速达到目的，但是试想一下，如果上面说的采集数据量非常大，不仅会消耗大量的存储空间，还会增加获取元素的时间复杂度集合。那么判断元素是否存在的情况有没有更好的实现方式呢？那就是布隆过滤器。通过一系列的Hash函数，将元素映射到一个位数组（BitArray）中的多个点，判断一个元素是否存在，就是判断所有的点是否都为1。但是位数组中并不全为1必然保证该元素存在，也有可能其他元素在Hash后落在这一点上，就是Bloomfilter的误判。因此，通过布隆过滤器，我们可以判断元素可能在集合中，元素一定不在集合中。应用场景网络爬虫忽略已经确定的URL路径。通过设置过滤器垃圾邮件集合中重复元素的识别，可以有效地判断该元素不在集合中并加以阻止。数据缓存时缓存穿透问题的优缺点优缺点与其他数据结构相比，布隆过滤器在空间和时间上具有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数。哈希函数之间没有任何关系，因此可以用硬件并行实现。布隆过滤器不需要存储元素本身，这在保密性要求非常严格的场合具有优势。布隆过滤器可以表示集成，其他数据结构都做不到。缺点元素存在的误判一般不支持删除元素（位数组）。实现原理的核心其实就是如何存储元素？如何检查元素是否存在？核心方法只有两个，一个是“保存”，一个是检查，涉及到算法相关的知识。有兴趣的可以深入研究其实现原理和思路。put将元素放入过滤器，但不放入存储空间//位数组，可以通过redis实现分布式布隆过滤器longhash64=Hashing.murmur3_128().hashObject(object,funnel).asLong();//通过funnel将object转化为基本类型并计算64位hashinthash1=(int)hash64;//取低32位inthash2=(int)(hash64>>>32);//取高32位booleanbitsChanged=false;//for(inti=1;i<=numHashFunctions;++i){intcombinedHash=hash1+i*hash2;如果(combinedHash<0){combinedHash=~combinedHash;}bitsChanged|=bits.set((long)combinedHash%bitSize);}返回bitsChanged;}mightContain和put类似，计算过程一样，不同的是值判断publicbooleanmightContain(@ParametricNullnessT对象，漏斗funnel,intnumHashFunctions,LockFreeBitArraybits){longbitSize=bits.位大小（）；longhash64=散列。杂音3_128()。hashObject（对象，漏斗）。只要（）;inthash1=(int)hash64;inthash2=(int)(hash64>>>32);for(inti=1;i<=numHashFunctions;++i){intcombinedHash=hash1+i*hash2;如果(combinedHash<0){combinedHash=~combinedHash;}if(!bits.get((long)combinedHash%bitSize)){returnfalse;}}返回真；是不是可以简单的了解一下它的实现原理呢？比如现在有一个容器，我们把它定义为String[]bitArray=newString[26]作为一个位数组，现在有一堆由小写英文组成的元素，我们假设Hash算法是从a-z到1~26现在有一个元素abc，hash后为1110000000...，存入bitArray：1110000000...现在有一个元素cde，hash后为0011100000...，存入bitArray：1111100000...现在多了一个元素ade，经过hash后，也是100110000...，很明显这个元素是存在的，这就是FFP判断这??个元素一定不在集合中的原因？显然，如果一个元素存在，则该元素hash后的位数组必须全为1，否则没有例子),10000,0.2);Listids=newArrayList<>();IntStream.rangeClosed(1,10000).forEach(index->??{Stringid=UUID.randomUUID().toString();ids.add(id);filter.put(id);});ids.forEach(id->{//通常都会失败，但20%会返回trueSystem.out.println(id+":"+filter.mightContain(id+1));});}过程很简单：根据配置构建一个BloomFilter对象，使用put方法，初始化数据到filter，使用mightContain方法判断元素是否存在结束语BloomFilter虽然看起来简单，但是其内部的实现包含了大量的数学和算法知识，我们可以通过其简单的API来执行各种复杂的功能。如何在具体项目中实践和融合上述内容，后面会介绍。首先，我们可以先了解一些可以一起解决上述问题的技术。了解了原理和用途之后，使用起来就不难了。