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

Given two files a and b, each containing 5 billion URLs (each URL is 64 bytes), with a 4GB memory limit, how do you find the common URLs between a and b?

题目类型: 技术面试题

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

难度: hard

分类: 大数据处理, 海量数据, 文件处理

标签: hash partition, divide and conquer, external memory, set intersection

参考答案摘要

核心答案 由于每个文件约为 320GB （远超 4GB 内存），无法整体载入内存，因此采用 分治 + 哈希分桶 来求交集。 Step 1：分桶拆分文件 a 遍历文件 a，对每个 URL 计算 hash(url) % 1000 ，按结果写入 1000 个小文件： a0, a1, ..., a999 ，每个约 300MB。 Step 2：分桶拆分文件 b 同样遍历文件 b，按 hash(url) % ...

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