Quel est l'algorithme de hachage le plus rapide pour vérifier si deux fichiers sont égaux?

Sauf si vous utilisez un hachage vraiment compliqué et/ou lent, le chargement des données à partir du disque prendra beaucoup plus de temps que le calcul du hachage (sauf si vous utilisez des disques RAM ou des SSD haut de gamme).

Donc, pour comparer deux fichiers, Utilisez cet algorithme:

• comparer les tailles
• comparez les dates (attention ici: cela peut vous donner la mauvaise réponse; vous devez tester si c'est le cas pour vous ou non)
• comparer les hachages

Cela permet un échec rapide (si le les tailles sont différentes, vous savez que les fichiers sont différents).

Pour rendre les choses encore plus rapides, vous pouvez calculer le hachage une fois et l'enregistrer avec le fichier. Enregistrez également la date et la taille du fichier dans ce fichier supplémentaire, afin que vous sachiez rapidement quand vous devez recalculer le hachage ou supprimer le fichier de hachage lorsque le fichier principal change.

Xxhash se prétend assez rapide et fort, collision-sage:

Http://cyan4973.github.io/xxHash/

Il existe une variante 64 bits qui fonctionne" encore plus vite " sur les processeurs 64 bits que le 32, globalement.

Http://code.google.com/p/crcutil est également dit assez rapide (et exploite les instructions CRC matérielles là où elles sont présentes, qui sont probablement très rapides, mais si vous n'avez pas de matériel qui les supporte, ne sont pas aussi rapides). Je ne sais pas si CRC32c est as bon d'un hachage (en termes de collisions) comme xxHash ou non...

Https://code.google.com/p/cityhash/ semble similaire et lié à crcutil [en ce sens qu'il peut compiler vers le bas pour utiliser les instructions crc32c matérielles si demandé].

Si vous "voulez juste la vitesse raw la plus rapide" et ne vous souciez pas autant de la qualité de la distribution aléatoire de la sortie de hachage (par exemple, avec de petits ensembles, ou où la vitesse est primordiale), il y a quelques algorithmes rapides mentionnés ici: http://www.sanmayce.com/Fastest_Hash/ (ces algorithmes de type de distribution" pas tout à fait aléatoires "sont, dans certains cas," assez bons " et très rapides). Apparemment FNV1A_Jesteress est le plus rapide pour les chaînes "longues", d'autres peut-être pour les petites chaînes. http://locklessinc.com/articles/fast_hash/ semble également lié. Je n'ai pas fait de recherche pour voir quelles sont les propriétés de collision de ceux-ci.

Vous pouvez essayer MurmurHash , qui a été spécialement conçu pour être rapide, et est assez simple à coder. Vous voudrez peut-être et un second hachage plus sûr si MurmurHash renvoie une correspondance, juste pour être sûr.

Pour ce type d'application, Adler32 est probablement l'algorithme le plus rapide, avec un niveau de sécurité raisonnable. Pour les fichiers plus gros, vous pouvez calculer plusieurs valeurs de hachage, par exemple une par bloc de 5 Mo du fichier, réduisant ainsi les risques d'erreurs (c'est-à-dire les cas où les hachages sont identiques mais le contenu du fichier différent). En outre, cette configuration de valeurs multi-hachage peut permettre le calcul du hachage à mettre en œuvre dans un multi-thread mode.

Edit : (suivant la remarque de Steven Sudit)
un mot d'avertissement si les fichiers sont petits!
Les propriétés "cryptographiques" d'Adler32, ou plutôt ses faiblesses, sont bien connues en particulier pour les messages courts. Pour cette raison, la solution proposée doit être évitée pour les fichiers de moins de quelques kilo-octets.
Néanmoins, dans la question, L'OP cherche explicitement un algorithme rapide et renonce aux préoccupations concernant la sécurité. Outre la quête de la vitesse peut impliquer plausiblement que on a affaire à de" gros " fichiers plutôt qu'à de petits fichiers. Dans ce contexte, Adler32, éventuellement appliqué en parallèle pour des morceaux de fichiers de 5 Mo par exemple, reste une réponse très valide. Alder32 est réputé pour sa simplicité et sa rapidité. En outre, sa fiabilité, tout en restant inférieure à celle des CRCs de même longueur, est tout à fait acceptable pour les messages de plus de 4000 octets.

