这不是面试题，这是真事

iteye上没人鸟，试试这边的深浅 
我有一个文件，一共100列，每个列以 tab 分开，第二列是一个 15位 的整数（此列是乱序的） 
文件行数在2亿行之内，文件很大，大约 50G 左右。现在要求我找出 满足这种条件的行：第二列的整数，在此文件中，出现过2次或2次以上 

有啥好办法嘛？ 
我现在这么搞的：将文件尽量分成小文件（保证同样的数字分到同一个小文件中），使得此文件可以整个load到内存中。然后对内存中的数据使用set看是否曾经重复出现过 
根据最后一位的值（0, 1, ..., 9），分成10个child文件。如果某个child文件还大于512M（我JVM内存比512大一点点，可以load整个文件），在根据第二位再分割此child文件，得到 grandchild文件；如果grandchild文件还是大于512M，则根据第三位分割...... 


缺点：太耗时，以至于不现实，要1个多小时 

PS：我将 JVM 最大heap设为 1024M，然后，测试将Long加入到set中，发现，可以创建 1700W个Long对象（Integer对象也是这么多）。到production环境中，我估计heap可以设置到8G，但是，即使这样，也只有1.6亿的Long（或者Integer），所以，肯定还是不能够读入所有的 整数，然后使用set判断哪个曾经出现过2次或2次以上 

各位，有好办法嘛？我只要知道哪些整数曾经出现过2次或2次以上即可（分不分文件、出现的确切次数 我都不在乎） 

另外：不要建议分布式啥的，这个也用不起来，我这就是一个 standalone 的应用 内存 JVM 大文件 亿 --------------------编程问答-------------------- 先桶排序遍历一遍：第二列小于1w的，放到文件1中；小于10w的放到文件2中，以此类推。
然后多线程处理各个桶文件1到n，每个线程的处理逻辑：
1. 使用Map<Integer,Integer> map存储，键为第二列值，value为所在文件的行编号；
2. 遍历记录，若map.get(第二列值)非空，则将此key-value记录到另外一个map2中；否则记录到map中。

嗯，暂时想这么多了，如果在某个数值范围内的记录特别多，可以细化桶内数量级，比如1千1千的递增，甚至1百1百递增来划分桶。
--------------------编程问答-------------------- 典型的mapreduce问题，单机的话也只有分割成小文件，然后多线程同时处理，内存的问题只要设计好了，应该不需要把所有的LONG全部new出来，数据结构和算法好的同学可以给点建议 --------------------编程问答-------------------- 从你这个文件去读一行 对第二列 哈希%N   （N是你要分割后的文件数），然后写入对应文件，写入时对文件扫描插入合适位置，比如3   文件内已存在1-2-4，插入后应是1-2-3-4， 这样如果有重复在你扫描过程就会发现 --------------------编程问答-------------------- 如果走Hash的思路，用trove的TLongSet，不需要创建Long，直接用long，production 8G内存应该就够了。

另一种思路是MergeSort，当你内存真的不够用的时候
1. 尽量多地读取源文件至long[]（位于内存），对其进行排序，将结果输出到另一个文件，此文件只有long数据（binary format）
2. 依次循环，直到你创建了很多只有数字的文件，姑且叫它们LF（long file）。按你的512MB内存计算，这样的文件大约只有4个
3. 打开所有的LF（不是读入内存），对其进行multiway-mergesort（为提高性能，给每个LF分配尽量多的缓存），然后你一边排序就能一边输出数字了，经过最后mergesort排序的数字可以直接扔掉

这个算法重点是第一步，每一个LF输出的已经是经过排序的数字（并不要急于在这一步输出重复的数，一是会重复输出，二是多了一次遍历，浪费时间，反正第三步都能解决）
效率基本就是你读入50GB+读写1.6Gb整数+输出结果的时间，20分钟内应该能完成 --------------------编程问答--------------------

引用 4 楼 lcf 的回复:

如果走Hash的思路，用trove的TLongSet，不需要创建Long，直接用long，production 8G内存应该就够了。

另一种思路是MergeSort，当你内存真的不够用的时候
1. 尽量多地读取源文件至long[]（位于内存），对其进行排序，将结果输出到另一个文件，此文件只有long数据（binary format）
2. 依次循环，直到你创建了很多只有数字的文件，姑且叫它们LF（long file）。按你的512MB内存计算，这样的文件大约只有4个
3. 打开所有的LF（不是读入内存），对其进行multiway-mergesort（为提高性能，给每个LF分配尽量多的缓存），然后你一边排序就能一边输出数字了，经过最后mergesort排序的数字可以直接扔掉

这个算法重点是第一步，每一个LF输出的已经是经过排序的数字（并不要急于在这一步输出重复的数，一是会重复输出，二是多了一次遍历，浪费时间，反正第三步都能解决）
效率基本就是你读入50GB+读写1.6Gb整数+输出结果的时间，20分钟内应该能完成

这个想法不错 --------------------编程问答-------------------- 不行   不会 --------------------编程问答-------------------- --------------------编程问答-------------------- --------------------编程问答--------------------

引用 5 楼 iceman1952 的回复:

Quote: 引用 4 楼 lcf 的回复:

如果走Hash的思路，用trove的TLongSet，不需要创建Long，直接用long，production 8G内存应该就够了。

另一种思路是MergeSort，当你内存真的不够用的时候
1. 尽量多地读取源文件至long[]（位于内存），对其进行排序，将结果输出到另一个文件，此文件只有long数据（binary format）
2. 依次循环，直到你创建了很多只有数字的文件，姑且叫它们LF（long file）。按你的512MB内存计算，这样的文件大约只有4个
3. 打开所有的LF（不是读入内存），对其进行multiway-mergesort（为提高性能，给每个LF分配尽量多的缓存），然后你一边排序就能一边输出数字了，经过最后mergesort排序的数字可以直接扔掉

这个算法重点是第一步，每一个LF输出的已经是经过排序的数字（并不要急于在这一步输出重复的数，一是会重复输出，二是多了一次遍历，浪费时间，反正第三步都能解决）
效率基本就是你读入50GB+读写1.6Gb整数+输出结果的时间，20分钟内应该能完成

这个想法不错

multiway-mergesort属于数据库应用里做sort的基本算法

补充：Java ,  Java SE