Более быстрая альтернатива MD5?
Я работаю над программой, которая ищет целые диски для данного файла. На данный момент я вычисляю хэш MD5 для известного файла, а затем рекурсивно просматриваю все файлы в поисках совпадения.
Единственная проблема в том, что MD5 очень медленно работает с большими файлами. Есть ли более быстрая альтернатива, которую я могу использовать, сохраняя при этом очень небольшую вероятность ложных срабатываний?
Весь код написан на C#.
Спасибо.
Обновлять
Я читал, что даже MD5 может быть довольно быстрым, и что дисковый ввод-вывод должен быть ограничивающим фактором. Это наводит меня на мысль, что мой код может быть не оптимальным. Есть ли проблемы с таким подходом?
MD5 md5 = MD5.Create();
StringBuilder sb = new StringBuilder();
try
{
using (FileStream fs = File.Open(fileName, FileMode.Open, FileAccess.Read))
{
foreach (byte b in md5.ComputeHash(fs))
sb.Append(b.ToString("X2"));
}
return sb.ToString();
}
catch (Exception)
{
return "";
}
Какой смысл называть ToLower и ToUpper?
Ответы 6
просто читать файл линейно? Кажется довольно бессмысленным читать весь файл, вычислять хеш md5, а затем сравнивать хеш.
Последовательное чтение файла, по несколько байтов за раз, позволит вам отбросить подавляющее большинство файлов после чтения, скажем, 4 байтов. И вы бы сэкономили все накладные расходы на обработку вычисления хеш-функции, которая ничего вам не дает в вашем случае.
Если у вас уже есть хэши для всех файлов на диске, имеет смысл сравнить их, но если вам нужно вычислять их на лету, хеширование просто не дает никаких преимуществ.
Я что-то упустил? Что в этом случае дает вам хеширование?
К сожалению, у меня не будет доступа к исходному файлу во время работы программы, поэтому хранение хешей (на самом деле многих хешей) - единственный способ сравнения.
По крайней мере, если вы можете сохранить хэш плюс первые несколько байтов (предпочтительно больше 4, потому что часто это размер магических чисел формата файла), тогда вы можете отказаться от подавляющего большинства случаев, только открыв файл и прочитав несколько байтов.
Сначала подумайте, что на самом деле является вашим узким местом: сама хеш-функция или, скорее, скорость доступа к диску? Если вы ограничены диском, изменение алгоритма хеширования мало что вам даст. Из вашего описания я подразумеваю, что вы всегда сканируете весь диск, чтобы найти совпадение - сначала подумайте о создании индекса, а затем сопоставьте только заданный хэш с индексом, это будет намного быстрее.
Надеюсь, вы проверяете совпадение MD5 только в том случае, если размер файла уже совпадает.
Другая оптимизация заключается в том, чтобы быстро вычислить контрольную сумму первой 1 КБ (или другого произвольного, но достаточно небольшого числа) и убедиться, что они совпадают, прежде чем работать со всем файлом.
Конечно, все это предполагает, что вы просто ищете совпадение / совпадение для определенного файла.
+1 за срез. Не нужно хешировать 37 гигов, когда первый байт другой.
Есть одна небольшая проблема с использованием MD5 для сравнения файлов: есть известные пары файлов, которые имеют разные, но имеют такой же MD5.
Это означает, что вы можете использовать MD5, чтобы определить, являются ли файлы разные (если MD5 отличается, файлы должны быть разными), но вы не можете использовать MD5, чтобы определить, являются ли файлы равный (если файлы равны, MD5 должен быть то же самое, но если MD5 равны, файлы могут быть или не быть равными).
Вы должны либо использовать хэш-функцию, которая еще не была нарушена (например, SHA-1), либо (как упоминалось в @SoapBox) использовать MD5 только как быстрый способ найти кандидатов для более глубокого сравнения.
Использованная литература:
Верно, но это относится к хешированию в целом. Когда длина хэша равна n битам, есть только 2 ^ n возможных значений хэша. Но количество разных файлов бесконечно счетно. Таким образом, количество пар разных файлов, имеющих одинаковое хеш-значение, также бесконечно счетно.
@Ingo: да, но для MD5 мы знаем, как создать пару файлов с одинаковым хеш-значением (не только это, но уже известно несколько таких пар). Для криптографических хэшей, которые еще не были взломаны, мы не можем создать такую пару специально, а создание ее случайно имеет крайне малую вероятность, достаточно мала, чтобы мы могли рассматривать ее, как если бы это было вообще невозможно (по крайней мере, до этого момента). хеш тоже ломается).
Его вариант использования, похоже, не касается атаки, поэтому это может не иметь значения.
Независимо от криптографических требований, существует возможность хеш-коллизии, поэтому никакая функция хеширования не может использоваться для гарантия, что два файла идентичны.
Некоторое время назад я написал аналогичный код, который мне удалось запустить довольно быстро, сначала проиндексировав все файлы и отбросив все файлы другого размера. Затем было выполнено быстрое сравнение хэшей (для части каждого файла) с оставшимися записями (сравнение байтов для этого шага оказалось менее полезным - многие типы файлов имеют общие заголовки, которые имеют идентичные байты в начале файла). Все файлы, оставшиеся после этого этапа, затем проверялись с помощью MD5 и, наконец, байтовое сравнение всего файла, если MD5 совпало, просто для того, чтобы убедиться, что содержимое было таким же.
Звучит как хороший и логичный подход - спасибо за участие.
Используйте MD5CryptoServiceProvider и BufferedStream
using (FileStream stream = File.OpenRead(filePath))
{
using (var bufferedStream = new BufferedStream(stream, 1024 * 32))
{
var sha = new MD5CryptoServiceProvider();
byte[] checksum = sha.ComputeHash(bufferedStream);
return BitConverter.ToString(checksum).Replace("-", String.Empty);
}
}
-1: Это не ускоряет процесс. Чтобы сделать это быстрее, будет работать только пятилетний, принятый и высоко оцененный ответ.
Вместо использования .ToString ("x2") используйте blogs.msdn.com/b/blambert/archive/2009/02/22/…, что сэкономит вам время.