程序员面试金典

1、题目描述

给定100亿个网址，如何检测出重复的文件？这里所谓的“重复”是指两个URL完全相同。

2、思路

100亿个网址（URL）要占用多少空间呢？如果每个网址平均长度为100个字符，每个字符要占用4字节，则这份100亿个网址的列表将占用约4兆兆字节（4TB）。在内存中可能放不下那么多数据。

不过，不防假装一下，这些数据真的奇迹般的放进了内存，毕竟先求解简化的题目是很有用的做法。对于此题的简化版，只要创建一个散列表（HashMap），第一次扫描所有网址，将URL作为key，将URL出现的次数作为value，统计所有URL出现的次数。第二次扫描所有URL,出现次数大于1的URL，则为重复的URL。（另一种做法是对列表进行排序，找出重复项，这需要额外耗费一些时间，几无优点可言）。

至此，我们得到此题简化版的解法，那么，假设我们手上有4000GB的数据，而且无法全部放入内存，该怎么办？倒也好办，我们可以将部分数据存储至磁盘，或者将数据分拆到多台机器上。

解法1：存储至磁盘

若将所有数据存储在一台机器上，可以对数据进行两次扫描。第一次扫描是将网址列表拆分为4000组，每组1GB。简单的做法是将每个网址u存放在名为.txt的文件中，其中x=hash(u)%4000。也就是说，我们会根据网址的散列值（除以分组数量取余数）分割这些网址。这样一来，所有散列值相同的网址都会位于同一文件。

第二次扫描时，我们其实是在实现前面简化版问题的解法：将每个文件载入内存，创建网址的散列表（HashMap），找出重复的。

解法2：多台机器

另一种解法的基本流程是一样的，只不过要使用多台机器。在这种解法中，我们会将网址发送到机器x上，而不是储存至文件.txt。

使用多台机器有优点也有缺点。

主要优点是可以并行执行这些操作，同时处理4000个分组。对于海量数据，这么做就能迅速有效的解决问题。

缺点是现在必须依靠4000台不同的机器，同时要做到操作无误。这可能不太现实（特别是对于数据量更大、机器更多的情况），我们需要开始考虑如何处理机器故障。此外，涉及这么多机器，无疑大幅度增加了系统的复杂性。

注：如果利用Hadoop，可以在mapper中，以x作为key，相应的url作为value发送到reducer，相同key的url会来到同一个reducer，利用前面简化版问题的解法，找出重复网址。