如何从 100 亿 URL 中找出相同的 URL?

公众号程序猿DD

共 1097字,需浏览 3分钟

 ·

2021-08-05 03:43

来源 | https://doocs.github.io/advanced-java/

题目描述

给定 a、b 两个文件,各存放 50 亿个 URL,每个 URL 各占 64B,内存限制是 4G。请找出 a、b 两个文件共同的 URL。

解答思路

每个 URL 占 64B,那么 50 亿个 URL占用的空间大小约为 320GB。

5, 000, 000, 000 * 64B ≈ 5GB * 64 = 320GB

由于内存大小只有 4G,因此,我们不可能一次性把所有 URL 加载到内存中处理。对于这种类型的题目,一般采用分治策略 ,即:把一个文件中的 URL 按照某个特征划分为多个小文件,使得每个小文件大小不超过 4G,这样就可以把这个小文件读到内存中进行处理了。

思路如下 :

首先遍历文件 a,对遍历到的 URL 求 hash(URL) % 1000 ,根据计算结果把遍历到的 URL 存储到 a0, a1, a2, ..., a999,这样每个大小约为 300MB。使用同样的方法遍历文件 b,把文件 b 中的 URL 分别存储到文件 b0, b1, b2, ..., b999 中。这样处理过后,所有可能相同的 URL 都在对应的小文件中,即 a0 对应 b0, ..., a999 对应 b999,不对应的小文件不可能有相同的 URL。那么接下来,我们只需要求出这 1000 对小文件中相同的 URL 就好了。

接着遍历 ai( i∈[0,999] ),把 URL 存储到一个 HashSet 集合中。然后遍历 bi 中每个 URL,看在 HashSet 集合中是否存在,若存在,说明这就是共同的 URL,可以把这个 URL 保存到一个单独的文件中。

方法总结

  • 分而治之,进行哈希取余;
  • 对每个子文件进行 HashSet 统计。


往期推荐

CEO不当了,CTO也不做了!我要回去写代码,这才是我所热爱的!

用谷歌搜索技术问题一定比用百度好?也未必...

好多大咖曾看他的书学习Java,如今这个男人的新作来了!

Lombok!代码简洁神器还是代码“亚健康”元凶?

IntelliJ IDEA官方宣布中文汉化包正式发布



喜欢本文欢迎转发,关注我订阅更多精彩

关注我回复「加群」,加入Spring技术交流群

浏览 20
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报