扫码关注微信公众号

回复“面试手册”,获取本站PDF版

回复“简历”,获取高质量简历模板

回复“加群”,加入程序员交流群

回复“电子书”,获取程序员类电子书

当前位置: 场景题 > 海量数据高频面试题 > 5.给定a、b两个文件,各存放50亿个url,每个url各占64字节,内存限制是4G,让你找出a、b文件共同的url?

每个url是64字节,50亿*64大约等于300多G,内存限制为4G,所以不能直接放入内存中。

还是前面的分治思路,遍历文件a中的url,对url进行hash(url)%1000,将50亿的url分到1000个文件中存储(a0,a1,a2…….),每个文件大约300多M,对文件b进行同样的操作,因为hash函数相同,所以相同的url必然会落到对应的文件中,比如文件a中的url1与文件b中的url2相同,那么它们经过hash(url)%1000也是相同的。即url1落入第n个文件中,url2也会落入到第n个文件中。

第二步是遍历a0中的url,存入HashSet中,同时遍历b0中的url,查看是否在HashSet中存在,如果存在则保存到单独的文件中。然后依次遍历a2,a3,a4………,b2,b3,b4………


点击面试手册,获取本站面试手册PDF完整版