44位图：如何实现网页爬虫中的URL去重功能

首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。

搜索引擎中爬虫的工作原理是——解析已经爬取页面中的网页链接，然后再爬取这些链接对应的网页。那同一个网页链接可能包含在多个页面中，导致爬虫的过程中，重复抓取相同的页面。那如何避免这些重复的爬取呢？最简单的方法是记录爬取的网页链接（URL），每次爬取一个网页之前，在记录中进行查询。

不过，应该如何记录已经爬取的网页链接呢？需要用什么样的数据结构呢？

算法解析

这个问题要处理的对象是网页链接，也就是URL。数据结构需要满足如下几个条件：

支持添加一个URL和查询一个URL，并且执行效率要尽可能高
因为URL很多，所以在存储效率上，要尽可能高效

前面学过的散列表、红黑树、跳表动态数据结构，都能支持快速地插入、查找数据。接着以散列表为例分析内存消耗。

假设要爬取10亿个网页，每个URL平均长度为64个字节，全部存储需要 60GB 的内存空间。而一方面，散列表必须维持较小的装载因子，才能保证不会出现过多的散列冲突，导致操作的性能下降。另一方面，用链表法解决冲突的散列表，还会存储链表指针。所以如果将这 10 亿个 URL 构建成散列表，那需要的内存空间会远大于 60GB，有可能会超过 100GB。这时可以采取分治的思想，用多台机器来存储这 10 亿网页链接。

不过，我们还应该考虑在添加、查询数据的效率以及内存消耗方面，是否还有进一步的优化空间呢？

散列表中添加、查找数据的时间复杂度已经是$O(1)$了。但是时间复杂度并不能完全代表代码的执行时间。大 O 时间复杂度表示法，会忽略掉常数、系数和低阶，并且统计的对象是语句的频度。不同的语句，执行时间也是不同的。时间复杂度只是表示执行时间随数据规模的变化趋势，并不能度量在特定的数据规模下，代码执行时间的多少。

若时间复杂度原来的系数是10，通过优化可以将系数降为1，那在时间复杂度没变化情况下，执行效率提高了10倍。对于这个问题，若用基于链表的方法解决冲突问题，散列表中存储的是URL，每次查询使用哈希函数定位到某个链表时，要依次比对每个链表中的 URL。这比较耗时：

链表中的结点在内存中是不连续存储的，所以不能一下子加载到CPU 缓存中，没法很好的利用到CPU的高速缓存，所以数据访问性能方面会打折扣
链表中的每个数据都是 URL，而 URL 不是简单的数字，是平均长度为 64 字节的字符串。这需要用到字符串匹配操作，比单纯的数字比对，要慢得多

对于内存消耗方面，除了刚刚这种基于散列表的解决方案，貌似没有更好的法子了。但是换一种存储结构——布隆过滤器（Bloom Filter），就可以在内存方面更加节省。这种数据结构本身是基于另一种数据结构——位图（BitMap）而言的，是对位图的一种改进。

首先思考一个跟开篇问题相似，但是稍微简单的问题——有 1 千万个整数，整数的范围在 1 到 1 亿之间。如何快速查找某个整数是否在这 1 千万个整数中呢？

这个问题仍然可以用散列表解决，不过可以用一个特殊的散列表——位图。申请一个大小为1亿，数据类型为bool类型的数组。将已知的一千万整数作为数组下标，相应的数组值设置为true。当查询某个整数 K 是否在这1千万个整数时，只需要将对应的数组值 array[K]取出来，看是否等于 true 即可。

不过，很多语言提供的bool类型大小为一个字节，并不是一个二进制位（bit），并不能节省太多空间。那如何通过编程语言，来表示一个二进制位呢？可以借助编程语言中提供的数据类型，比如 int、long、char 等类型，通过位运算，用其中的某个位表示某个数字。对应代码如下：

// 将数字 A 的第 k 位设置为1：A = A | (1 << (k - 1))
// 将数字 A 的第 k 位设置为0：A = A & ~(1 << (k - 1))
// 检测数字 A 的第 k 位：A & (1 << (k - 1)) != 0
// 可以参考 https://mp.weixin.qq.com/s/xxauNrJY9HlVNvLrL5j2hg
public class BitMap { // Java中char类型占16bit，也即是2个字节
  private char[] bytes;
  private int nbits;
  
  public BitMap(int nbits) {
    this.nbits = nbits;
    this.bytes = new char[nbits/16+1];
  }

  public void set(int k) {
    if (k > nbits) return;
    int byteIndex = k / 16;
    int bitIndex = k % 16;
    bytes[byteIndex] |= (1 << bitIndex);
  }

  public boolean get(int k) {
    if (k > nbits) return false;
    int byteIndex = k / 16;
    int bitIndex = k % 16;
    return (bytes[byteIndex] & (1 << bitIndex)) != 0;
  }
}

位图通过数组下标来定位数据，所以访问效率非常高。另外，每个数字用一个二进制位表示，数组范围不大时，所需内存空间非常节省。

