美文网首页
两个大文件中找出共同记录: 分而治之+布隆过滤器

两个大文件中找出共同记录: 分而治之+布隆过滤器

作者: 疯狂的冰块 | 来源:发表于2019-10-28 21:14 被阅读0次

题目描述

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

解决方案是分而治之:
将文件a按照hash分为10000份,
hash(url)%10000
然后去b文件逐个判断是否在a文件中。

这里有一个优化的地方,就是使用布隆过滤器,如果判断不存在不再去b文件判断,这样可以有效挡住大部分无效的判断。

相关文章

网友评论

      本文标题:两个大文件中找出共同记录: 分而治之+布隆过滤器

      本文链接:https://www.haomeiwen.com/subject/sdrivctx.html