Determining whether a file is a duplicate

Question

Is there a reliable way to determine whether or not two files are the same? For example, two files with the same size and type may or may not be the same binarilly (yeah, I know it's not really a word). I assume that comparing one or two checksums of the files will help, but I wonder:

1. How reliable are checksums at determining whether two files are different; what are the chances of two different files having the same checksum?
2. Would reliability increase by applying additional checksum comparisons?
3. Which checksum algorithm(s) would be the most efficient and/or reliable?

Any ideas, suggestions or thoughts are appreciated!

P.S. The code for this is being written in Java running on a nix system, but generic or platform agnostic input is most helpful.

Answer 1

1) Very reliable
2) Not theoretically
3) SHA-1

Answer 2

Any standard checksum algorithm as MD5 will give you a reliable test, for most real life scenarios. If you need even more reliability, go SHA. http://en.wikipedia.org/wiki/Cryptographic_hash_function#Cryptographic_hash_algorithms

Answer 3

It's impossible to know with certainty whether or not two files are the same unless you compare them byte for byte. It's similar to how you can't guarantee that a collection does or doesn't contain a given object unless you check every item in the collection.

Checksums are basically a hash. Whether they're good enough for your purposes depends on how mission-critical your app is. It's certainly possible to create a hash function with low risk of collision; after all, passwords are hashed, even in situations where they protect sensitive data and you wouldn't want to have a second valid password on your account. Unless you're writing code for, say, a bank, a strong checksum algorithm should provide a very good approximation.

Using multiple checksums will increase reliability if and only if the different checksum algorithms use dissimilar hash functions.

Your third question has already been taken care of by leonbloy's answer; MD5 and SHA-1 are common.

Answer 4

Any checksum will give you a false positive for a very small number of cases. If you can live with that, fine. If not then the way to do this is to do the checksum comparison first, and if the checksums are equal then to a byte-by-byte test. The byte-by-byte test will be done very rarely, so the cost averaged over a lot of comparisons will be very small. HOWEVER this is not the case when most of your comparisons are expected to return 'true'.

It also depends on how many different files you are testing. Calcualting a high-reliability checksum is nearly as expensive as doing a comparison - if each file gets compared approximately once then it may be cheaper to do the comparisons.