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

Given two files A and B, each containing 5 billion URLs (64 bytes each), with only 4GB memory, find the URLs common to both files.

题目类型: 技术面试题

这是一道技术面试题，常见于澳洲IT公司面试中。

难度: hard

分类: 大数据处理, 哈希分治, 集合求交

标签: Hash Partition, Divide and Conquer, Hash Set, Bloom Filter

参考答案摘要

核心答案 由于文件规模远超内存限制，无法整体载入。可用 分而治之 + Hash 分桶 ，或允许误差时用 Bloom Filter 。 方案1（分桶求交，精确） 估计每个文件大小约为 50亿 × 64B ≈ 320GB ，远大于 4GB，不能全量加载。 遍历文件a，对每个URL计算 hash(url)%1000 ，写入1000个小文件（a0...a999），每个约300MB。 遍历文件b，同样方式分...

本题提供 STAR 原则详细解答和技术解析，登录匠人学院学习中心即可查看完整答案。