如何快速检查元素是否存在？

大家好，我是指北君。,如标题一样，我们今天看一下一个经常听到，可能没用到的技术。,布隆过滤器是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。,基本概念,当需要判断某个元素是否在某个数据集中时，一般会怎么做？,将数据集封装成集合，比如List、Set等,通过集合提供的API判断该元素是否存在于集合,这样的实现比较简单，同时通过现有的JDK都能很快达到目的，但是设想一下，如果上面说到的集合数据量非常的大，这样不仅会耗费较大的存储空间，同时 在集合中检索元素的时间复杂度也会随之增加。那么有没比较好的方法去实现判断元素是否存在这样的情形呢？,也就是布隆过滤器。,通过一系列的Hash函数将元素映射到一个位阵列（Bit Array）中的多个点位上，判断元素是否存在，则是判断所有点位是不是都为1。然而，位阵列上都为1并不一定能够保证该元素一定存在，也有可能是其他元素Hash后落在了该点位上，这就是布隆过滤器的误判。,因此通过布隆过滤器我们可以确定：,应用场景,优缺点,相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。,布隆过滤器存储空间和插入/查询时间都是常数。,Hash函数相互之间没有关系，方便由硬件并行实现。,布隆过滤器不需要存储元素本身，对保密要求非常严格的场合有优势。,布隆过滤器可以表示全集，其它任何数据结构都不能。,元素存在的误判,一般情况下不支持元素（位阵列）的删除,实现原理,,核心其实是元素如何存储？如何判断元素是否存在？核心方法就两个，一个“存”一个检查，里面涉及到了算法相关知识，感兴趣可以深入研究下其实现原理与思想。,我们可以简单第理解其实现原理？比如现在有一个容器，我们定义为String[] bitArray = new String[26]作为位阵列， 现在有一堆由小写英文组成的元素，我们假定Hash算法为a-z到1~26的映射。,为什么判断元素一定不在集合中呢？很显然，如果一个元素存在，则该元素hash后的bit数组必须全部都是1，反之则不存在,示例,流程很简单：,BloomFilter虽然看起来简单，但是其内部的实现包含了很多的数学与算法知识，我们只是通过其简单的API就能各种复杂的功能。关于如何将目前说到的这些在具体的项目中进行实践与集成 后面会来介绍，首先我们能够先了解一些技术一起能解决上面问题，理解了原理与目的，使用也就不是难事。,