Cracking the coding interview--Q12.6

题目

原文：

You have a billion urls, where each is a huge page. How do you detect the duplicate documents?

译文：

你有10亿个url，每个url对应一个非常大的网页。你怎么检测重复的网页？

网页大，数量多，要把它们载入内存是不现实的。因此我们需要一个更简短的方式来表示这些网页。而hash表正是干这事的。我们将网页内容做哈希，而不是url，这里不同url可能对应相同的网页内容。
将每个网页转换为一个哈希值后，我们就得到了10亿个哈希值，很明显，两两对比也是非常耗时的O(n^2 )。因此我们需要使用其它高效的方法。

根据以上分析，我们可以推出满足条件的以下算法：

通过这种方法我们可以得到一组url，其对应的网页内容都是唯一的。但有一个问题，一台计算机可以完成以上任务吗？

一个网页我们要花费多少存储空间？
- 每个网页转换成一个4字节的哈希值
- 假设一个url平均是30个字符，那我们至少需要30个字节
- 因此对应一个url，我们一共要用掉34个字节
34字节 * 10亿 = 31.6GB。很明显，单机的内存是无法搞定的。

我们要如何解决这个问题？

我们可以将这些数据分成多个文件放在磁盘中，分次载入内存处理。这样一来我们要解决的就是文件的载入/载出问题。
我们可以通过哈希的方式将数据保存在不同文件，这样一来，大小就不是问题了，但存取时间就成了问题。硬盘上的哈希表随机读写要耗费较多的时间，主要花费在寻道及旋转延迟上。关于这个问题，可以使用电梯调度算法来消除磁头在磁道间的随机移动，以此减少消耗的时间。
我们可以使用多台机器来处理这些数据。这样一来，我们要面对的就是网络延迟。假如我们有n台机器。
- 首先，我们对网页做哈希，得到一个哈希值v
- v%n 决定这个网页的哈希值会存放在哪台机器
- v/n 决定这个哈希值存放在该机器上哈希表的位置

全书题解目录：

全书的C++代码托管在Github上：

声明：自由转载-非商用-非衍生-保持署名 | 创意共享3.0许可证，转载请注明作者及出处

出处：http://hawstein.com/2013/02/01/12.6/