Заданный список имен файлов, возврат списка списков файлов с одинаковым содержанием - вопрос интервью

Question

Вам дан список имен файлов, и вам нужно вернуть список, что каждый элемент в нем является списком с файлами, имеющими одинаковое содержимое.Также важно отметить, что эти файлы имеют очень большой размер.

Например:
Если мы получили список {"file1", "file2", "file3", "file4", "file5"} в качестве входных данных, и мы знаем, что file1.content()==file2.content()==file3.content, file4.content==file5.content(), file3.content()!=file4.content(), то результат должен быть:
{{"file1", "file2", "file3"}, {"file4", "file5"}}.

Я сказал интервьюеру, что мы можем создать HashMap, который хэширует файлы по их sha512 хэш-коду.Затем мы можем перебирать ключи на карте, для каждого ключа мы перебираем список, сопоставленный с ним, для сравнения пар файлов в списке (для проверки того, что действительно каждая пара файлов имеет одинаковое содержимое).

Единственная проблема, которая у меня возникла с этим решением, заключается в том, что я не возвращал список списков, как упомянуто выше, а только пары дубликатов файлов.Это означает, что для примера выше - я вернул это:
{{"file1", "file2"}, {"file2", "file3"}, {"file4", "file5"}}.

Я просто не нашел эффективного способа создания требуемого вывода.
В приведенном выше примере мой HashMap потенциально (хотя и не очень) может иметь только один ключ, который сопоставлен со всемивходные файлы.
Для подобных сценариев я не смог найти алгоритм для возврата нужного списка при последнем сравнении O(n^2) (n - количество файлов в списке).

Есть ли у вас эффективный способ вернуть желаемый список, учитывая, что у вас уже есть HashMap из sha512 ключей, сопоставленных со списком файлов с этим 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, маловероятно, что они будут разными.Но если вы хотите быть уверены, вы должны сравнить каждый файл, побайтово с другими файлами.

Answer 2

Существует некоторая эвристика при сравнении файлов перед хэшированием, как указано в комментариях (например, проверка файлов по размеру файла).Кстати, если дан хеш каждого файла, вы можете сортировать хеш-файлы (в O (n log (n)), а также перебирать хэши и разбивать файлы на блоки (в O (n)). Следовательно, он можетбыть сделано в O (n log (n)) в худшем случае.