如何高效的进行大数据量比对

最近讨论到一个问题：
A、B两个文本文件里面都有手机号，A文件是千万甚至上亿行，B文件是上百万行，如何高效的将A文件手机号存在于B文件中有的提取出来？

比较常见的答案：
1、将文件导入数据库，用一条SQL解决，类似select * from A where num in (select distinct num from B)
2、将B文件号码按条取出，通过类似grep脚本逐个过滤A文件

这些由于涉及数据的导入导出、数据库查询机制、文件的多次遍历因素的影响，都不是最佳方案。

要想效率到极致，主要考虑两个方面：
1、A和B文件只能遍历一次
2、查询号码是否存在的效率一定要高，且复杂度应该为常数，而不是线性甚至指数

记得很久之前，在网上看到一篇文章介绍google在GMAIL中如何解决海量垃圾邮件名单的问题，大致是初始化一个很大的文件，将邮件地址摘要化（例如MD5），使用摘要作为文件偏移量，在文件对应位置写入标识，用一个bit代表一个邮件地址；查询的话也是先计算摘要，再通过摘要直接读取文件对应文字看有否标识，这样的话就解决了每次可以快速查询邮件列表是否是黑名单，且查询复杂度为常数；如果不同的邮件地址出现了相同的摘要会出现误判（虽然这个概率很低很低），但误判的邮件地址用户发现后可以选择加入白名单，白名单的数量从理论上来说就是很少很少的，查询效率有保障。

基于这个思路，我们可以考虑使用手机号码作为偏移量，直接在文件或内存中建立一个结构；现在号段是13、14、15、18，号码最大差值是6*10^9，如果用1 bit代表一个号码，只需要6*10^9 / 1024 / 1024 / 8 = 716MB，放在内存里面也不多，比磁盘效率高百倍！再来，还可以按1x号段来建立多个标识串，比如13、14、15、18分别1个，就只需要大概477MB内存；甚至还可以细分到1XX号段。

软硬件环境：Lenovo X230，i5-3320M CPU@2.6GHz，12GB RAM，日立7200转500G缓存32M硬盘（HTS725050A7E630），64位WIN7
开发环境：Microsoft Visual Studio 2008，C++，64位编译
测试文件：A文件有3000万手机号码，380MB；B文件有150万手机号码，19MB；随机产生的，可能有少量重复
测试结果（DEBUG模式）：内存消耗约750MB；遍历B文件初始化数据结构耗时2秒；遍历A文件中B文件有的号码，保存到C文件耗时42秒，大小约196K，有1万5千多个号码。

一次遍历和高效查询，确保了结果也是很高效的！

测试代码猛击这里下载