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

前言

网页爬虫是搜索引擎中非常重要的系统，负责几十亿、上百亿的网页。爬虫的工作原理是，通过解析已经爬取的页面中的网页链接，然后再爬取这些链接对应的网页。而同一网页链接有可能被包含在多个页面中，这就会导致爬虫算法在爬取的过程中，重复爬取相同的网页。如果你是一名负责爬虫的工程师，你会如何避免这些重复的爬取呢？

最容易想到的方法是，我们记录已经爬取的网页链接，再爬取一个新的网页之前，我们拿它的链接，在已经爬取的网页链接到表中搜索，如果存在，那就说明这个网页已经被爬取过了；如果不存在，那就说明这个网页链接没有被爬取过，可以继续去爬取。等爬取到这个网页之后，我们将这个网页的链接添加到已经爬取的网页链接列表里。

思路非常简单，我想你应该很容易就能想到，但是如何存储已经爬取的链接呢？需要重什么样的数据结构？

算法解析

我们先来回顾下，是否可以用我们之前学过的数据结构来解决？

这个问题要处理的对象是网页链接，也就是URL，要支持的操作有两个，添加一个URL和查找一个URL。除了这两个功能性的要求之外，在非功能性方面，我们还要求这两个操作的执行效率要尽可能高。除此之外，我们要处理的是上亿的网页链接，内存消耗会非常大，所以在存储效率上，我们要尽可能的高效。

我们回想一下，满足这些条件的数据结构有哪些？显然，散列表、红黑树、跳表这些动态数据结构，都能够支持快速插入、查找数据，但是对内存消耗方面，是否可以结构呢？

我们拿散列表来举例。假设我们要爬取10亿个网页（像google、百度这样的通用搜索引擎，爬取的网页可能会更多），为了判重，我们把着10亿个URL存储在散列表中，你来估算下，需要多少内存？

假设一个URL的平均长度是64字节，那单纯存储着10亿个URL就需要大约60GB内存空间。因为散列表需要维持较小的散列因子，才能保证不会出现过多的散列冲突，导致性能下降。而且用链表法解决冲突的散列，还需要存储链表指针，所以，如果用这10亿个URL构建的散列表，需要的内存会远远大于60GB，有可能会超过100GB。

当然，对于一个大型的搜索引擎来说，即便是100GB的内存要求，其实也不算太高，我们可以采用分治的思想，用多台机器（比如20台8GB的机器）来存储这10亿URL，这种分治的思想，我们前面讲过很多次，这里就不详细说了。

对于爬虫的URL去重这个问题，刚刚讲的分治加散列表的思想，已经可以实实在在的工作了。不过作为一个有追求的工程师，我们应该考虑，在添加、查询数据的效率以及内存消耗方面，我们是否还有进一步的优化空间呢？

你可能会说，散列表中添加、查找数据的时间复杂度都是O(1)，还有进一步优化的空间吗？实际上我们前面也说过，时间复杂度并不能代表代码的执行时间。大O时间复杂度表示法，会忽略掉常数、系数和低阶，并且统计的是语句的频度。不同的语句，执行的时间是不同的，时间复杂度只能表示执行时间随着数据规模的变化趋势，并不能度量在特定的数据规模下，代码具体执行的时间多少。

如果时间复杂度中原来的系数是10，我们现在通过优化，将系数降为1，那在时间复杂度没有变化的情况下，执行效率就提高了10倍。对于实际的软件开发来说，10倍效率的提升，显然是一个非常值得的优化。

如果我们用基于链表的方法解决散列冲突，散列表中存储的是URL，那当查询的时候，通过哈希函数定位为某个链表之后，我们还需要依次对比每个链表中的URL，这个操作是比较耗时的，主要有两点原因。

一方面，链表中的节点在内存中不是连续的，所以不能一下子加载CPU缓存中，没法很好的利用CPU高速缓存，所以数据访问性方面会大大降低。

另一方面，链表中的每个数据都是URL，而URL不是简单的数字，是平均长度为64字节的字符串，也就是说，我们要让待判重的URL，根链表中的每个URL，做字符串匹配。显然，这样一个字符串匹配操作，比起单纯的数字来说，要慢很多。

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

对于内存消耗方面的优化，除了刚刚这种基于散列表的解决方案之外，貌似没有更好的法子了。实际上，如果想要在内存方面有明显的节省，那就得换一种解决方案了，也就是我们今天要重点将的这种存储结构，布隆过滤器（Bloom Filter）。

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

我们先来看一个跟开篇的问题非常类似，但稍微简单的问题。我们有1千万个整数，整数的范围在1到1亿之间，如何快速查找某个整数是否在这1千万个整数中？

当然，这个问题还是可以用散列表解决，不过，我们还可以使用一种比较特殊的散列表，那就是位图。我们申请一个大小为1亿、数据类型为布尔类型的数组。我们将这一千万个整数作为数组下标，将对应的数组值设成true。比如，整数5对应的下标为5的数组值设成true，也就是array[5] = true。

当我们查询某个整数K是否在这1千万个整数中的时候，我们只需要将对应的数组值array[k] 取出来，看是否等于true。如果等于true，说明1千万整数中包含这个整数k，相反，就表示不包含这个整数k。

