Jaki jest najszybszy algorytm haszujący, aby sprawdzić, czy dwa pliki są równe?

Jeśli nie używasz naprawdę skomplikowanego i / lub powolnego skrótu, ładowanie danych z dysku zajmie znacznie więcej czasu niż obliczanie tego skrótu (chyba że używasz dysków RAM lub dysków SSD najwyższej klasy).

Aby porównać dwa pliki, użyj algorytmu:

• Porównaj rozmiary
• Porównaj daty (uważaj tutaj: to może dać złą odpowiedź; musisz sprawdzić, czy jest to dla Ciebie, czy nie)
• Compare the hashes

Pozwala to na szybką awarię (jeśli rozmiary są różne, wiesz, że pliki są różne).

Aby wszystko było jeszcze szybsze, możesz obliczyć hash raz i zapisać go wraz z plikiem. Zapisz również datę i rozmiar pliku w tym dodatkowym pliku, aby szybko wiedzieć, kiedy trzeba ponownie obliczyć hash lub usunąć plik hash, gdy główny plik się zmieni.

Xxhash twierdzi, że jest dość szybki i silny, zderzeniowy:

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

Istnieje wariant 64-bitowy, który działa "jeszcze szybciej" na 64-bitowych procesorach niż ogólnie 32.

Http://code.google.com/p/crcutil mówi się również, że jest dość szybki (i wykorzystuje sprzętowe instrukcje CRC tam, gdzie są obecne, które prawdopodobnie są bardzo szybkie, ale jeśli nie masz sprzętu, który je obsługuje, nie są tak szybkie). Nie wiem czy CRC32c jest jak dobry hash (pod względem kolizji) jako xxHash lub nie...

Https://code.google.com/p/cityhash/ wydaje się podobny i związany z crcutilem [w tym, że może skompilować się, aby użyć sprzętowych instrukcji CRC32c, jeśli zostanie poinstruowany].

Jeśli "zależy Ci tylko na najszybszej szybkości" i nie dbasz tak bardzo o jakość losowego rozkładu danych wyjściowych (na przykład przy małych zestawach lub gdzie szybkość jest najważniejsza), istnieją szybkie algorytmy wymienione tutaj: http://www.sanmayce.com/Fastest_Hash / (te "nie całkiem przypadkowe" algorytmy typu dystrybucji są w niektórych przypadkach "wystarczająco dobre" i bardzo szybkie). Najwyraźniej FNV1A_Jesteress jest najszybszy dla "długich" strun, niektóre inne prawdopodobnie dla małych strun. http://locklessinc.com/articles/fast_hash / również wydaje się powiązane. Nie badałem, jakie są ich właściwości kolizyjne.

Możesz spróbować MurmurHash , który został specjalnie zaprojektowany, aby być szybki i jest dość prosty w kodowaniu. Możesz chcieć i drugi, bardziej bezpieczny hash, jeśli MurmurHash zwróci dopasowanie, tylko dla pewności.

Dla tego typu aplikacji, Adler32 jest prawdopodobnie najszybszym algorytmem, o rozsądnym poziomie bezpieczeństwa. W przypadku większych plików można obliczyć wiele wartości skrótu, na przykład jedną na blok 5 Mb pliku, zmniejszając tym samym szanse na błędy (np. w przypadkach, gdy skróty są takie same, a zawartość pliku jest różna). Ponadto to ustawienie wartości wielu skrótów może umożliwić obliczanie skrótu do zaimplementowania w wielu wątkach Moda.

Edit : (po uwagach Stevena Sudita)
ostrzeżenie, jeśli pliki są małe!
Właściwości "kryptograficzne" Adler32, a raczej jego słabe strony są dobrze znane szczególnie w przypadku krótkich wiadomości. Z tego powodu należy unikać proponowanego rozwiązania dla plików mniejszych niż kilka kilobajtów.
Nie mniej jednak, w pytaniu, OP wyraźnie szuka szybkiego algorytmu i zrzeka się obaw o bezpieczeństwo. Ponadto dążenie do szybkości może sugerować, że mamy do czynienia z "dużymi" plikami, a nie z małymi. W tym kontekście bardzo poprawną odpowiedzią pozostaje Adler32, ewentualnie zastosowany równolegle do plików po 5MB. Alder32 jest znany ze swojej prostoty i szybkości. Ponadto jego niezawodność, pozostając niższa niż CRC o tej samej długości, jest całkiem akceptowalna dla wiadomości powyżej 4000 bajtów.

