Быстрее альтернатива MD5?

Я работаю над программой, которая ищет все диски для данного файла. На данный момент я вычисляю хэш MD5 для известного файла и затем рекурсивно сканирую все файлы, ища совпадение.

Единственная проблема заключается в том, что MD5 мучительно медленен в больших файлах. Есть ли более быстрая альтернатива, которую я могу использовать, сохраняя при этом очень небольшую вероятность ложных срабатываний?

Весь код находится на С#.

Спасибо.

Обновление

Я читал, что даже 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 "";
        }

Ответ 1

Я надеюсь, что вы проверяете соответствие MD5, только если размер файла уже соответствует.

Другая оптимизация - сделать быструю контрольную сумму первого 1K (или какого-либо другого произвольного, но достаточно маленького числа) и убедиться, что они совпадают, прежде чем работать со всем файлом.

Конечно, все это предполагает, что вы просто ищете решение match/nomatch для определенного файла.

Ответ 2

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

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

Ответ 3

Сначала рассмотрим, что на самом деле является вашим узким местом: сама хэш-функция или, скорее, скорость доступа к диску? Если вы ограничены диском, изменение алгоритма хэширования не даст вам многого. Из вашего описания я подразумеваю, что вы всегда просматриваете весь диск, чтобы найти совпадение - сначала создайте индекс, а затем только сопоставьте данный хэш с индексом, это будет намного быстрее.

Ответ 4

просто читайте файл линейно? Кажется, совершенно бессмысленно читать весь файл, вычислять хеш md5, а затем сравнивать хэш.

Чтение файла последовательно, несколько байтов за раз, позволит вам отбросить подавляющее большинство файлов после чтения, скажем, 4 байта. И вы сохраните все накладные расходы на обработку вычислительной функции хэширования, которая не даст вам ничего в вашем случае.

Если у вас уже есть хэши для всех файлов на диске, имеет смысл сравнить их, но если вам нужно их вычислить на лету, просто не кажется, что это преимущество для хэширования.

Я что-то упустил? Что заставляет вас хешировать в этом случае?

Ответ 5

Есть одна небольшая проблема с использованием MD5 для сравнения файлов: есть известные пары файлов, которые отличаются друг от друга, но имеют тот же MD5.

Это означает, что вы можете использовать MD5, чтобы узнать, отличны ли файлы (если MD5 отличается, файлы должны быть разными), но вы не можете использовать MD5, чтобы узнать, равны ли файлы (если файлы равны, MD5 должен быть одинаковым, но если MD5 равен, файлы могут быть или не совпадать).

Вы должны либо использовать хеш-функцию, которая еще не была сломана (например, SHA-1), либо (как упоминалось в @SoapBox) использовать MD5 только как быстрый способ найти кандидатов для более глубокого сравнения.

Литература:

http://www.win.tue.nl/hashclash/SoftIntCodeSign/

Ответ 6

Использовать 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);
            }
        }