如何快速找到两个几乎相同的文件之间的差异？

Question

如果您有两个主要相同的文件,其中包含1000条记录,您将如何编写代码来查找它们之间的差异.假设不允许使用unix/linux命令.

我的想法:

因为大多数条目都是相同的,所以我们可以对这两个文件的条目进行排序,然后逐个比较每个条目,例如file1中的条目i与file2中的条目i相比较.它是O(n lg n),n是文件的大小.

有O(n)解决方案吗？

Answer 1

哈希表是你的朋友。

1. 从文件 1 中获取一条记录。
2. 散列它。
3. 获取对应的内存地址。
4. 将其设置为1.
5. 对文件 1 中的所有记录重复此操作。
6. 对文件 2 中的所有记录重复此操作，但添加 2 而不是设置为 1。

现在您知道哪条记录存在于两个文件中（值 3），哪条记录仅存在于第一个文件中（值 1），哪条记录仅存在于第二个文件中（值 2）。并且在线性时间内。

注意：如果您要实现自己的哈希表，则必须根据需要处理表大小的增长以及冲突。我确信如果你能做到这一点，那么你就不会很难解决这个问题，所以使用图书馆。