不重复抓取策略

不重复的关键在于记住历史，只有记住过去才可能不重复。那些不需要记忆历史的程序设计往往都比较简单，从计算机的角度上讲即有限状态机模型。每个状态都是对历史的积累，而没有记忆历史，这种只需要有限的存储即可完成的工作通常都比较简单。而那些需要记住历史的程序相对复杂，例如迷宫求解程序，则需要一个栈（stack）结构记住走过的地方。从而在失败时可以回溯，继续寻找出路。而通过动态规划寻找问题最优解等程序，也都需要一个记住历史的功能才能保证不重复计算。

爬虫记录历史的方式是哈希表（也称为“杂凑表”），每一条记录是否被抓取的信息存放在哈希表的某一个槽位上。如果某网页在过去的某个时刻已经被抓取，则将其对应的槽位的值置1，反之置0。而具体映射到哪一个槽位，则由哈希函数决定。在介绍哈希表前，我们首先简单了解一下MD5签名函数。

1992年8月，Ronald L. Rivest在向IEFT提交的一份重要文件中描述了这种MD5签名算法的原理。由于这种算法的公开性和安全性，所以在20世纪90年代被广泛使用。MD5签名是一个哈希函数，可以将任意长度的数据流转换为一个固定长度的数字（通常为4个整型，即128位）。这个数字称为“数据流的签名”或者“指纹”（Digital Finger Print），并且数据流中的任意一个微小的变化都会导致签名值发生变化。

将URL字符串数字化是通过某种计算将任何一个URL字符串唯一地计算成一个整数，

在一个URL哈希函数映射下，任意一个字符串都唯一地对应一个整数。一个64位整数可以表达1800万TB（1TB＝1000GB），而字符串空间的大小远远大于64位整数所表达的整数空间大小，因此碰撞是不可避免的。碰撞是指那些字符串不同，而计算出相同的签名值的情况。如果杂凑函数设计得足够好，则相互碰撞的机会可以小到忽略不计。

更加理论化的表示如下：

令U＝128位整数集合，S＝字符串集合：

其中Ti∈U，Tj∈U，URLi≠URLj，则P（Ti＝Tj）＜ε。

不难看出，对于两个不相同的URL，即URLi和URLj通过哈希函数分别计算出各自的签名值Ti及Tj，这两个签名值相等（碰撞）的概率小于一个足够小的小整数ε。正是由于MD5函数符合这种特性，因此被广泛地用做哈希函数。

标准MD5签名的整数空间很大，128位整数能表达2的128次方个不同的数，这是十分巨大的。而实际分配的哈希表空间却十分有限，一个普通32位处理器，理论上最多可以分配2的32次方大小的内存，即4G大小的内存（Linux系统中操作系统内核还需占用1G内存，实际上可供搜索引擎使用的极限内存只有3G）。

因此，在实际处理中将签名值进行模运算映射到实际的哈希表中（可以理解为哈希表存放在内存中）。哈希函数可以是MD5（URL）％n（％表示取模运算），这样使得一个URL被映射到大小为n的哈希表的某个槽位上。

哈希表是简单的顺序表，即数组。从实际应用的角度看，这个数组要足够大，而且尽可能地全部放在内存中，以保证每一个URL的签名都可以通过查找哈希表来确定是否曾经抓取过，其示例如图2-9所示。