What is the fastest hash algorithm to check if two files are equal?

Question

What is the fastest way to create a hash function which will be used to check if two files are equal?

Security is not very important.

Edit: I am sending a file over a network connection, and will be sure that the file on both sides are equal

Answer 1

Unless you're using a really complicated and/or slow hash, loading the data from the disk is going to take much longer than computing the hash (unless you use RAM disks or top-end SSDs).

So to compare two files, use this algorithm:

• Compare sizes
• Compare dates (be careful here: this can give you the wrong answer; you must test whether this is the case for you or not)
• Compare the hashes

This allows for a fast fail (if the sizes are different, you know that the files are different).

To make things even faster, you can compute the hash once and save it along with the file. Also save the file date and size into this extra file, so you know quickly when you have to recompute the hash or delete the hash file when the main file changes.

Answer 2

One approach might be to use a simple CRC-32 algorithm, and only if the CRC values compare equal, rerun the hash with a SHA1 or something more robust. A fast CRC-32 will outperform a cryptographically secure hash any day.

Answer 3

xxhash purports itself as quite fast and strong, collision-wise:

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

There is a 64 bit variant that runs "even faster" on 64 bit processors than the 32, overall, though slower on 32-bit processors (go figure).

http://code.google.com/p/crcutil is also said to be quite fast (and leverages hardware CRC instructions where present, which are probably very fast, but if you don't have hardware that supports them, aren't as fast). Don't know if CRC32c is as good of a hash (in terms of collisions) as xxHash or not...

https://code.google.com/p/cityhash/ seems similar and related to crcutil [in that it can compile down to use hardware CRC32c instructions if instructed].

If you "just want the fastest raw speed" and don't care as much about quality of random distribution of the hash output (for instance, with small sets, or where speed is paramount), there are some fast algorithms mentioned here: http://www.sanmayce.com/Fastest_Hash/ (these "not quite random" distribution type algorithms are, in some cases, "good enough" and very fast). Apparently FNV1A_Jesteress is the fastest for "long" strings, some others possibly for small strings. http://locklessinc.com/articles/fast_hash/ also seems related. I did not research to see what the collision properties of these are.

Latest hotness seems to be https://github.com/erthink/t1ha and https://github.com/wangyi-fudan/wyhash and xxhash also has a slightly updated version as well.

Answer 4

You could try MurmurHash, which was specifically designed to be fast, and is pretty simple to code. You might want to and a second, more secure hash if MurmurHash returns a match though, just to be sure.

Answer 5

What we are optimizing here is time spent on a task. Unfortunately we do not know enough about the task at hand to know what the optimal solution should be.

Is it for one-time comparison of 2 arbitrary files? Then compare size, and after that simply compare the files, byte by byte (or mb by mb) if that's better for your IO.

If it is for 2 large sets of files, or many sets of files, and it is not a one-time exercise. but something that will happen frequently, then one should store hashes for each file. A hash is never unique, but a hash with a number of say 9 digits (32 bits) would be good for about 4 billion combination, and a 64 bit number would be good enough to distinguish between some 16 * 10^18 Quintillion different files.

A decent compromise would be to generate 2 32-bit hashes for each file, one for first 8k, another for 1MB+8k, slap them together as a single 64 bit number. Cataloging all existing files into a DB should be fairly quick, and looking up a candidate file against this DB should also be very quick. Once there is a match, the only way to determine if they are the same is to compare the whole files.

I am a believer in giving people what they need, which is not always never what they think they need, or what the want.

Answer 6

If it's only a one off then given that you'll have to read both files to generate a hash of both of them, why not just read through a small amount of each at a time and compare?

Failing that CRC is a very simple algorithm.

Answer 7

For this type of application, Adler32 is probably the fastest algorithm, with a reasonable level of security. For bigger files, you may calculate multiple hash values, for example one per block of 5 Mb of the file, hence decreasing the chances of errors (i.e. of cases when the hashes are same yet the file content differ). Furthermore this multi-hash values setup may allow the calculation of the hash to be implemented in a multi-thread fashion.

