algorithm - 给定文件名列表，返回具有相同内容的文件列表列表 - 面试题

Question

你得到一个文件名列表，需要返回一个列表，其中的每个项目都是一个包含具有相同内容的文件的列表。同样重要的是，这些文件的尺寸非常大。

例如:
如果我们得到列表 {"file1", "file2", "file3", "file4", "file5"} 作为输入，我们知道 file1.content()== file2.content()==file3.content, file4.content==file5.content(), file3.content()!=file4.content() ，所以输出应该是:
{{“文件 1”、“文件 2”、“文件 3”}、{“文件 4”、“文件 5”}}。

我对面试官说，我们可以创建 HashMap，通过它们的 sha512 哈希码对文件进行哈希处理。然后我们可以遍历映射中的键，对于每个键，我们遍历映射到它的列表以比较列表中的文件对(用于检查确实每对文件具有相同的内容)。

我在这个解决方案中遇到的唯一问题是，我没有像上面提到的那样返回列表列表，而只是成对的重复文件。这意味着，对于上面的例子——我返回了这个:
{{“文件 1”、“文件 2”}、{“文件 2”、“文件 3”}、{“文件 4”、“文件 5”}}。

我只是没有找到创建所需输出的有效方法。
对于上面的示例，我的 HashMap 可能(尽管不太可能)只有一个映射到所有输入文件的键。
对于像这样的场景，我找不到一种算法来在最后返回所需的列表而不是 O(n^2) 比较(n 是文件中的文件数列表)。

假设您已经将 sha512 键的 HashMap 映射到具有该 sha512 哈希码的文件列表，您是否有返回所需列表的有效方法？

Answer 1

所以你有文件:“file1”到“file5”。假设您为每个计算 sha512，最后得到的结果是:

 Name                SHA512
file1   000102030405060708090A0B0C0D0E0F000102030405060708090A0B0C0D0E0F
file2   0123456789ABCDEFFEDCBA98765432101963DEADBEEFF00BA977345417B00BE5
file3   000102030405060708090A0B0C0D0E0F000102030405060708090A0B0C0D0E0F
file4   0123456789ABCDEFFEDCBA98765432101963DEADBEEFF00BA977345417B00BE5
file5   000102030405060708090A0B0C0D0E0F000102030405060708090A0B0C0D0E0F

如果按 SHA512 对列表进行排序，您有:

file1   000102030405060708090A0B0C0D0E0F000102030405060708090A0B0C0D0E0F
file3   000102030405060708090A0B0C0D0E0F000102030405060708090A0B0C0D0E0F
file5   000102030405060708090A0B0C0D0E0F000102030405060708090A0B0C0D0E0F
file2   0123456789ABCDEFFEDCBA98765432101963DEADBEEFF00BA977345417B00BE5
file4   0123456789ABCDEFFEDCBA98765432101963DEADBEEFF00BA977345417B00BE5

列表中的文件现在按哈希值分组。遍历列表并输出组是一件微不足道的事情。

正如 OP 在评论中指出的那样，不能保证具有相同 SHA512 哈希值的两个文件具有相同的内容。因此，在按哈希对文件进行分组后，您必须将每个文件与另一个文件进行比较。

或者，您可以使用 MD5 作为初始哈希值，并通过文件的 MD5 哈希值将文件分组在一起。然后，对于具有相同 MD5 哈希值的文件，计算 SHA512 哈希值。如果两个文件具有相同的 MD5 哈希值和相同的 SHA512 哈希值，则它们不同的可能性很小。但是，如果您想确定，就必须将每个文件逐字节与其他文件进行比较。