方案1：可以估计每个文件安的大小为5G×64=320G，远远大于内存限制的4G。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。
遍历文件a，对每个url求取hash(url)%1000，然后根据所取得的值将url分别存储到1000个小文件（记为a0,a1,...,a999）中。这样每个小文件的大约为300M。
遍历文件b，采取和a相同的方式将url分别存储到1000小文件（记为b0,b1,...,b999）。这样处理后，所有可能相同的url都在对应的小文件（a0vsb0,a1vsb1,...,a999vsb999）中，不对应的小文件不可能有相同的url。然后我们只要求出1000对小文件中相同的url即可。
求每对小文件中相同的url时，可以把其中一个小文件的url存储到hash_set中。然后遍历另一个小文件的每个url，看其是否在刚才构建的hash_set中，如果是，那么就是共同的url，存到文件里面就可以了。
方案2：如果允许有一定的错误率，可以使用Bloom filter，4G内存大概可以表示340亿bit。将其中一个文件中的url使用Bloom filter映射为这340亿bit，然后挨个读取另外一个文件的url，检查是否与Bloom filter，如果是，那么该url应该是共同的url（注意会有一定的错误率）。
转载于:https://my.oschina.net/u/4167465/blog/3096501
分享到：
相关推荐
3.给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url? 4.在2.5亿个整数中找出不重复的整数 5.腾讯面试题：给40亿个不重复的unsigned int的整数，没排过序的，然后再...
五、给定 a、b 两个文件，各存放 50 亿个 url，每个 url 各占 64 字节，内存限制是 4G，让你找出 a、b 文件共同的 url？ 解决方案可以使用 Hash 表来统计每个 url 出现的次数，然后找出共同的 url。还可以使用...
#### 一、给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，找出a、b文件共同的url **问题背景**： - 文件a、b各自包含50亿个URL，每个URL占用64字节空间。 - 内存限制为4GB，显然无法将两个...
给定 a、b 两个文件，各存放50 亿个 url，每个 url 各占 64 字节，内存限制是4G，让你找出 a、b 文件共同的url？ 方案 1：可以估计每个文件安的大小为50G× 64=320G，远远大于内存限制的4G。所以不可能将其完全加载...
1. 数据去重复：给定两个文件，各存放 50 亿个 URL，每个 URL 各占 64 字节，内存限制是 4G，要求找出共同的 URL。解决方案有两种：一种是使用分而治之的方法，分割文件然后使用 hash_set 来查找共同的 URL；另一种...
应用中，经常需要将字符串压缩成一个整数，即字符串散列。比如下面这些问题： （1）搜索引擎会通过日志...（4）给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url。
1. 根据给定的两个文件A和B，每个文件存放50亿条URL，内存限制是4G，需要找出A、B文件共同的URL。解决方法是使用Hash表来存储URL，然后使用散列函数将URL映射到不同的Hash表中，最后统计共同的URL。 2. 给定10个...
给定a、b两个⽂件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b⽂件共同的url？ 每个url⼤⼩为64bytes，那么可以估计每个⽂件的⼤⼩为5G×64=320G，远远⼤于内存限制的4G，所以不可能将其完全...
问题：给你 a、b 两个文件，各存放 50 亿条 url，每条 url 各占用 64 字节，内存限制是 4G，让你找出 a、b 文件共同的 url。 方法：使用 hash 表。使用 a 中元素创建 hash 表，hash 控制在适当规模。在hash 中查找 ...
12. 【不可使用本地 IDE】给定 a、b 两个文件，各存放 50 亿个 url，每个 url 各占 64 字节，内存限制是 4G，找出 a、b 文件共同的 url。 知识点：大规模数据处理，Hash 函数的应用，分治策略的思想，hash_set 的...