Java-怎样在两个1G的大文件中查找出重复的条目

Question

两个1G左右的文件，文件中每行记录一个地址，现在想查找两个文件中重复的地址条目，有什么较好的方法吗？

Answer 1

可以用java调用shell，先从第一个文件读出若干行，再从第二个文件读出相同的行数，将从两个文件读出的内容逐行进行比对，一直将第二个文件读完，循环这个过程直至比对完成。

Answer 2

"若是纯数字的话，且值均小于2^32-1，可以构造一个大数组array(int[Integer.SIZE],1G的数据足够保存)，初始值为0."
--> 这里我们不用int数组, 而用 位图(bitmap)的 概念, 即用一个bit来表示对应的整数有没有出现过(注意我们不需要 计算重复此数, 只须知道有重复即可), 一个文件的bitmap: array(byte[Integer.MAX_VALUE/8]) = 256M. 下面的算法 和newcomer给出的差不多, 不多说了.
如果题中的"地址"指的是web地址, 就更方便了, 还是用hash. 我们来算一下, 假定一个url地址长度为30个字节(不算多吧), 那么一个文件差不多有30M 条记录. 每条记录hash到16字节, 因为hash空间足够大(2的128次方, 10的38次方级). 基本不用考虑碰撞了. 这样hash后结果为480m.

最后要说的是, 如果内存够大, 就把两个文件都做bitmap或hash后存入内存; 否则只保存一个文件的hash在内存, 顺序读出另一个文件条目, 与内存中的hash做比较.(类似Oracle的Hash Join).

Answer 3

简单想了一下,感觉这样应该可行:
方便说明, 用A,B表示两个文件吧
用先遍历一遍A, Hash一把,把Hash到一起的放在一个文件里(比如有:产生了10000个文件), 文件内容标识一下: A:{原始内容}:行数

然后再遍历B, 同样的Hash, 类似处理, 只是内容标识修改为:B:{原始内容}:行数

然后依次遍历新产生的N个文件, 用大不了用HashMap搞定(当然Hash时做的足够好, 每个文件都比较小了)

Answer 4

上面的方法我觉得可能会有内存上的问题，如果高性能机肯定没问题。我说的也是使用Hash算法，使用Hash算法将上面的两个文件中的内容分隔成小的文件，然后再对每对小文件进行重复计算

Answer 5

地址是纯数字记录的还是其他？

若是纯数字的话，且值均小于2^32-1，可以构造一个大数组array(int[Integer.SIZE],1G的数据足够保存)，初始值为0.
首先遍历文件1:对于每次读取的地址，将数组对应位置的值增一。如地址为k，则array[k]++;

然后再遍历文件2：对每次读取的地址，判断数组中对应位置的值是否为零，即array[k]==0?若不为零，则说明文件1中存在该地址值。

要么就大文件排序，然后用归并去找重。

Answer 6

可以试试用哈希函数把每行记录转成数值，最后比较两个文件中有没有相同的数值。不过要注意碰撞问题。