Edit: (Following Steven Sudit's remark)
A word of caution if the files are small!
Adler32's "cryptographic" properties, or rather its weaknesses are well known particularly for short messages. For this reason the solution proposed should be avoided for files smaller than than a few kilobytes.
Never the less, in the question, the OP explicitly seeks a fast algorithm and waives concerns about security. Furthermore the quest for speed may plausibly imply that one is dealing with "big" files rather than small ones. In this context, Adler32, possibly applied in parallel for files chunks of say 5Mb remains a very valid answer. Alder32 is reputed for its simplicity and speed. Also, its reliability, while remaining lower than that of CRCs of the same length, is quite acceptable for messages over 4000 bytes.

Answer 8

In any case, you should read each file fully (except case when sizes mismatch), so just read both file and compare block-to-block.

Using hash just gain CPU usage and nothing more. As you do not write anything, cache of OS will effectively DROP data you read, so, under Linux, just use cmp tool

Answer 9

Why do you want to hash it?

If you want to make sure that two files are equal then by definition you will have to read the entire file (unless they are literally the same file, in which case you can tell by looking at meta-data on the file system). Anyways, no reason to hash, just read over them and see if they are the same. Hashing will make it less efficient. And even if the hashes match, you still aren't sure if the files really are equal.

Edit: This answer was posted before the question specified anything about a network. It just asked about comparing two files. Now that I know there is a network hop between the files, I would say just use an MD5 hash and be done with it.

Answer 10

Background:

For file comparison, using a cryptographic-grade hash function such as MD5, SHA-1, SHA-2, SHA-3 etc will be very slow as these tools are optimised for good statistical and security properties over speed.

Unfortunately, many of the tools that some users will be familiar with use the cryptographic hash functions as this is probably the most widespread use of hashing from a users' perspective. So although you can use openssl dgst or sha1, sha256 etc to compare files, it will be very slow. This is especially the case for a large directory of large files, which also happens to be a very typical use case!

For internal applications, you may not be interested in cryptographic properties. Specifically, if you are worried that an adversary may be trying to create a collision on purpose, then you should stick with one of the above algorithms (and avoid MD5 or SHA-1 which are broken).

Benchmarking hash functions:

The SMhasher website has some benchmarks which aid direct performance comparison and notes / weakness, if you have specific needs.

Good compromise:

xxdhash is very fast (at the expense of security) and is perfect for file comparison tasks internally, when security is not of concern. Binaries are widely available and these include command line utilities.

Optimisation: You only need to run the hash on files of the same size: https://unix.stackexchange.com/questions/339491/find-a-file-by-hash

Example use case:

I want to check a large directory of photos to see if some duplicated files have crept in. I'm not integrating with the outside world and, in my use case, there is no chance that a malicious actor will try to add a non-duplicate photo with an identical hash (known as a collision).

Installation:

xxdhash is available in many distributions' repositories. To install on Debian-based distributions (including Ubuntu):

sudo apt update && sudo apt install xxhash

On OpenBSD:

doas pkg_add -U xxdhash

Or from github

Get unique hashes for a full directory of files:

The xxh128sum command line tool should now be available to you. You can combine this with the find command to look for duplicated files:

find . -type f -exec xxh128sum {} \; > hashes.txt

Find duplicates:

You now have a file of hashes and filenames that can be used to find duplicates. List just the filename of the second found duplicate:

awk 'visited[$1]++ { print $2 }' hashes.txt

Answer 11

The following is the code to find duplicate files from my personal project to sort pictures which also removes duplicates. As per my experience, first using fast hashing algo like CRC32 and then doing MD5 or SHA1 was even slower and didn't made any improvement as most of the files with same sizes were indeed duplicate so running hashing twice was more expensive from cpu time perspective, this approach may not be correct for all type of projects but it definitely true for image files. Here I am doing MD5 or SHA1 hashing only on the files with same size.

PS: It depends on Apache commons codec to generate hash efficiently.

Sample usage: new 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 12

you might check out the algorithm that the samba/rsync developers use. I haven't looked at it in depth, but i see it mentioned all the time. apparently its quite good.

Answer 13

You can do it all in a single step - why sort when none is needed until the duplicated list is found :

nice find . -type f -print0 \
\
| xargs -0 -P 8 xxh128sum --tag | pvZ -i 0.5 -l -cN in0 \
\
| mawk2 'BEGIN {

   _=(FS="(^XXH(32|64|128)[ ][(]|[)][ ]["(OFS="=")"][ ])")<"" 

  } __[$(NF=NF)]--<-_ ' |  pvZ -i 0.5 -l -cN out9 \
                                                  \
  | LC_ALL=C gsort -f -t= -k 3,3n -k 2,2 | gcat -n | lgp3 3

