Какой самый быстрый алгоритм хеширования, чтобы проверить, равны ли два файла?

Question

Какой самый быстрый способ создать хеш-функцию, которая будет использоваться для проверки, равны ли два файла?

Безопасность не очень важна.

Редактировать: я отправляю файл по сетевому соединению и буду уверен, что файл с обеих сторон равен

Answer 1

Если вы не используете действительно сложный и / или медленный хеш, загрузка данных с диска займет намного больше времени, чем вычисление хеша (если вы не используете RAM-диски или топовые SSD).

Чтобы сравнить два файла, используйте этот алгоритм:

• Сравнить размеры
• Сравните даты (будьте осторожны: это может дать вам неправильный ответ; вы должны проверить, так ли это для вас или нет)
• Сравните хэши

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

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

Answer 2

Одним из подходов может быть использование простого алгоритма CRC-32, и только если значения CRC сравниваются равными, перезапустите хэш с SHA1 или чем-то более надежным. Быстрый CRC-32 превзойдет криптографически безопасный хэш в любой день.

Answer 3

xxhash заявляет о себе как о достаточно быстром и сильном, с точки зрения столкновения:

http://cyan4973.github.io/xxHash/

Существует 64-разрядный вариант, который работает «еще быстрее» на 64-разрядных процессорах, чем 32, в целом, но медленнее на 32-разрядных процессорах (см. Рисунок).

http://code.google.com/p/crcutil также называется довольно быстрым (и использует инструкции аппаратного CRC, если они присутствуют, которые, вероятно, очень быстрые, но если у вас нет аппаратного обеспечения, которое их поддерживает, не такие быстрые). Не знаю, является ли CRC32c таким же хорошим хэшем (с точки зрения коллизий), как xxHash или нет ...

https://code.google.com/p/cityhash/ выглядит аналогично и связано с crcutil [в том смысле, что он может компилироваться для использования инструкций аппаратного CRC32c, если это указано].

Если вы «просто хотите самую быструю необработанную скорость» и вас не заботит качество случайного распределения хеш-результата (например, с небольшими наборами или где скорость имеет первостепенное значение), то упоминаются некоторые быстрые алгоритмы здесь: http://www.sanmayce.com/Fastest_Hash/ (эти «не совсем случайные» алгоритмы типа распределения в некоторых случаях являются «достаточно хорошими» и очень быстрыми). Очевидно, FNV1A_Jesteress является самым быстрым для «длинных» струн, некоторые другие, возможно, для маленьких струн. http://locklessinc.com/articles/fast_hash/ также кажется связанным. Я не исследовал, чтобы увидеть, каковы их свойства столкновения.

Answer 4

Для этого типа приложений Adler32 , вероятно, самый быстрый алгоритм с разумным уровнем безопасности. Для больших файлов вы можете рассчитать несколько хеш-значений, например, одно на блок размером 5 Мбайт файла, что снижает вероятность ошибок (т. Е. В случаях, когда хеш-коды одинаковы, но содержимое файла отличается). Кроме того, эта установка значений нескольких хешей может позволить вычисление хешей быть реализованным многопоточным способом.

Редактировать : (после замечания Стивена Судита)
Предупреждение, если файлы маленькие!
«Криптографические» свойства Adler32 или, скорее, его слабые места хорошо известны, в частности, для коротких сообщений. По этой причине следует избегать предлагаемого решения для файлов размером менее нескольких килобайт.
Тем не менее, в этом вопросе OP явно ищет быстрый алгоритм , а не заботится о безопасности . Более того, стремление к скорости может означать, что имеет дело с «большими» файлами , а не с маленькими. В этом контексте Adler32, возможно, применяемый параллельно для файловых блоков размером, скажем, 5Mb, остается очень правильным ответом. Alder32 известен своей простотой и скоростью. Кроме того, его надежность, оставаясь ниже, чем у CRC такой же длины, вполне приемлема для сообщений длиной более 4000 байтов.

Answer 5

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

Answer 6

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

Это для одноразового сравнения 2 произвольных файлов? Затем сравните размер, и после этого просто сравните файлы, побайтные (или мб на мб), если это лучше для вашего ввода-вывода.

Если это для 2 больших наборов файлов или множества наборов файлов, и это не разовое упражнение. но что-то случается часто, тогда нужно хранить хэши для каждого файла. Хеш-код никогда не бывает уникальным, но хэш с числом, скажем, 9 цифр (32 бита) был бы хорош для примерно 4-миллиардной комбинации, а 64-битное число было бы достаточно для различения 16 * 10 ^ 18 квинтиллионов различных файлов .

Приличным компромиссом было бы создание 2 32-битных хэшей для каждого файла, один для первых 8 КБ, другой для 1 МБ + 8 КБ, соединяя их вместе как одно 64-битное число. Каталогизация всех существующих файлов в БД должна быть достаточно быстрой, и поиск файла-кандидата по этой БД также должен быть очень быстрым. После совпадения единственный способ определить, совпадают ли они, - сравнить файлы целиком.

Я верю в предоставление людям того, что им нужно, что не всегда никогда не то, что они думают, что им нужно, или что хотят.

Answer 7

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

В противном случае CRC - очень простой алгоритм.

Answer 8

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

PS: Эффективность генерации хеша зависит от кодека Apache commons.

