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

本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer,已开源在github ,欢迎star!

转载声明:转载请注明出处,本技术博客是本人原创文章

本文GitHub https://github.com/OUYANGSIHAI/JavaInterview 已收录,这是我花了6个月总结的一线大厂Java面试总结,本人已拿大厂offer,欢迎star

原文链接:blog.ouyangsihai.cn >> 面试——如何从 100 亿 URL 中找出相同的 URL?

点击上方 **好好学java **,选择 **星标 **公众号


重磅资讯、干货,第一时间送达


今日推荐:20207月程序员工资统计,平均14357元,又跌了,扎心个人原创100W+访问量博客:点击前往,查看更多

来源:8rr.co/FR7V

  • 题目描述- 解答思路- 方法总结

    题目描述

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


推荐一个艿艿写的 6000+ Star 的 SpringBoot + SpringCloud + Dubbo 教程的仓库:https://github.com/YunaiV/SpringBoot-Labs

解答思路

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


推荐一个艿艿写的 3000+ Star 的 SpringCloud Alibaba 电商开源项目的仓库:https://github.com/YunaiV/onemall

方法总结

  1. 分而治之,进行哈希取余;1. 对每个子文件进行 HashSet 统计。
    最后,再附上我历时三个月总结的 Java 面试 + Java 后端技术学习指南,笔者这几年及春招的总结,github 1.4k star,拿去不谢!

下载方式1. 首先扫描下方二维码2. 后台回复「Java面试」即可获取

原文地址:https://sihai.blog.csdn.net/article/details/109465839

本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer,已开源在github ,欢迎star!

转载声明:转载请注明出处,本技术博客是本人原创文章

本文GitHub https://github.com/OUYANGSIHAI/JavaInterview 已收录,这是我花了6个月总结的一线大厂Java面试总结,本人已拿大厂offer,欢迎star

原文链接:blog.ouyangsihai.cn >> 面试——如何从 100 亿 URL 中找出相同的 URL?


 上一篇
面试官写了个双冒号————问我这是什么语法?Java中有这玩意? 面试官写了个双冒号————问我这是什么语法?Java中有这玩意?
点击上方 **好好学java **,选择 **星标 **公众号 重磅资讯、干货,第一时间送达 今日推荐:2020年7月程序员工资统计,平均14357元,又跌了,扎心个人原创100W+访问量博客:点击前往,查看更多 来源:suo.im
2021-04-04
下一篇 
Docker 实战总结(非常全面) Docker 实战总结(非常全面)
点击上方 **好好学java **,选择 **星标 **公众号 重磅资讯、干货,第一时间送达 今日推荐:2020年7月程序员工资统计,平均14357元,又跌了,扎心个人原创100W+访问量博客:点击前往,查看更多 来源:cnblog
2021-04-04