"Самая быстрая" хеш-функция реализована в Java, сравнивая часть файла
Мне нужно сравнить два разных файла экземпляра "Файл" в Java и хочу сделать это с помощью быстрой функции хеширования.
Идея: - Хэширование 20 первых строк в файле 1 - Хэширование 20 первых строк в файле 2 - Сравнить два хэша и вернуть true, если они равны.
Я хочу использовать самую быструю хэш-функцию, когда-либо реализованную в Java. Какой из них вы бы выбрали?
2 ответа
Если вы хотите скорость, не хэшируйте! Особенно не криптографический хеш, как MD5. Эти хэши разработаны так, чтобы их нельзя было перевернуть, а не быстро вычислить. То, что вы должны использовать, это контрольная сумма - смотрите java.util.zip.Checksum и две его конкретные реализации. Adler32 очень быстро вычисляет.
Любой метод, основанный на контрольных суммах или хэшах, уязвим для коллизий, но вы можете минимизировать риск, используя два разных метода, как это делает RSYNC.
Алгоритм в основном:
- Проверьте размеры файлов равны
- Разбейте файлы на куски размером N байтов
- Вычислить контрольную сумму на каждой паре совпадающих блоков и сравнить. Любые различия доказывают, что файлы не совпадают.
Это позволяет раннее обнаружение разницы. Вы можете улучшить его, вычислив две контрольные суммы одновременно с разными алгоритмами или разными размерами блоков.
Чем больше битов в результате, тем меньше вероятность столкновения, но как только вы превысите 64 бита, вы выйдете за пределы того, что Java (и ЦП компьютера) может обрабатывать изначально, и, следовательно, работать медленнее, поэтому FNV-1024 с меньшей вероятностью даст вам ложный минус, но гораздо медленнее.
Если все дело в скорости, просто используйте Adler32 и признайте, что очень редко разница не будет обнаружена. Это действительно редко. Подобные контрольные суммы используются, чтобы гарантировать, что Интернет может обнаружить ошибки передачи, и как часто вы получаете неправильные данные?
На самом деле все зависит от точности, вам придется сравнивать каждый байт. Ничто другое не будет работать.
Если вы можете пойти на компромисс между скоростью и точностью, существует множество вариантов.
Если вы сравниваете два файла одновременно в одной и той же системе, нет необходимости хэшировать их оба. Просто сравните байты в обоих файлах равны, как вы читаете оба. Если вы хотите сравнить их в разное время или в разных местах, MD5 будет быстрым и адекватным. Нет особой причины нуждаться в более быстром, если вы не имеете дело с действительно большими файлами. Даже мой ноутбук может хэшировать сотни мегабайт в секунду.
Вам также нужно хэшировать весь файл, если вы хотите убедиться, что они идентичны. В противном случае вы можете просто проверить размер и время последнего изменения, если вы хотите действительно быструю проверку. Вы также можете проверить начало и конец файла, если они просто очень большие, и вы уверены, что середина не изменится. Если вы не имеете дело с сотнями мегабайт, вы можете также проверить каждый байт каждого файла.