比如刚才例子，用散列表存储这1千万数据，数据为32位整数（占用4个字节的存储空间），那总共至少需要 40MB存储空间。而若用位图，数字范围在1到1亿之间，只需要1亿个二进制位，占用12MB左右存储空间。

但是，若数字范围很大为从1到10亿，那位图大小就是10亿个二进制位，也就是120MB大小，消耗的内存更大了。这时需要布隆过滤器了。

假设数据个数是1千万，数据范围是从1到10亿，布隆过滤器仍然使用一个1亿个二进制大小的位图，然后通过哈希函数，将数据映射到1到1亿范围内。比如哈希函数设计为 f(x) = x%n。其中，x表示数字，n 表示位图的大小（1 亿）。但是这样肯定是存在哈希冲突问题的。如一亿零一和1两个数字经过哈希函数后，结果都是1。也就无法判断位图存储的是 1 还是一亿零一了。

对于这个问题，可以设计一个复杂点、随机点的哈希算法。布隆过滤器换了另外一种解决思路：一个哈希函数可能会存在冲突，那用多个哈希函数一块儿定位一个数据，是否能降低冲突的概率呢？

具体而言，使用K个哈希函数，对同一个数字求哈希值，得到K个不同的哈希值。分别记作 $X_1，X_2，X_3，…，X_K$。把这 K 个数字作为位图中的下标，将对应的 $BitMap[X_1]，BitMap[X_2]，BitMap[X_3]，…，BitMap[X_K]$都设置成 true。也就是用 K 个二进制位表示一个数字的存在。

当要查询某个数字是否存在时，用相同的K个哈希函数，对这个数字求哈希值，分别得到 $Y_1，Y_2，Y_3，…，Y_K$。看这 K 个哈希值，对应位图中的数值是否都为 true，如果都是 true，则说明，这个数字存在，如果有其中任意一个不为 true，那就说明这个数字不存在。

对于两个不同的数字，经过一个哈希函数处理之后，可能会产生相同的哈希值。但是经过 K 个哈希函数之后，K个哈希值都相同的概率非常低。但这又带来了一个问题——容易误判。

布隆过滤器误判有一个特点——只对存在的情况有误判。如果某个数字经过布隆过滤器判断不存在，那说明这个数字真的不存在，不会发生误判；如果某个数字经过布隆过滤器判断存在，这个时候才会有可能误判，有可能并不存在。不过，只要调整哈希函数的个数、位图大小跟要存储数字的个数之间的比例，那就可以将这种误判的概率降到非常低。

尽管布隆过滤器存在误判，但很多场景对误判有一定的容忍度，所以并不影响它发挥大作用。比如今天爬虫判重问题，即便一个没有被爬取过的网页，被误判为已经被爬取，这是可以容忍的。

接下来说下网页去重的思路：用布隆过滤器来记录已经爬取过的网页链接，假设需要判重的网页有 10 亿，可以用一个 10 倍大小的位图来存储，也就是 100 亿个二进制位，大约 1.2GB。之前用散列表判重，需要至少 100GB 的空间。相比来讲，布隆过滤器在存储空间的消耗上，降低了非常多。

相比于散列表，使用布隆过滤器在执行效率上：布隆过滤器用多个哈希函数对同一个网页链接进行处理，CPU 只需要将网页链接从内存中读取一次，进行多次哈希计算，理论上讲这组操作是 CPU 密集型的。而在散列表的处理方式中，需要读取散列冲突拉链的多个网页链接，分别跟待判重的网页链接，进行字符串匹配。这个操作涉及很多内存数据的读取，所以是内存密集型的。我们知道 CPU 计算可能是要比内存访问更快速的，所以，理论上讲，布隆过滤器的判重方式，更加快速。

总结引申

本节讲的布隆过滤器非常适合这种不需要 100% 准确的、允许存在小概率误判的大规模判重场景。除了网页去重，它还可以用来统计一个大型网站的每天UV数（每天有多少用户访问了网站），对重复访问的用户去重。

布隆过滤器的误判率，主要跟哈希函数的个数、位图的大小有关。当往布隆过滤器中不停地加入数据之后，位图中不是 true 的位置就越来越少了，误判率就越来越高了。所以，对于无法事先知道要判重的数据个数的情况，需要支持自动扩容的功能。

当布隆过滤器中，数据个数与位图大小的比例超过某个阈值的时候，就重新申请一个新的位图。后面来的新数据，会被放置到新的位图中。但是，如果要判断某个数据是否在布隆过滤器中已经存在，就需要查看多个位图，相应的执行效率就降低了一些。

课后思考

假设我们有 1 亿个整数，数据范围是从 1 到 10 亿，如何快速并且省内存地给这 1 亿个数据从小到大排序？
答：传统做法：1亿个整数，存储需要400M空间，排序时间复杂度最优 N×log(N)。使用位图：数字范围是1到10亿，用位图存储125M就够了，然后将1亿个数字依次添加到位图中，然后再将位图按下标从小到大输出值为1的下标，排序就完成了，时间复杂度为 N。