网页爬虫中使用到了什么数据结构？

一、引言

相信大家对网页爬虫一定不陌生，爬虫的工作原理是：

爬理：通过解析已经爬取页面中的网页链接，然后再爬取这些链接对应的网页。

但是重点是，同一个网页链接有可能被包含在多个页面中，这就会导致爬虫在爬取的过程中，重复爬取相同的网页。

那么如何避免这些重复的爬取呢？

Record已经爬取的网页链接（ URL）；
在爬取一个新的网页之前，拿新的网页的链接，在已经爬取的网页链接列表中搜索；
如果存在，那就说明这个网页已经被爬取过了；
如果不存在，那就说明这个网页还没有被爬取过，可以继续去爬取；
等爬取到这个网页之后，我们将这个网页的链接add到已经爬取的网页链接列表了。

二、怎么爬取网页链接？

2.1 对URL要进行的操作有哪些？

这个problem要处理的对象是网页链接，需要support的操作有两个：

添加一个URL
查询一个URL

In the meantime，在非功能性方面，

执行效率尽可能高
存储效率尽可能高

2.2 哪些数据结构可以满足上述要求？

首先我们need想想，

满足要求的数据结构的特点是什么？

快速地插入、查找数据

那么哪些数据结构有这种特点？

散列表、红黑树、跳表这些动态数据结构

但是需要注意的是，我们对内存也有要求。For example，我们用散列表来爬取10亿个web pages，

将10亿web pages存储到散列表中，大约需要多少内存？

假设一个 URL 的平均长度是 64 字节，那单纯存储这 10 亿个 URL，
需要大约 60GB 的内存空间。

因为散列表必须维持较小的装载因子，才能保证不会出现过多的散列冲突，导致操作的性能下降。
而且，用链表法解决冲突的散列表，还会存储链表指针。

所以，如果将这 10 亿个 URL 构建成散列表，那需要的内存空间会远大于 60GB，有可能会超过 100GB。

Of course，对于一个Google来说，
即便是 100GB 的内存要求，其实也不高，
我们can采用分治的思想，用多台机器（比如 20 台内存是 8GB 的机器）来存储这 10 亿网页链接。

时间复杂度只是表示执行时间随数据规模的变化趋势，并不能度量在特定的数据规模下，代码执行时间的多少。

2.3 如何优化DS？

如果时间复杂度中原来的系数是 10，现在能够通过优化，将系数降为 1，
那在时间复杂度没有变化的情况下，执行效率就提高了 10 倍。

如果我们用基于链表的方法解决冲突问题，散列表中存储的是 URL，那当查询的时候，通过哈希函数定位到某个链表之后，我们还需要依次比对每个链表中的 URL。

这个操作是比较耗时的，主要有两点原因。

一方面，链表中的结点在内存中不是连续存储的，所以不能一下子加载到 CPU 缓存中，没法很好地利用到 CPU 高速缓存，所以数据访问性能方面会打折扣。

另一方面，链表中的每个数据都是 URL，而 URL 不是简单的数字，是平均长度为 64 字节的字符串。

也就是说，我们要让待判重的 URL，跟链表中的每个 URL，做字符串匹配。显然，这样一个字符串匹配操作，比起单纯的数字比对，要慢很多。

所以，基于这两点，执行效率方面肯定是有优化空间的。

In actually，如果要想内存方面有优化，那就得换一种存储结构，布隆过滤器（Bloom Filter）。

在讲布隆过滤器前，我要先讲一下另一种存储结构，位图（BitMap）。因为，布隆过滤器本身就是基于位图的，是对位图的一种改进。

Q: 有 1 千万个整数，整数的范围在 1 到 1 亿之间。如何快速查找某个整数是否在这 1 千万个整数中呢？当然，这个问题还是可以用散列表来解决。不过，我们可以使用一种比较“特殊”的散列表，那就是位图。

我们申请一个大小为 1 亿、数据类型为布尔类型（true 或者 false）的数组。将这 1 千万个整数作为数组下标，将对应的数组值设置成 true。

比如，整数 5 对应下标为 5 的数组值设置为 true，也就是 array[5]=true。

当查询某个整数 K 是否在这 1 千万个整数中的时候，只需要将对应的数组值 array[K] 取出来，看是否等于 true。

如果等于 true，那说明 1 千万整数中包含这个整数 K；相反，就表示不包含这个整数 K。

2.4 位图&布隆过滤器

实际上，表示 true 和 false 两个值，我们只需要用一个二进制位（bit）就行。

那如何通过编程语言，来表示一个二进制位呢？

这里就要用到位运算了。可以借助编程语言中提供的数据类型，比如 int、long、char 等类型，通过位运算，用其中的某个位表示某个数字。

位图通过数组下标来定位数据，

所以，访问效率非常高。

而且，每个数字用一个二进制位来表示，在数字范围不大的情况下，所需要的内存空间非常节省。

比如just的例子，如果用散列表存储这 1 千万的数据，数据是 32 位的整型数，也就是需要 4 个字节的存储空间，那总共至少需要 40MB 的存储空间。

如果我们通过位图的话，数字范围在 1 到 1 亿之间，只需要 1 亿个二进制位，也就是 12MB 左右的存储空间就够了。

但是，

如果数字的范围很大，比如刚刚那个问题，数字范围不是 1 到 1 亿，而是 1 到 10 亿，那位图的大小是多少？

