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

同一个网页链接有可能被包含在多个页面中，这就会导致爬虫在爬取的过程中，重复爬取相同的网页。如果你是一名负责爬虫的工程师，你会如何避免这些重复的爬取呢？

1. 算法解析

1.1 10亿个URL的特点

假设每个URL64字节，10亿个URL大概需要60G内存，如果是散列表存储，因为装载因子和存储链表指针等，可能需要100G以上。另外散列表的查询时间复杂度是O(1)， 但是大O时间复杂度表示法会忽略掉常数、系数和低阶，实际查询时间可能不低。

由此，思考有没有占用内存更少，查询更快的数据存储结构和算法？

1.2 位图（BitMap）

有1千万个整数，整数的范围在1到1亿之间。如何快速查找某个整数是否在这1千万个整数中呢？

• 申请一个大小为1亿、数据类型为布尔类型（true或者false）的数组，多数语言布尔类型；
• 实际上true和false可以用一个bit存储**，那如何通过编程语言，来表示一个二进制位呢？**

public class BitMap {
  private char[] bytes;
  private int nbits;
  
  public BitMap(int nbits) {
    this.nbits = nbits;
    this.bytes = new char[nbits/8+1];
  }

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

  public boolean get(int k) {
    if (k > nbits) return false;
    int byteIndex = k / 8;
    int bitIndex = k % 8;
    return (bytes[byteIndex] & (1 << bitIndex)) != 0;
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

优点：访问效率高，如果数据范围不大，非常节省内存。

1.3 布隆过滤器（Bloom Filter）

对位图的改进。

简单点讲：多个哈希函数一起定位一个数据。

1.3.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，那就说明这个数字不存在。

1.3.2 哈希冲突和误判

k个哈希函数降低哈希冲突，但带来误判问题。

• 如果布隆过滤器判断不存在，就真的不存在；
• 如果布隆过滤器判断存在，有可能并不存在，可以通过调整哈希函数的个数、位图大小跟要存储数字的个数之间的比例，降低误判比例。 误判是可以容忍的，一个没被爬取的网页，误判为爬过，没什么大不了。

2. 总结延申

• 布隆过滤器非常适合这种不需要100%准确的、允许存在小概率误判的大规模判重场景。
• 无法事先知道要判重的数据个数的情况，需要支持自动扩容的功能。数据个数与位图大小的比例超过某个阈值，重新申请一个新的位图，执行效率降低一些。