面试：如何从 100 亿 URL 中找出相同的 URL？

- 日理万妓 2021-09-02 06:52 334阅读 0赞

点击上方 [Java后端][Java]，选择 设为星标

优质文章，及时送达

--------------------

来源：8rr.co/FR7V

题目描述

给定 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 保存到一个单独的文件中。

方法总结

1.  分而治之，进行哈希取余；
2.  对每个子文件进行 HashSet 统计。

- END -
    最近整理一份面试资料《Java技术栈学习手册》，覆盖了Java技术、面试题精选、Spring全家桶、Nginx、SSM、微服务、数据库、数据结构、架构等等。
    获取方式：点“ 在看，关注公众号 Java后端 并回复 777 领取，更多内容陆续奉上。
    推荐阅读 
    1. 贼 TM 好用的 Java 工具类库
    2. 推荐 5 款好用的REST API工具
    3. MySQL 优化实施方案
    4. 牛逼！这篇文章让我重新认识了并发编程
    5. 955 不加班公司名单：955.WLB
    
    喜欢文章，点个在看

[Java]: http://mp.weixin.qq.com/s?__biz=Mzg2MjEwMjI1Mg%3D%3D&chksm=ce0da17bf97a286df119047a25b7de51621fe542816673bb4aa3ebd8ab97b09a86ed7db2e2ee&idx=3&mid=2247489272&scene=21&sn=ce74938072fc73a808d83ccb474db46d#wechat_redirect