Si ce n'est qu'un seul, alors étant donné que vous devrez lire les deux fichiers pour générer un hachage des deux, pourquoi ne pas simplement lire une petite quantité de chacun à la fois et comparer?

Défaut CRC est un algorithme très simple.

Pourquoi voulez-vous le hacher?

Si vous voulez vous assurer que deux fichiers sont égaux, vous devrez par définition lire le fichier entier (sauf s'il s'agit littéralement du même fichier, auquel cas vous pouvez le dire en regardant les méta-données sur le système de fichiers). Quoi qu'il en soit, aucune raison de hachage, il suffit de lire sur eux et voir si elles sont les mêmes. Le hachage le rendra moins efficace. Et même si les hachages correspondent, vous n'êtes toujours pas sûr si les fichiers sont vraiment égaux.

Edit: Ceci la réponse a été publiée avant que la question ne spécifie quoi que ce soit sur un réseau. Il a juste demandé à comparer deux fichiers. Maintenant que je sais qu'il y a un saut de réseau entre les fichiers, je dirais juste utiliser un hachage MD5 et en faire avec.

Ce que nous optimisons ici, c'est le temps passé sur une tâche. Malheureusement, nous ne savons pas assez sur la tâche à accomplir pour savoir quelle devrait être la solution optimale.

Est-ce pour une comparaison unique de 2 fichiers arbitraires? Ensuite, comparez la taille, et après cela, comparez simplement les fichiers, octet par octet (ou mb par mb) si c'est mieux pour votre E / S.

Si c'est pour 2 grands ensembles de fichiers, ou plusieurs ensembles de fichiers, et il n'est pas un exercice. mais quelque chose qui arrivera fréquemment, alors il faut stocker des hachages pour chaque fichier. Un hachage n'est jamais unique, mais un hachage avec un nombre de 9 chiffres (32 bits) serait bon pour environ 4 milliards de combinaison, et un nombre de 64 bits serait assez bon pour faire la distinction entre certains 16 * 10^18 Quintillion fichiers différents.

Un compromis décent serait de générer 2 hachages 32 bits pour chaque fichier, un pour le premier 8k, un autre pour 1MB + 8k, les gifler ensemble comme un seul nombre 64 bits. Cataloguer tous les fichiers existants dans une base de données devrait être équitable rapide, et la recherche d'un fichier candidat contre cette base de données devrait également être très rapide. Une fois qu'il y a une correspondance, la seule façon de déterminer si elles sont les mêmes est de comparer les fichiers entiers.

Je crois à donner aux gens ce dont ils ont besoin, ce qui n'est pas toujours ce dont ils pensent avoir besoin,ou ce qu'ils veulent.

Dans tous les cas, vous devriez lire chaque fichier complètement (sauf cas où les tailles ne correspondent pas), donc il suffit de lire les deux fichiers et de comparer bloc à bloc.

En utilisant hash juste gagner l'utilisation du processeur et rien de plus. Comme vous n'écrivez rien, le cache du système d'exploitation supprimera efficacement les données que vous lisez, donc, sous Linux, utilisez simplement cmp tool

Ce qui suit est le code pour trouver les fichiers en double de mon projet personnel pour trier les images qui supprime également les doublons. Selon mon expérience, d'abord en utilisant le hachage rapide algo comme CRC32, puis en faisant MD5 ou SHA1 était encore plus lent et n'a apporté aucune amélioration car la plupart des fichiers de même taille étaient en effet dupliqués, donc exécuter le hachage deux fois était plus cher du point de vue du temps cpu, cette approche peut ne pas Ici, je fais MD5 ou sha1 hachage uniquement sur les fichiers de même taille.

PS: Cela dépend du codec Apache commons pour générer du hachage efficacement.

Exemple d'utilisation: Nouveau 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));
            }
        }
    }

Vous pouvez consulter l'algorithme utilisé par les développeurs Samba / rsync. Je ne l'ai pas regardé en profondeur, mais je le vois mentionné tout le temps. apparemment, c'est assez bon.