What are the most effective methods to search duplicate files?

Question

1. check files with same extension and same size
2. use some hash function (md5, md6 suppose to be better)

The first is not very reliable because the name is not part of the file. The file can have no extension. The second is rather slow on large files.

I suppose there are some more effective methods.

Answer 1

There are no more effective methods.

You can check that the file sizes are the same, but there's a very real chance of a false positive. Checking file extension is useless because you can have two identical files with different extensions.

You can check that the file contents match exactly, e.g. with the cmp command, which is part of any Unix install. This is much slower than checking file size, because size is just a metadata read and a byte-for-byte compare requires reading the entirety of both files.

You can compute a checksum, which is essentially the same as the above but (1) consumes more CPU in the simple two-file case and (2) makes comparing more than two files much easier. The reason for this is that you can cache the checksum so you don't have to re-read each file for every other file, you just compare the checksums.

If you have a known file type, such as an image type, you could perform "better" tests for approximate equality, if approximate equality was your goal. Any such method would not consume less CPU or fewer disk reads than any of the above methods.

If your filesystem is ZFS or another FS that checksums files or blocks "natively" you could efficiently compare files simply by reading filesystem metadata.

Your best bet when implementing a generic duplicate finder is to go with a pre-rolled solution. If you must do it yourself you should scan and checksum all files, maintain a database of the results, and then refresh it when files change (or periodically if that is better for your scenario). Duplicate checking then becomes a simple and efficient matter of querying the database.

Answer 2

A more effective method would be a combination to prevent useless comparisons:

1. Group files by the file size.
2. Group files based on a hash of the beginning data of each file.
3. Compare the files in each hash group with one another using a hash function.

The size of the beginning data should be chosen large enough to be unique enough (not the header).

You might want to consider not to completely check large files, but rather check a smaller part and list them as "large files / possible duplicates" instead of "exact duplicates" and provide a full check option.

As phogg mentioned, if you need to do this behavior regular:
You might want to update the hash group in a database every time a file has been changed...