有两个文件，分别有20亿个QQ号（bigint类型，8字节）

[问答题]

有两个文件，分别有20亿个QQ号（bigint类型，8字节），我们只有2G内存，如何找到两个文件交集？

牛客840735377号

步骤1:使用hash函数将第一个文件的所有整数映射到1000个文件中，每个文件有2000万个整数，大约160M内存，2G的内存就可以放下了，把1000个文件记为a1,a2....a10000;

步骤2：用同样的hash函数映射第二个文件到1000个文件中，这1000个文件记为b1,b2,b3......b1000；

步骤3：由于使用的是相同的hash函数，所以两个文件中一样的数字会被分配到文件下标一致的文件中，分别对a1和b1求交集，a2和b2求交集，ai和bi求交集l；

步骤4：最后将步骤3的结果汇总，即为两个文件的交集。

发表于 2021-01-23 20:47:32 回复(0)

牛客6107965号

<p>使用bitmap</p>

发表于 2021-01-22 23:01:08 回复(0)

提交观点

问题信息

阅文集团 2021 大数据开发工程师

来自：2023届阅文大数据方...

上传者：小小

难度：

2条回答 31收藏 2301浏览

扫一扫，把题目装进口袋