BD面试题1-两个大文件中找出公共记录[转载]

时间:2023-12-11 13:15:50

转自:https://blog.csdn.net/tiankong_/article/details/77234726#commentBox

1.题目

给定a、b两个文件,各存放50亿个url,每个url各占64字节,内存限制是4G,让你找出a、b文件共同的url?

2.思考过程

//我看见这个题就啥也没想到,想不到哈希啊。。。

可以使用哈希,对a文件中的所有进行遍历,再对b进行遍历,但是由于文件过大,并且还要给哈希表分配空间,所以一次性建立哈希表希望不大。

3.解决办法

50亿*64B=320G,一个G相当于9个0.

那么可以对每个url得到的hash值,再%1000,这样可以将其分为1000个文件,每个大约300M,那么总共就大约320G了;

对b文件也用同样的方法进行映射,那么相同的url肯定被映射到同一文件了;

那么问题就变成了比较1000个小文件中的了,这就比较好办了,就用hash就可以了