Take the 2-minute tour ×
Super User is a question and answer site for computer enthusiasts and power users. It's 100% free, no registration required.

I have an external hard drive on which I have backed up files several times. Some files were modified between backups, others were not. Some may have been renamed. Now I'm running out of space, and I'd like to clean up duplicate files.

My idea was to md5sum every file on the drive, then look for duplicates, and diff the relevant files (just in case, haha). Is this the best way to do this? What are some other methods of checking for duplicate files?

share|improve this question

migrated from stackoverflow.com Mar 21 '10 at 19:12

This question came from our site for professional and enthusiast programmers.

    
Do you want to write a program to do this, or use existing tools? –  Michael Petrotta Mar 21 '10 at 18:56
    
I've already hacked this together at the command line using the strategy described, and it works. I was simply wondering if other strategies exist. –  miorel Mar 21 '10 at 19:01

3 Answers 3

Computing an MD5 hash of each and every file (suggested in the question and the links from answers) seems to be a quite "expensive" way to solve the problem. Ignoring the actual computation of each hash, just reading each an every file completely incurs a lot of work on the (extremely slow) hard drive.

My suggestion for an "algorithm" would be something link this:

  • Get the exact length of every file on the drive (or directory, or whatever). This should be relatively cheap, as the length is likely to be stored in the index part of the file system.
  • For each unique file size with more than one file associated, compute the MD5 of each of these and compare the hash values to spot duplicates. While not very likely, two files with same length could hash to the same value. If you do not want to take the risk of false positives, compare files byte by byte instead or after the hash comparison.
  • For every other unique file size, you do not have any duplicates.
share|improve this answer
1  
I would check size, on dup file sizes, check first 512 bytes (one sector), and if same, then computer md5. But keep in mind md5 reads the entire file to compute, so why not just binary compare the entire file to be sure (after all, md5 is broken) –  Cole Johnson Nov 16 '12 at 19:19
    
"two files with the same length": no, it's even more general: "two files": a possible md5-collision does not require same length of input (same is true for sha* etc). –  akira Nov 16 '12 at 20:09

If md5 says it's the same file, you don't need the diff. People have solved this problem a good number of times so you can do what they did.

share|improve this answer
3  
Uh, yes, you do need the diff in order to be certain that they're the same. MD5 only outputs 128 bits, so if your file is larger than that, it must necessarily be possible to find two files A and B which have the same MD5, but do not have the same contents. If two files have different MD5, then you know they're different, but the inverse is not the case - you have to compare each byte of the file if you want to be absolutely certain that they are different. –  Michael Madsen Mar 21 '10 at 19:04
2  
so if my file is larger than 128 bit I have to go through all 100 Megabytes, for example?? That doesn't sound right, as the whole point of hashing is that is hashing the entire file. While there are duplicates that occur when using the MD5 hash, the odds of one occurring between two user generated non malicious files are extremely low. SHA 256 or 512 is preferred now. –  BigHomie Jun 30 at 16:00
    
@Michael With a good 128-bit hash, there are about 10^40 possible output values. If an overlap of two such values is the sort of risk that keeps you up at night...well, I'll just say it doesn't keep me up at night. ;) –  Tomislav Nakic-Alfirevic Jul 1 at 8:49

protected by Community Feb 11 '13 at 10:40

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?