The same logic used to locate unique items in awk via its associative hashed array feature can also be leveraged to find duplicates - it's just the flip side of the same coin - only sort when the list is much smaller.

I got output like this in my own folder filled to the brim with duplicates :

 24131  =./songChunk_93634773_0011_.8045v202108091628512738.ts=56075211016703871f208f88839e2acc
 24132  =./songChunk_93634773_0011_.8045v202108091628512772.ts=56075211016703871f208f88839e2acc

 24133  =./songChunk_93634773_0011_.8045v202108091628512806.ts=56075211016703871f208f88839e2acc
 24134  =./songChunk_93634773_0011_.8045v202108091628512839.ts=56075211016703871f208f88839e2acc
 24135  =./songChunk_93666774_0043_.7102v202108091628512485.ts=77643645774287386a02e83808a632ed

 24136  =./songChunk_93666774_0043_.7102v202108091628536916.ts=77643645774287386a02e83808a632ed
 24137  =./songChunk_92647129_0023_.8045v202108091628536907.ts=146289716096910587a15001b5d2e9d6
 24138  =./songChunk_92647129_0023_.8045v202108091628536946.ts=146289716096910587a15001b5d2e9d6

That said, the major limitation of my lazy approach is that the first file with the same hash it sees is the one it keeps, so if you care about timestamps and naming and all that, then yes you'll have to do a side-by-side call to stat to get you all the precise timestamps and inode numbers and all that TMI it offers.

— The 4Chan Teller

Answer 14

the most humane way to compare 2 files that are exactly the same is to compare the hashes, the most suitable algorithm for file hashing needs without burdening the processor's work according to my test results the "fnv1a64" algorithm is the best, no need to add additional applications, almost all software versions for server supports this algorithm.

TOTAL FILE TO SCAN 877958

TOTAL EXECUTION TIME 22353.953384876

EXECUTION TIME	ALGO
287.33039116859	xxh64
287.48988413811	murmur3f
288.99125409126	xxh128
289.31353402138	xxh3
289.95356488228	murmur3a
291.07013106346	crc32
292.12370014191	murmur3c
294.61375999451	xxh32
294.80482602119	crc32c
295.07662701607	adler32
300.95663881302	crc32b
302.49028491974	joaat
303.52309799194	fnv132
305.78797912598	md4
306.00277495384	fnv164
307.34593200684	fnv1a32
308.21020579338	tiger192,3
308.65456604958	md5
311.2399160862	tiger160,4
311.49055314064	sha1
311.90242314339	fnv1a64
312.08589076996	tiger160,3
314.24259185791	tiger128,3
315.16137599945	tiger192,4
315.28597712517	haval224,3
316.56637001038	haval160,3
317.15466785431	haval128,3
319.63687586784	haval192,3
320.57202386856	sha512
320.92411613464	tiger128,4
321.84568786621	haval256,3
322.48667311668	sha384
327.83715701103	haval192,4
328.23257398605	haval160,4
329.07334899902	haval224,4
330.29799699783	haval256,4
331.03335189819	sha3-256
332.09470105171	ripemd256
332.61167287827	haval128,4
332.66794395447	ripemd128
333.23926591873	sha512/256
336.2356030941	sha3-384
337.06548285484	sha3-224
337.61635899544	sha512/224
337.90623784065	sha256
338.38005399704	haval128,5
338.39897894859	haval160,5
345.30661702156	haval224,5
347.6267209053	sha224
348.70697999001	ripemd320
349.56418085098	haval192,5
355.15771198273	ripemd160
364.52631402016	sha3-512
367.94311404228	haval256,5
405.92915797234	whirlpool
473.47747612	gost
482.507365942	gost-crypto
687.59661793709	snefru256
689.45465397835	snefru
2137.421407938	md2

Answer 15

I remember the old modem transfer protocols, like Zmodem, would do some sort of CRC compare for each block as it was sent. CRC32, if I remember ancient history well enough. I'm not suggesting you make your own transfer protocol, unless that's exactly what you're doing, but you could maybe have it spot check a block of the file periodically, or maybe doing hashes of each 8k block would be simple enough for the processors to handle. Haven't tried it, myself.