algorithm - 在大文件中查找重复项

Question

我的文件非常大，大约有 1500 万个条目。文件中的每一行都包含一个字符串(称之为键)。

我需要使用 java 查找文件中的重复项。我尝试使用 HashMap 并检测重复条目。显然，这种方法给我带来了“java.lang.OutOfMemoryError:Java 堆空间”错误。

我该如何解决这个问题？

我想我可以增加堆空间并尝试一下，但我想知道是否有更高效的解决方案而无需调整堆空间。

Answer 1

关键是你的数据不适合内存。您可以使用 external merge sort为此:

将您的文件分成多个适合内存的小块。对每个 block 进行排序，消除重复项(现在是相邻元素)。

合并 block 并在合并时再次消除重复项。由于您将在此处进行 n-nway 合并，因此您可以将每个 block 的下一个 k 元素保留在内存中，一旦 block 的项目耗尽(它们已经合并)从磁盘中获取更多元素。