What is the fastest hash algorithm to check if two files are equal?
https://stackoverflow.com/questions/1761607
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
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
Solution
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.
OTHER TIPS
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.
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.
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.
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.
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.
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.
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
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));
}
}
}
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.
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.
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.
