这不是面试题，这是真事

Question

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大文件亿

Answer 1

先桶排序遍历一遍：第二列小于1w的，放到文件1中；小于10w的放到文件2中，以此类推。
然后多线程处理各个桶文件1到n，每个线程的处理逻辑：
1. 使用Map<Integer,Integer> map存储，键为第二列值，value为所在文件的行编号；
2. 遍历记录，若map.get(第二列值)非空，则将此key-value记录到另外一个map2中；否则记录到map中。嗯，暂时想这么多了，如果在某个数值范围内的记录特别多，可以细化桶内数量级，比如1千1千的递增，甚至1百1百递增来划分桶。

Answer 2

典型的mapreduce问题，单机的话也只有分割成小文件，然后多线程同时处理，内存的问题只要设计好了，应该不需要把所有的LONG全部new出来，数据结构和算法好的同学可以给点建议

Answer 3

如果走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分钟内应该能完成

Answer 4

这个想法不错multiway-mergesort属于数据库应用里做sort的基本算法