答案就是 10 亿个二进制位，也就是 120MB 的大小，消耗的内存空间，不降反增。这个时候，布隆过滤器就要出场了。

Suppose刚刚的例子，数据个数是 1 千万，数据的范围是 1 到 10 亿。

布隆过滤器的做法是，仍然使用一个 1 亿个二进制大小的位图，然后通过哈希函数，对数字进行处理，让它落在这 1 到 1 亿范围内。
比如我们把哈希函数设计成 f(x)=x%n。其中，x 表示数字，n 表示位图的大小（1 亿），也就是，对数字跟位图的大小进行取模求余。

不过，哈希函数会存在冲突的问题，一亿零一和 1 两个数字，经过刚刚那个取模求余的哈希函数处理之后，最后的结果都是 1。

这样就无法区分，位图存储的是 1 还是一亿零一了。

为了降低这种冲突概率，当然我们可以设计一个复杂点、随机点的哈希函数。

除此之外，还有其他方法吗？我们来看布隆过滤器的处理方法。既然一个哈希函数可能会存在冲突，那用多个哈希函数一块儿定位一个数据，是否能降低冲突的概率呢？

2.5 布隆过滤器是怎么做的？

使用 K 个哈希函数，对同一个数字进行求哈希值，那会得到 K 个不同的哈希值，

分别记作 X1，X2，X3，…，XK。

把这 K 个数字作为位图中的下标，将对应的 BitMap[X1]，BitMap[X2]，BitMap[X3]，…，BitMap[XK] 都设置成 true，i.e.，用 K 个二进制位，来表示一个数字的存在。

when要查询某个数字是否存在的时候，用同样的 K 个哈希函数，对这个数字求哈希值，分别得到 Y1，Y2，Y3，…，YK。

We看这 K 个哈希值，对应位图中的数值是否都为 true，如果都是 true，则说明，这个数字存在，如果有其中任意一个不为 true，那就说明这个数字不存在。

布隆过滤器是怎么做的

对于两个不同的数字来说，经过一个哈希函数处理之后，可能会产生相同的哈希值。但是经过 K 个哈希函数处理之后，K 个哈希值都相同的概率就非常低了。

尽管采用 K 个哈希函数之后，两个数字哈希冲突的概率降低了，但是，这种处理方式又带来了新的问题，那就是容易误判。看看下面这个例子——

K个哈希函数的缺点——容易误判

三、布隆过滤器的骚操作

3.1 布隆过滤器会误判？

是的，布隆过滤器会误判。

布隆过滤器的误判的特点是什么？

它只会对存在的情况有误判。

如果某个数字经过布隆过滤器判断不存在，那说明这个数字真的不存在，不会发生误判；
如果某个数字经过布隆过滤器判断存在，这个时候才会有可能误判，有可能并不存在。

No more than，只要调整哈希函数的个数、位图大小跟要存储数字的个数之间的比例，那就可以将这种误判的概率降到非常低。
尽管布隆过滤器会存在误判，但是，这并不影响它发挥大作用。很多场景对误判有一定的容忍度。

比如我们今天要解决的爬虫判重这个问题，即便一个没有被爬取过的网页，被误判为已经被爬取，对于搜索引擎来说，也并不是什么大事情，是可以容忍的，毕竟网页太多了，搜索引擎也不可能 100% 都爬取到。

3.2 回到网页爬虫

弄懂了布隆过滤器，我们今天的爬虫网页去重的问题，就很简单了。

我们用布隆过滤器来记录已经爬取过的网页链接，假设需要判重的网页有 10 亿，那我们可以用一个 10 倍大小的位图来存储，也就是 100 亿个二进制位，换算成字节，那就是大约 1.2GB。

之前我们用散列表判重，需要至少 100GB 的空间。

相比来讲，布隆过滤器在存储空间的消耗上，降低了非常多。

再来看下，

利用布隆过滤器，在执行效率方面，是否比散列表更加高效呢？

布隆过滤器用多个哈希函数对同一个网页链接进行处理，CPU 只需要将网页链接从内存中读取一次，进行多次哈希计算，理论上讲这组操作是 CPU 密集型的。

而在散列表的处理方式中，需要读取散列冲突拉链的多个网页链接，分别跟待判重的网页链接，进行字符串匹配。

这个操作涉及很多内存数据的读取，所以是内存密集型的。我们知道 CPU 计算可能是要比内存访问更快速的，所以，理论上讲，布隆过滤器的判重方式，更加快速。

3.3 summary

布隆过滤器非常适合这种不需要 100% 准确的、允许存在小概率误判的大规模判重场景。

除了爬虫网页去重这个例子，还有比如统计一个大型网站的每天的 UV 数，也就是每天有多少用户访问了网站，可以使用布隆过滤器，对重复访问的用户，进行去重。

前面讲到，布隆过滤器的误判率，主要跟哈希函数的个数、位图的大小有关。

当We往布隆过滤器中不停地加入数据之后，位图中不是 true 的位置就越来越少了，误判率就越来越高了。

所以，对于无法事先知道要判重的数据个数的情况，我们需要支持自动扩容的功能。

当布隆过滤器中，数据个数与位图大小的比例超过某个阈值的时候，我们就重新申请一个新的位图。后面来的新数据，会被放置到新的位图中。

但是，如果我们要判断某个数据是否在布隆过滤器中已经存在，我们就需要查看多个位图，相应的执行效率就降低了一些。