Пример использования: новый DuplicateFileFinder ("MD5"). FindDuplicateFilesList (filesList);

    import java.io.File;
    import java.io.FileInputStream;
    import java.io.IOException;
    import java.util.ArrayList;
    import java.util.Collection;
    import java.util.HashMap;
    import java.util.Iterator;
    import java.util.List;
    import java.util.Map;

    import org.apache.commons.codec.digest.DigestUtils;

    /**
     * Finds the duplicate files using md5/sha1 hashing, which is used only for the sizes which are of same size.
     *  
     * @author HemantSingh
     *
     */
    public class DuplicateFileFinder {

        private HashProvider hashProvider;
        // Used only for logging purpose.
        private String hashingAlgo;

        public DuplicateFileFinder(String hashingAlgo) {
            this.hashingAlgo = hashingAlgo;
            if ("SHA1".equalsIgnoreCase(hashingAlgo)) {
                hashProvider = new Sha1HashProvider();
            } else if ("MD5".equalsIgnoreCase(hashingAlgo)) {
                hashProvider = new Md5HashProvider();
            } else {
                throw new RuntimeException("Unsupported hashing algorithm:" + hashingAlgo + " Please use either SHA1 or MD5.");
            }
        }

        /**
         * This API returns the list of duplicate files reference.
         * 
         * @param files
         *            - List of all the files which we need to check for duplicates.
         * @return It returns the list which contains list of duplicate files for
         *         e.g. if a file a.JPG have 3 copies then first element in the list
         *         will be list with three references of File reference.
         */
        public List<List<File>> findDuplicateFilesList(List<File> files) {
            // First create the map for the file size and file reference in the array list.
            Map<Long, List<File>> fileSizeMap = new HashMap<Long, List<File>>();
            List<Long> potDuplicateFilesSize = new ArrayList<Long>();

            for (Iterator<File> iterator = files.iterator(); iterator.hasNext();) {
                File file = (File) iterator.next();
                Long fileLength = new Long(file.length());
                List<File> filesOfSameLength = fileSizeMap.get(fileLength);
                if (filesOfSameLength == null) {
                    filesOfSameLength = new ArrayList<File>();
                    fileSizeMap.put(fileLength, filesOfSameLength);
                } else {
                    potDuplicateFilesSize.add(fileLength);
                }
                filesOfSameLength.add(file);
            }

            // If we don't have any potential duplicates then skip further processing.
            if (potDuplicateFilesSize.size() == 0) {
                return null;
            }

            System.out.println(potDuplicateFilesSize.size() + " files will go thru " + hashingAlgo + " hash check to verify if they are duplicate.");

            // Now we will scan the potential duplicate files, and eliminate false positives using md5 hash check.
            List<List<File>> finalListOfDuplicates = new ArrayList<List<File>>();
            for (Iterator<Long> potDuplicatesFileSizeIterator = potDuplicateFilesSize
                    .iterator(); potDuplicatesFileSizeIterator.hasNext();) {
                Long fileSize = (Long) potDuplicatesFileSizeIterator.next();
                List<File> potDupFiles = fileSizeMap.get(fileSize);
                Map<String, List<File>> trueDuplicateFiles = new HashMap<String, List<File>>();
                for (Iterator<File> potDuplicateFilesIterator = potDupFiles.iterator(); potDuplicateFilesIterator
                        .hasNext();) {
                    File file = (File) potDuplicateFilesIterator.next();
                    try {
                        String md5Hex = hashProvider.getHashHex(file);
                        List<File> listOfDuplicatesOfAFile = trueDuplicateFiles.get(md5Hex);
                        if (listOfDuplicatesOfAFile == null) {
                            listOfDuplicatesOfAFile = new ArrayList<File>();
                            trueDuplicateFiles.put(md5Hex, listOfDuplicatesOfAFile);
                        }
                        listOfDuplicatesOfAFile.add(file);
                    } catch (IOException e) {
                        e.printStackTrace();
                    }
                }
                Collection<List<File>> dupsOfSameSizeList = trueDuplicateFiles.values();
                for (Iterator<List<File>> dupsOfSameSizeListIterator = dupsOfSameSizeList.iterator(); dupsOfSameSizeListIterator
                        .hasNext();) {
                    List<File> list = (List<File>) dupsOfSameSizeListIterator.next();
                    // It will be duplicate only if we have more then one copy of it.
                    if (list.size() > 1) {
                        finalListOfDuplicates.add(list);
                        System.out.println("Duplicate sets found: " + finalListOfDuplicates.size());
                    }
                }
            }

            return finalListOfDuplicates;
        }

        abstract class HashProvider {
            abstract String getHashHex(File file) throws IOException ;
        }

        class Md5HashProvider extends HashProvider {
            String getHashHex(File file) throws IOException {
                return DigestUtils.md5Hex(new FileInputStream(file));
            }
        }
        class Sha1HashProvider extends HashProvider {
            String getHashHex(File file) throws IOException {
                return DigestUtils.sha1Hex(new FileInputStream(file));
            }
        }
    }

Answer 9

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

Использование хэша только увеличивает загрузку процессора и ничего более. Поскольку вы ничего не пишете, кеш ОС будет эффективно УДАЛЯТЬ прочитанные вами данные, поэтому в Linux просто используйте cmp tool

Answer 10

Почему вы хотите его хешировать?

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

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