最近有个朋友问了我这样一个面试题：现在数据量非常大，假设都是int类型。现在我给你一个数字，你需要告诉我它是否存在（尽可能高效）。需求其实很明确，就是判断一条数据是否存在。但是这里还有一个更重要的前提：非常大的数据。忽略常规实现的这个条件，首先想到的解决方案是什么？我想大部分人都会想到用HashMap来存储数据，因为它的写入和查询效率都比较高。有相应的API来编写和判断一个元素是否存在，所以实现起来比较简单。为此，我写了一个单体测试，使用HashSet存储数据（底层也是HashMap）；同时，为了后面的对比，把堆内存写死了：-Xms64m-Xmx64m-XX:+PrintHeapAtGC-XX:+HeapDumpOnOutOfMemoryError为了调试方便GC日志打印，以及内存溢出后Dump内存添加：@TestpublicvoidhashMapTest(){longstar=System.currentTimeMillis();Sethashset=newHashSet<>(100);for(inti=0;i<100;i++){hashset.add(i);}Assert.assertTrue(hashset.contains(1));Assert.assertTrue(hashset.contains(2));Assert.assertTrue(hashset.contains(3));longend=System.currentTimeMillis();System.out.println("执行时间："+(end-star));}当我只写入100条数据时，没有问题。还是在此基础上，尝试写入1000W的数据：执行完立即内存溢出：可见，在内存有限的情况下，我们不能使用该方法。实际情况也是如此；既然要判断某条数据是否存在于集合中，那么考虑的算法效率和准确率就一定是将所有数据加载到内存中。布隆过滤器就是基于上面分析的条件。要实现这个需求，最需要解决的就是如何将庞大的数据加载到内存中。而我们是不是可以换个思路，因为只需要判断数据是否存在，不需要去查询数据，所以也没有必要在里面存储真正的数据。伟大的科学家帮助我们想到了这样的需求。BurtonHowardBloom在1970年提出了一种叫做布隆过滤器（中文译名：布隆过滤器）的算法，主要用来解决一个元素是否在集合中，但它的优点是只需要占用很小的内存空间，具有很高的查询效率。所以它非常适合这种情况。BloomFilter的原理下面来分析一下它的实现原理。官方的说法是：它是一个长二进制向量，结合Hash函数存储和实现。听起来比较绕口，但是通过一张图更容易理解：如上图所示：首先需要初始化一个二进制数组，长度设置为L（图中为8），初始值为all0、写入A1=1000的数据时，需要进行H次Hash函数运算（这里为2次）；有点类似于HashMap，计算出来的HashCode取L取模后，定位到0和2，位置值设为1。同理计算A2=2000，4和7位置设置为1。当有一个B1=1000需要判断是否存在时，它也进行两次Hash运算定位0和2。此时它们的值都是1，所以认为B1=1000存在于集合中。当有B2=3000时也是如此。当第一次Hash位于index=4时，数组中的值为1，于是进行第二次Hash运算，结果位于index=5。该值为0，则认为B2=3000不存在于集合中。整个写入和查询的过程是这样的，总结起来就是：对写入的数据进行H次哈希运算，定位到数组中的位置，同时将数据变为1。当有数据查询时，同样定位到数组中。一旦其中之一为0，则认为该数据肯定不存在于集合中，否则该数据可能存在于集合中。所以，布隆过滤有如下特点：只要返回的数据不存在，就一定不存在。返回的数据存在，但可能性很大。同时，里面的数据也无法清除。***点你应该能看懂，重点解释2点和3点。为什么可以返回已有数据？这其实类似于HashMap。要在有限的数组长度内存储大量的数据，即使是最先进的Hash算法也会产生冲突，所以有可能两个完全不同的数据A和B会位于完全相同的位置。这时候用B来查询，自然是误报了。删除数据也是如此。当我删除B的数据时，其实就相当于删除了A的数据，同样会造成后续的误报。基于上述Hash冲突的前提，BloomFilter存在一定的误报率，这与Hash算法的个数H和数组长度L有关。自己实现一个布隆过滤算法其实很简单，也不难理解，所以用Java实现了一个简单的原型：首先初始化一个int数组。写入数据时，进行3次Hash运算，同时将对应位置置1。查询时同样进行3次Hash运算，得到对应的值。一旦该值为0，则认为该数据不存在。代码如下：publicclassBloomFilters{/***数组长度*/privateintarraySize;/***数组*/privateint[]array;publicBloomFilters(intarraySize){this.arraySize=arraySize;array=newint[arraySize];}/***输入数据*@paramkey*/publicvoidadd(Stringkey){intfirst=hashcode_1(key);intsecond=hashcode_2(key);intthird=hashcode_3(key);array[first%arraySize]=1;array[second%arraySize]=1;array[third%arraySize]=1;}/***判定数据是否存在于*@paramkey*@return*/publicbooleancheck(Stringkey){intfirst=hashcode_1(key);intsecond=hashcode_2(key);intthird=hashcode_3(键);intfirstIndex=array[first%arraySize];if(firstIndex==0){returnfalse;}intsecondIndex=array[second%arraySize];if(secondIndex==0){returnfalse;}intthirdIndex=array[third%arraySize];if(thirdIndex==0){returnfalse;}returntrue;}/***哈希算法1*@paramkey*@return*/privateinthashcode_1(Stringkey){inthash=0;inti;for(i=0;i>7;hash+=hash<<3;hash^=hash>>17;hash+=hash<<5;returnMath.abs(hash);}/***哈希算法3*@paramkey*@return*/privateinthashcode_3(Stringkey){inthash,i;for(hash=0,i=0;i>6);}哈希+=(哈希<<3);哈希^=(哈希>>11);哈希+=(哈希<<15);returnMath.abs(哈希);}}实现逻辑其实和上面描述的一样我们来测试一下，同样的参数：-Xms64m-Xmx64m-XX:+PrintHeapAtGC@TestpublicvoidbloomFilterTest(){longstar=System.currentTimeMillis();BloomFiltersbloomFilters=newBloomFilters(10000000);for(inti=0;i<10000000;i++){bloomFilters.add(i+"");}Assert.assertTrue(bloomFilters.check(1+""));Assert.assertTrue(bloomFilters.check(2+""));Assert.assertTrue(bloomFilters.check(3+""));Assert.assertTrue(bloomFilters.check(999999+""));Assert.assertFalse(bloomFilters.check(400230340+""));longend=System.currentTimeMillis();System.out.println("执行时间："+(end-star));}执行结果如下：写入1000W数据只用了3秒，判断准确。当我将数组的长度减少到100W时，出现了误报。数字400230340显然不在集合中，但它返回存在。这也反映了布隆过滤器的误报率。我们增加数组长度和Hash计算次数来降低误报率，但是相应的CPU和内存消耗会增加；这需要根据业务需求进行权衡。Guava实现的方式虽然只是实现了功能，但是也满足了大量的数据。但是观察GC日志很频繁，老年代也用了90%，接近崩溃的边缘。一般来说，内存利用率不好。其实这个算法在GoogleGuava库中也有实现。我们来看看业界权威的实现：-Xms64m-Xmx64m-XX:+PrintHeapAtGC@TestpublicvoidguavaTest(){longstar=System.currentTimeMillis();BloomFilterfilter=BloomFilter。创建(Funnels.integerFunnel(),10000000,0.01);for(inti=0;i<10000000;i++){filter.put(i);}Assert.assertTrue(filter.mightContain(1));Assert.assertTrue(filter.mightContain(2));Assert.assertTrue(filter.mightContain(3));Assert.assertFalse(filter.mightContain(10000000));longend=System.currentTimeMillis();System.out.println("执行时间："+(end-star));}也写了1000W的数据，执行没有问题。观察GC日志会发现没有fullGC，老年代的使用率很低。和前面的相比，这里明显好很多，可以写入更多的数据。我们来看看Guava是如何实现的？构造方法中有两个重要的参数，一个是期望存储多少数据，另一个是可接受的误报率。我这里的测试demo分别是1000W和0.01。Guava会根据你的预期数量和误报率，帮你计算出你应该使用的数组大小numBits和你需要计算几次的Hash函数numHashFunctions。该算法的计算规则可以参考维基百科。putwrite函数中实际存储数据的put函数如下：按照murmur3_128的方法，生成一个长度为128位的byte[]。分别取高低8位为两个Hash值。然后根据初始化时执行Hash的次数进行Hash运算。bitsChanged|=bits.set((combinedHash&Long.MAX_VALUE)%bitSize);其实也是Hash取模得到索引赋值1，关键点是bits.set()方法。set方法是BitArray中的一个函数，BitArray是真正存储数据的底层数据结构，使用一个long[]data来存储数据。所以set()也是对这个数据进行处理：在set之前，通过get()判断set中是否存在数据，如果存在则直接返回，通知客户端写入失败。下一步是通过按位运算进行按位或赋值。get()方法的计算逻辑和set类似，只要判断为0，就直接返回值存在。mightContain函数前面几步的逻辑类似，只是调用了get()方法判断元素是否存在。综上所述，布隆过滤的应用还是蛮多的，比如数据库、爬虫、防缓存崩溃等。尤其是当你需要在某个数据不存在的情况下准确知道该做什么时，它非常适合布隆过滤。请在此处参考此示例代码：https://github.com/crossoverJie/JCSprout
