65

问答题 65 /69

给两个文件,分别有100亿个query,我们只有1G内存,如何找到两个文件交集?分别给出精确 算法和近似算法?

参考答案

精确算法:Hash分桶法
• 将两个文件中的query hash到N个小文件中,并标明query的来源
• 在各个小文件中找到重合的query
• 将找到的重合query汇总 近似算法:BloomFilter