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

沙海 2021年3月10日05:20:39杂谈 Java评论88字数 1455阅读4分51秒阅读模式
摘要

速读摘要

速读摘要文章源自JAVA秀-https://www.javaxiu.com/3191.html

给定a、b两个文件,各存放50亿个URL,每个URL各占64B,内存限制是4G。由于内存大小只有4G,我们不可能一次性把所有URL加载到内存中处理。集合中是否存在,说明这就是共同的URL,可以把这个URL保存到一个单独的文件中。MyBatis、Redis、MongoDB、ES、分库分表、读写分离、SpringMVC、Webflux、权限、WebSocket、Dubbo、RabbitMQ、RocketMQ、Kafka、性能测试等等内容。文章源自JAVA秀-https://www.javaxiu.com/3191.html

原文约 2811 | 图片 6 | 建议阅读 6 分钟 | 评价反馈文章源自JAVA秀-https://www.javaxiu.com/3191.html

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

点击关注 ? Java基基 文章源自JAVA秀-https://www.javaxiu.com/3191.html

点击上方“Java基基”,选择“设为星标”文章源自JAVA秀-https://www.javaxiu.com/3191.html

做积极的人,而不是积极废人!文章源自JAVA秀-https://www.javaxiu.com/3191.html

文章源自JAVA秀-https://www.javaxiu.com/3191.html

源码精品专栏文章源自JAVA秀-https://www.javaxiu.com/3191.html

 文章源自JAVA秀-https://www.javaxiu.com/3191.html

文章源自JAVA秀-https://www.javaxiu.com/3191.html

来源:8rr.co/FR7V文章源自JAVA秀-https://www.javaxiu.com/3191.html

  • 题目描述文章源自JAVA秀-https://www.javaxiu.com/3191.html

  • 解答思路文章源自JAVA秀-https://www.javaxiu.com/3191.html

  • 方法总结文章源自JAVA秀-https://www.javaxiu.com/3191.html

面试:如何从 100 亿 URL 中找出相同的 URL?文章源自JAVA秀-https://www.javaxiu.com/3191.html

题目描述

给定 a、b 两个文件,各存放 50 亿个 URL,每个 URL 各占 64B,内存限制是 4G。请找出 a、b 两个文件共同的 URL。文章源自JAVA秀-https://www.javaxiu.com/3191.html

解答思路

每个 URL 占 64B,那么 50 亿个 URL占用的空间大小约为 320GB。文章源自JAVA秀-https://www.javaxiu.com/3191.html

5, 000, 000, 000 * 64B ≈ 5GB * 64 = 320GB文章源自JAVA秀-https://www.javaxiu.com/3191.html

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

思路如下文章源自JAVA秀-https://www.javaxiu.com/3191.html

首先遍历文件 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 就好了。文章源自JAVA秀-https://www.javaxiu.com/3191.html

接着遍历 ai( i∈[0,999] ),把 URL 存储到一个 HashSet 集合中。然后遍历 bi 中每个 URL,看在 HashSet 集合中是否存在,若存在,说明这就是共同的 URL,可以把这个 URL 保存到一个单独的文件中。文章源自JAVA秀-https://www.javaxiu.com/3191.html

方法总结

  1. 分而治之,进行哈希取余;文章源自JAVA秀-https://www.javaxiu.com/3191.html

  2. 对每个子文件进行 HashSet 统计。文章源自JAVA秀-https://www.javaxiu.com/3191.html

文章源自JAVA秀-https://www.javaxiu.com/3191.html

欢迎加入我的知识星球,一起探讨架构,交流源码。加入方式,长按下方二维码噢文章源自JAVA秀-https://www.javaxiu.com/3191.html

面试:如何从 100 亿 URL 中找出相同的 URL?文章源自JAVA秀-https://www.javaxiu.com/3191.html

已在知识星球更新源码解析如下:文章源自JAVA秀-https://www.javaxiu.com/3191.html

面试:如何从 100 亿 URL 中找出相同的 URL?文章源自JAVA秀-https://www.javaxiu.com/3191.html

面试:如何从 100 亿 URL 中找出相同的 URL?文章源自JAVA秀-https://www.javaxiu.com/3191.html

面试:如何从 100 亿 URL 中找出相同的 URL?文章源自JAVA秀-https://www.javaxiu.com/3191.html

面试:如何从 100 亿 URL 中找出相同的 URL?文章源自JAVA秀-https://www.javaxiu.com/3191.html

最近更新《芋道 SpringBoot 2.X 入门》系列,已经 20 余篇,覆盖了 MyBatis、Redis、MongoDB、ES、分库分表、读写分离、SpringMVC、Webflux、权限、WebSocket、Dubbo、RabbitMQ、RocketMQ、Kafka、性能测试等等内容。文章源自JAVA秀-https://www.javaxiu.com/3191.html

提供近 3W 行代码的 SpringBoot 示例,以及超 4W 行代码的电商微服务项目。文章源自JAVA秀-https://www.javaxiu.com/3191.html

获取方式:点“在看”,关注公众号并回复 666 领取,更多内容陆续奉上。文章源自JAVA秀-https://www.javaxiu.com/3191.html

文章源自JAVA秀-https://www.javaxiu.com/3191.html

文章有帮助的话,在看,转发吧。谢谢支持哟 (*^__^*)
文章源自JAVA秀-https://www.javaxiu.com/3191.html

阅读原文文章源自JAVA秀-https://www.javaxiu.com/3191.html

继续阅读
速蛙云 - 极致体验,强烈推荐!!!购买套餐就免费送各大视频网站会员!快速稳定、独家福利社、流媒体稳定解锁!速度快,全球上网、视频、游戏加速、独立IP均支持!基础套餐性价比很高!这里不多说,我一直正在使用,推荐购买:https://www.javaxiu.com/59919.html
weinxin
资源分享QQ群
本站是JAVA秀团队的技术分享社区, 会经常分享资源和教程; 分享的时代, 请别再沉默!
沙海
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定