Jeśli jest to tylko jeden off, to biorąc pod uwagę, że będziesz musiał odczytać oba pliki, aby wygenerować hash obu z nich, dlaczego nie po prostu odczytać niewielkiej ilości każdego na raz i porównać?

Brak tego CRC jest bardzo prostym algorytmem.

Dlaczego chcesz to hashować?

Jeśli chcesz mieć pewność, że dwa pliki są sobie równe, z definicji będziesz musiał przeczytać cały plik (chyba że są to dosłownie ten sam plik, w którym to przypadku możesz to stwierdzić patrząc na metadane w systemie plików). Tak czy inaczej, nie ma powodu do hashowania, po prostu przeczytaj je i sprawdź, czy są takie same. Haszowanie sprawi, że będzie mniej wydajne. I nawet jeśli hashe się zgadzają, nadal nie masz pewności, czy pliki naprawdę są równe.

Edit: To odpowiedź została zamieszczona, zanim pytanie określiło cokolwiek o sieci. Pytano tylko o porównanie dwóch plików. Teraz, gdy Wiem, że między plikami jest przeskok sieciowy, powiedziałbym, że po prostu użyj skrótu MD5 i skończ z tym.

Optymalizujemy tutaj czas spędzony na zadaniu. Niestety nie wiemy wystarczająco dużo o zadaniu, aby wiedzieć, jakie powinno być optymalne rozwiązanie.

Czy służy do jednorazowego porównania 2 dowolnych plików? Następnie porównaj rozmiar, a następnie po prostu porównaj pliki, bajt po bajcie (lub mb po mb), jeśli jest to lepsze dla Twojego IO.

Jeśli jest to dla 2 dużych zestawów plików lub wielu zestawów plików i nie jest to ćwiczenie jednorazowe. ale coś, co będzie się działo często, wtedy należy przechowywać hasze dla każdego pliku. Hash nigdy nie jest unikalny, ale hash o liczbie powiedzmy 9 cyfr (32 bity) byłby dobry dla około 4 miliardów kombinacji, a liczba 64 bitów byłaby wystarczająco dobra, aby odróżnić niektóre 16 * 10^18 trylionów różnych plików.

Przyzwoitym kompromisem byłoby wygenerowanie 2 32-bitowych hashów dla każdego pliku, jeden dla pierwszego 8k, drugi dla 1MB+8k, spoliczkować je razem jako jeden 64-bitowy numer. Katalogowanie wszystkich istniejących plików w DB powinno być sprawiedliwe szybkie, a szukanie pliku kandydata na podstawie tego DB powinno być również bardzo szybkie. Gdy istnieje dopasowanie, jedynym sposobem na określenie, czy są one takie same, jest porównanie całych plików.

Wierzę w dawanie ludziom tego, czego potrzebują, co nie zawsze nigdy nie jest tym, co myślą, że potrzebują, lub czego chcą.

W każdym przypadku, powinieneś przeczytać każdy plik w pełni( z wyjątkiem przypadków, gdy rozmiary są niedopasowane), więc po prostu przeczytaj oba pliki i porównaj block-to-block.

Użycie hasha po prostu zwiększa zużycie procesora i nic więcej. Jak nic nie piszesz, cache OS skutecznie upuści dane, które czytasz, więc pod Linuksem wystarczy użyć CMP tool

Poniżej znajduje się kod do wyszukiwania duplikatów plików z mojego osobistego projektu do sortowania zdjęć, które również usuwa duplikaty. Jak na moje doświadczenie, najpierw za pomocą szybkiego mieszania algo jak CRC32, a następnie robi MD5 lub SHA1 był jeszcze wolniejszy i nie zrobił żadnej poprawy, jak większość plików o tych samych rozmiarach były rzeczywiście zduplikowane, więc uruchomienie mieszania dwa razy był droższy z perspektywy czasu procesora, to podejście może nie być poprawne dla wszystkich typów projektów, ale to na pewno prawda dla plików graficznych. Tutaj robię haszowanie MD5 lub SHA1 tylko na plikach o tym samym rozmiarze.

PS: To zależy od kodeka Apache commons, aby generować hash sprawnie.

Przykładowe użycie: nowy DuplicateFileFinder ("MD5").findDuplicateFilesList(lista plików);

    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));
            }
        }
    }

Możesz sprawdzić algorytm, którego używają Programiści samba/rsync. Nie przyjrzałem się temu dogłębnie, ale widzę, że ciągle o tym wspominam. najwyraźniej jest całkiem dobry.