不过，很多语言中提供的布尔类型，大小是1个字节，并不能节省太多内存空间。实际上，表示true和false两个值，我们只需要用一个二进制位bit表示就可以了。那如何通过编程语言，来表示一个二进制位呢？

这里就要用到位运算了。我们可以借助编程语言中提供的数据类型，比如int、long、char等类型，通过位运算，用其中的某个位表示某个数字。文字描述起来有点不好理解，我把位图的代码写了出来，你可以对照代码看下，应该就能懂了。

package org.renhj.bitmap;

import java.util.Random;

public class BitMap {
    private char[] chars;
    private int nBits;

    BitMap(int nBits){
        this.nBits = nBits;
        this.chars = new char[nBits/16 + 1];
    }

    public void set(int k) {
        if (k > nBits) return;
        int byteIndex = k/16;
        int bitIndex = k%16;

        chars[byteIndex] |= (1<< bitIndex);
    }

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

    public static void main(String[] args) {
        BitMap bitMap = new BitMap(1000);

        for (int i = 0; i < 100; i++) {
            bitMap.set(new Random().nextInt(100));
        }
    }
}

从刚刚位图结构的讲解中，你应该可以发现，位图通过数组下标来定位数据，所以访问效率非常高，而且，每个数字用一个二进制位来表示，在数字范围不大的情况下，所需要的内存空间非常节省。

比如刚刚的例子，如果用散列表存储这1千万的数据，数据是32位的整型，也就是需要4个字节的存储空间，那总共至少需要40MB的存储空间，如果我们通过位图的话，数字范围在1到1亿之间，只需要1亿个二进制位，也就是12MB左右的存储空间就够了。

关于位图，我们就讲完了，是不是很简单？不过，这里我们有个假设，就是数字所在的范围不是很大，如果数字的范围很大，比如刚刚那个问题，数字范围不是1到1亿，而是1到10亿，那位图的大小就是10亿个二进制位，也就是120MB大小，消耗的内存空间，不降反增。

这个时候，布隆过滤器就出场了。布隆过滤器就是为了解决刚刚这个问题，对位图这种数据结构的一种改进。

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

不过，你肯定会说，哈希函数会存在冲突的问题，一亿零一和1两个数字，经过你刚刚那个取模求余的哈希函数之后，最后的处理结果都是1。这样我就无法区分，位图存储的是1还是一亿零一了。

为了降低这种冲突概率，当然我们可以设计一个复杂点、随机点的哈希函数。除此之外，还有其他方法吗？我们来看看布隆过滤器的处理方法。既然一个哈希函数可能会存在冲突，那用多个哈希函数一块定位一个数据，是否能降低冲突的概率呢？我来具体解释一下，布隆过滤器是怎么做的。

我们使用k个哈希函数，对同一个数字进行哈希求值，那会得到k个不同的哈希值，我们分别记做X1、X2、X3、。。。 Xk。我们把这k个数字作为位图中的下标，将对应的Bitmap[X1]、Bitmap[X2]、Bitmap[X3]、… Bitmap[Xk] 都设置成True，也就是说，我们用k个二进制位，来表示一个数字的存在。

当我们需要查询某个数字是否存在的时候，我们用同样的k个哈希函数，对这个数字求哈希值，分别得到Y1、Y2、Y3、… Yk。我们看这k个哈希值，对应位图中的数值是否都为True，如果都是True，则说明这个数字存在，如果有其中一个不为True，这说明这个数字不存在。

对于两个不同的数字来说，经过一个哈希函数的处理之后，可能会产生相同的哈希值，但是经过k个哈希函数处理后，k个哈希值都相同的概率就非常低了。尽管采用k个哈希函数之后，两个数字哈希冲突的概率降低了，但是这种处理方式又带来了新的问题，那就是容易误判，

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

尽管布隆过滤器会存在误判，但是这并不影响它的应用。在很多场景中，对于误判有一定的容忍度。比如我们今天要解决的爬虫去重的问题，即使一个没有被爬取过的网页，被误判为已经爬取过，对于搜索引擎来说，也不是什么大事，是可以容忍的，毕竟网页太多了，搜索引擎也不可能都爬取到。

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

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

那我们再来看下，利用布隆过滤器，在执行效率方面，是否比散列表更加高效呢？

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

总结引申

今天，关于搜索引擎爬虫网页去重问题的解决，我们从散列表讲到位图，在讲到布隆过滤器。布隆过滤器非常适合这种不需要100%准确的、允许存在小概率误判的大规模判重场景。除了爬虫网页去重这个例子，还有比如统计一个大型网站的每天UV数，也就是每天有多少用户访问了网站，我们就可以使用布隆过滤器，对重复访问的用户，进行去重。

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

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

位图、布隆过滤器应用如此广泛，很多编程语言都已经实现了。比如Java的BitSet类就是一个位图，Redis也提供了BitMap位图类，Google的Guava工具包提供了BloomFliter布隆过滤器的实现。如果你感兴趣，可以去研究下这些源码。

课后思考

假设我们有1亿个整数，整数范围是从1到10亿，如何快速并且省内存的给这1亿个数据从小到大排序
还记得我们在哈希函数中就讲过的分治思想，用散列表记忆哈希函数，实现海量图库中的判重功能？如果我们允许小概率的误判，那是否可以用今天的布隆过滤器来解决呢？你可以参照我们当时的评估算法，重新评估下，用布隆过滤器需要多少台机器？