【出自BD面试题】
难度系数：★★★★☆ 被考察系数：★★★★☆
题目描述：
给定a、b两个文件，各存放50亿个url，每个url各占64B，内存限制是4GB，请找出a、b两个文件共同的url。
分析与解答：(www.xing528.com)
由于每个url需要占64B，所以50亿个url占用空间的大小为50亿×64=5GB×64=320GB。由于内存大小只有4GB，因此不可能一次性把所有的url都加载到内存中处理。对于这个类型的题目，一般都需要使用分治法，即把一个文件中的url按照某一特征分成多个文件，使得每个文件的内容都小于4GB，这样就可以把这个文件一次性读到内存中进行处理了。对于本题而言，主要的实现思路如下：
（1）遍历文件a，对遍历到的url求hash（url）%500，根据计算结果把遍历到的url分别存储到a0，a1，a2，…，a499（计算结果为i的url存储到文件ai中），这样每个文件的大小大约为600M。当某一个文件中url的大小超过2GB的时候，可以按照类似的思路把这个文件继续分为更小的子文件（例如：如果a1大小超过2GB，那么可以把文件继续分成a11，a12…）。
（2）使用同样的方法遍历文件b，把文件b中的url分别存储到文件b0，b1，…，b499中。
（3）通过上面的划分，与ai中url相同的的url一定在bi中。由于ai与bi中所有的url的大小不会超过4GB，因此可以把它们同时读入到内存中进行处理。具体思路：遍历文件ai，把遍历到的url存入到hash_set中，接着遍历文件bi中的url，如果这个url在hash_set中存在，那么说明这个url是这两个文件共同的url，可以把这个url保存到另外一个单独的文件中。当把文件a0～a499都遍历完成后，就找到了两个文件共同的url。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
