解答
思路:
先计算总的数据大小,看能不能一次性放到内存里
·50亿 = 5,000,000,000≈5G,
·总大小为 5G * 64B = 32GB, 远大于4G内存
找到共同的Url,需要每个值都比较,只能使用哈希将文件切分成小文件
·文件的数量怎么确定?
切成小文件后,内存里需要同时存在a和b的两个小文件,才能进行比较。
那一个小文件的最大大小为2G, 32/2 = 16, 但是机器运行还需要内存
我们可以切分为20份,两个小文件占用内存3.2G
1.对a ,b hash(url)%20, 分为20个小文件里
hash映射函数可以有多样选择,
最简单的就是按首字母分类,可以分成26个小文件,但是不能保证每个文件大小相等, 也不符合20个小文件的设定(当然也可以改成切分成26个小文件)
可以取前4个字节的int和%20,分配到20个小文件中
2.因为使用同一个hash函数映射规则的原因,a,b切分后相同的Url存在于对应的小文件中,即a0只需要和b0比较, a1 和b1比较即可
3.然后,同时加载每一对小文件(如a0和b0),如果有相同的url, 则输出到文件中记录
全部比较完成后,文件中就是所有相同的记录
哈希切分成小文件,是解决大数据问题最常用的方法
简直是我梦想中的offer,好想去上班
感觉文章思路挺清晰的~