在之前的Java多线程爬虫和分布式爬虫架构探索的文章中，我们使用了JDK自带的Set集合去重URL，貌似效果不错，但是这种方法有一个致命的缺陷，那就是随着收集的URL越来越多，你需要的内存会越来越大，最终会导致你的内存崩溃。那么我们有没有不用数据库的解决方案呢？还记得上一篇我们提到的布隆过滤器吗？可以完美解决这个问题。布隆过滤器有什么特别之处？什么？接下来，让我们了解布隆过滤器。什么是BloomfilterBloomfilter是一种数据结构，一种巧妙的概率数据结构，它是由一个叫Bloom的人在1970年提出的。它实际上是由一个很长的二进制向量和一系列随机映射函数组成的，有点类似于哈希表，但是和哈希表相比，Bloomfilter效率更高，占用空间更小。布隆过滤器有一个缺点，它有一定的错误识别。率和去除困难。Bloomfilters只能告诉你一个元素一定不能存在或者可能存在于集合中，所以Bloomfilters常用于处理能够容忍判断错误的业务，比如爬虫URL去重。BloomFilter的原理在说BloomFilter的原理之前，我们先来回顾一下哈希表。在上一篇文章中，我们使用Set来对URL进行去重。再来看看存储模型SetofSeturl去重URL经过hash函数后存储在一个数组中，查询的时候效率也很高。但是，由于URL存储在数组中，随着URL数量的增加，所需的数组变得越来越大，这意味着你需要更多的内存。例如，如果我们收集数亿个URL，那么可能需要数百GB的内存。这是不允许的，因为内存是非常昂贵的，所以这是url去重的关键。不可取，占用内存少的布隆过滤器是不错的选择。布隆过滤器本质上由长度为m的位向量或位列表（仅包含0或1位值的列表）组成，最初所有值都设置为0，如下所示。因为布隆过滤器底层是一个位数组，也就是说这个数组只有0和1两个值。像哈希表一样，我们通过K个函数把URL映射到位数组中，改变值对应指向的Bit数组to变为1。我们以/nba/2492297.html为例，如下图所示。Bloomfilter/nba/2492297.html通过三个hash函数映射到1、4、9的位置，这三个位数组的值就变成了1，我们再存入一个/nba/2492298。html，位数组变成如下：Bloomfilter/nba/2492298.html被映射到位置0、4、11，所以位数组上5个位置的值为1，应该是有6个值的1，但是因为位置4重复了，所以会被覆盖掉。布隆过滤器是如何判断某个值一定不存在或者可能存在的呢？通过hash函数判断映射到对应数组的值，如果都是1，说明可能存在。如果一个不为1，则表示它一定不存在。肯定不存在很好理解，但是当它们都为1的时候，为什么说可能存在呢？这个和哈希表一样，哈希函数会产生哈希冲突，也就是说两个不同的值经过哈希函数后会得到相同的一个数组索引，布隆过滤器也是一样的。下面以判断/nba/2492299.html是否被采集为例。哈希函数映射到的位数组上的位置如下图所示：Bloomfilter/nba/2492299.html映射到4、9、11，这几个位置的值都是1，所以Bloomfilter认为/nba/2492299.html已经采集了，但实际上并没有采集到，这说明Bloomfilter存在设备误判，这也是我们业务允许的。布隆过滤器的误判率与位数组的大小和哈希函数的个数有关。如果位数组太小，哈希函数太多，位数组的值很快就会变成1，属于误判。如果位数组太大，会浪费更多的内存，所以需要平衡位数组的大小和哈希函数的数量。如何平衡这两者的关系不是我们本文的重点。我们已经了解了布隆过滤器的原理。为了加深对Bloomfilter的理解，我们使用Java实现了一个简单版的Bloomfilter。代码如下：publicclassSimpleBloomFilterTest{//位数组的大小privatestaticfinalintDEFAULT_SIZE=1000;//privatestaticfinalint[]seeds=newint[]{7,31,61,}用于产生三种不同的哈希函数；//位数组privateBitSetbits=newBitSet(DEFAULT_SIZE)；//数组privateSimpleHash，用于存储哈希函数[]func=newSimpleHash[seeds.length];publicstaticvoidmain(String[]args){Si??mpleBloomFilterTestfilter=newSimpleBloomFilterTest();filter.add("https://voice.hupu.com/nba/2492440.html");过滤器。add("https://voice.hupu.com/nba/2492437.html");filter.add("https://voice.hupu.com/nba/2492439.html");System.out.println(filter.contains("https://voice.hupu.com/nba/2492440.html"));System.out.println(filter.contains("https://voice.hupu.com/nba/249244.html")"));}publicSimpleBloomFilterTest(){for(inti=0;i
