大文本重复数据

Question

比如a文件和b文件都是手机号码。一行一个。我要找出两个文件合并一起的重复号码。2个文件都有百万级数据。用java实现怎么做效率更好。更快。

Answer 1

发一个相同案例：

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

方案1：可以估计每个文件安的大小为5G×64=320G，远远大于内存限制的4G。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。

遍历文件a，对每个url求取hash(url)%1000，然后根据所取得的值将url分别存储到1000个小文件（记为a0,a1,...,a999）中。这样每个小文件的大约为300M。

遍历文件b，采取和a相同的方式将url分别存储到1000小文件（记为b0,b1,...,b999）。这样处理后，所有可能相同的url都在对应的小文件（a0vsb0,a1vsb1,...,a999vsb999）中，不对应的小文件不可能有相同的url。然后我们只要求出1000对小文件中相同的url即可。

求每对小文件中相同的url时，可以把其中一个小文件的url存储到hash_set中。然后遍历另一个小文件的每个url，看其是否在刚才构建的hash_set中，如果是，那么就是共同的url，存到文件里面就可以了。

方案2：如果允许有一定的错误率，可以使用Bloom filter，4G内存大概可以表示340亿bit。将其中一个文件中的url使用Bloom filter映射为这340亿bit，然后挨个读取另外一个文件的url，检查是否与Bloom filter，如果是，那么该url应该是共同的url（注意会有一定的错误率）。

Answer 2

只是百万级别的话，用下面作法应该是效率最快的了。

1，声明一个下标千万级的数组
2，顺序读第一个和第二个文件
3，数组下标和电话号码相同的数组元素 + 1
4, 遍历数组，输出所有元素值大于1的下标

千万级byte数组也占用不了多少内存。
只需要读2次文件，循环一次数组。
没有比数组下标访问更快的了。

Answer 3

我觉得应该是这样的，但不一定高效哈，把两个文件中的数据读入到两个list中比较，找出重复的即可。
希望对立有帮助，

Answer 4

若考虑到内存不够的情况，可以使用磁盘做中间存储

（1）创建一个文件，如：filehashMap.text 作用相当于存储在磁盘上的hashMap
每行的存储内容为 phoneNumber(电话号码) count(出现次数)
（2）顺序读入a和b中的每个电话号码
（3）对每个电话号码hash取hash值，然后根据mod / （（a的行数+b的行数）* 1.25） ，取得该记录要写入到的filehashMap.txt里的行数，若改行不为空则比较改行的phoneNumber是否为当前的phoneNumber，若是将该行的count + 1，若为空行时则写入正处理的phoneNumber， count置1（处理冲突才有二次散列的方式）
（4）filehashMap.text中 count字段大于1的，即为重复的电话号码

Answer 5

几百万条数据，由于只是电话号码，每行号码不过是几十个字节，一百万行也只是占用几十兆内存而已，数据量不大，还是好办的。

可以在内存里面开一个HashMap，把一个文件的所有数据放进去，然后逐行遍历另外一个文件，能够在HashMap里面找到的数据，就是重复号码。

当然，还有比较偷懒的办法，就是在数据库里面开两个临时表，然后求交集intersect，但是效率嘛……就不好说了。

Answer 6

这个用代码比较高效吧，HashMap的效率还是可以的

Answer 7

问题 没有说清 对内存的要求和 存储可用环境。

如果对内存要求高，使用文件归并算法。
如果对内存要求不高，使用treemap或者hashmap就可以了。

Answer 8

采取key-value的存储结构
内存不够大就分而治之，
一个大文件你逐行读取，取hash ，相同hash 的写入到另外一个文件，新写的文件控制大小
然后对生成的小文件统计，合并结果。
应该就可以了