ProjectsDuplicate File Finder
A command-line tool that walks a directory tree, finds files whose contents are identical, and offers to delete the extra copies. Building it teaches how to narrow a huge set of candidates with checks that grow from cheap to costly, what a content hash can and can't prove, how to walk a real file system full of links and errors, and how to delete files without ever losing the only copy.
From Coding Challenges #75 ↗ by John Crickett
No sign-up. You tell the mentor your language: Java, Python or Node.js.
What you'll learn · 8 concepts
In the order the steps use them. Each one links to the best places to learn it, and you explain it in your own words once its steps are built.
Steps 2, 3 and 4 are exactly these stages, and the page's test files are made so that size alone can't decide: many random files of one size share a group until the hash splits them. The minimum size in step 5 is one more cheap filter in front of them all.
Covers: a cheap necessary test before a costly sufficient one · size comes from metadata, without opening the file · only groups of two or more go on to the next stage · a hash of the first block as an extra stage · empty files, which are all identical · cost measured in bytes read from disk
fdupes (Wikipedia) ↗ · rmlint Developer's Guide: Optimizations ↗
Step 3 replaces sizes with MD5 hashes and can only call the result probable duplicates, and step 4 exists because a matching hash is strong evidence but not proof.
Covers: a short, fixed-size fingerprint of any input · equal files always give equal hashes, but not the reverse · the pigeonhole principle · accidental collisions and the birthday bound · collisions made on purpose, as for MD5 and SHA-1 · when cryptographic strength matters and when it doesn't
RFC 6151: Updated Security Considerations for the MD5 Message-Digest and HMAC-MD5 Algorithms ↗ · Google Online Security Blog: Announcing the first SHA1 collision ↗ · Birthday attack (Wikipedia) ↗
Step 2 groups files by size and step 3 by hash, and each report is simply the groups that have more than one member.
Covers: one pass instead of comparing every pair · a map from each key to a list of records · keeping only groups with more than one member · refining groups with a finer key, such as size and then hash · memory of one entry per file · groups come out in no fixed order
Hash table (Wikipedia) ↗ · Algorithms, Lecture 5: Hash Tables (Jeff Erickson) ↗
Step 1 lists every file under the given directory at any depth, and the optional going further step asks you to handle symbolic links.
Covers: depth-first walk with recursion or an explicit stack · regular files, directories, links and special files · symbolic links and cycles · remembering visited directories by device and inode · unreadable entries, reported without stopping the walk · paths relative to the starting directory
fts(3), Linux manual page ↗ · symlink(7), Linux manual page ↗ · POSIX: find, find files ↗
Step 3 hashes whole files and step 4 compares them byte by byte, and both have to work on files far bigger than the test data.
Covers: constant memory for a file of any size · feeding a hash one chunk at a time · comparing two files chunk by chunk and stopping at the first difference · short reads · chunk size against the number of reads · seek thrash on spinning disks
read(2), Linux manual page ↗ · Merkle-Damgard construction (Wikipedia) ↗ · POSIX: cmp, compare two files ↗
Step 3 suggests keeping hashes in memory or in a local database, and asks you to think about how you'd know a saved hash is still correct before you rely on it.
Covers: what the cache is keyed by · size and times as a cheap change detector · timestamp resolution and changes within the same tick · tools that set a modification time back on purpose · entries for files that no longer exist · trusting metadata against reading the content again
Git documentation: Use of index and Racy Git problem ↗ · rsync(1) manual page (the quick check algorithm) ↗
A byte compare can't tell a second name for a file from a real copy, step 6 deletes whatever the user picks, and the optional going further step brings symbolic links in.
Covers: a directory entry is a name that points at an inode · hard links, several names for one file · device and inode number as a file's identity · the link count · a symbolic link is a separate file that holds a path · same file against same content
inode(7), Linux manual page ↗ · link(2), Linux manual page ↗
Step 6 asks the user which copy to delete and acts on the answer, and keeping every file on anything but a valid choice is part of its contract. A log of deletions is one of the optional extras.
Covers: deleting removes a name, and the data only when no name or open file is left · every group keeps at least one file · anything but a clear, valid choice means keep · checking again right before deleting · a dry run and a log of what was removed · moving files to a holding folder instead of deleting
unlink(2), Linux manual page ↗ · rmlint: Cautions (or why it's hard to write a dupefinder) ↗ · Time-of-check to time-of-use (Wikipedia) ↗
What you'll build · 7 steps
Steps of 30 to 60 minutes, in your own editor and language. Each one has a check, so you know when it works.
Create the project and a throwaway test tree: a set of small files of random bytes that all have the same size, a copy of one of them, and nested folders holding more copies at different depths. Install fdupes too if you want a reference to compare against.
Works whenThe tree has several levels, at least one pair of identical files sits in different folders, and many files share one size while their contents differ.
Take a directory as the argument and print the path of every file beneath it, relative to that directory, going into subdirectories at any depth.
Works whenEvery file in the test tree appears exactly once, nested ones with their folders in the path, and no directory is printed as if it were a file.
Concepts: walking a directory tree that isn't quite a tree
Record each file's path and size, group the files that share a size, and print each group with more than one member as potential duplicates. Stop printing the full listing.
Works whenThe copies you made appear together, and so do all the random files of the same size, which shows that size alone can't decide.
Concepts: grouping records by a key with a hash map · narrowing candidates from cheap checks to costly ones
Hash the contents of the files in each size group, with MD5 or a SHA hash if you prefer, and print the files that share a hash as probable duplicates. If you like, keep the hashes between runs and make sure a saved hash is still valid before using it.
Works whenOnly the real copies are reported, the random files of the same size drop out, and a file whose size no other file shares is never hashed.
Concepts: content hashes and collisions · reading large files in fixed-size chunks · caching hashes and knowing when they're stale
Within each group of matching hashes, compare the files byte by byte and print only the ones that match completely as duplicates.
Works whenEvery reported pair also compares equal with cmp, and the groups are the same ones that fdupes finds when it searches the same tree recursively.
Concepts: narrowing candidates from cheap checks to costly ones · content hashes and collisions · reading large files in fixed-size chunks
Add an optional --minsize argument that leaves out files smaller than the given number of bytes before any of them is read. The page doesn't say whether a file of exactly that size counts, so choose and say which.
Works whenWith a minimum above the size of the test files nothing is reported, and with one well below it the groups are the same as before.
Concepts: narrowing candidates from cheap checks to costly ones
For each group of duplicates, show its files as a numbered list, ask which one to delete, and delete that file. Any answer that isn't one of the numbers keeps every file and moves on to the next group.
Works whenOn a copy of the test tree, choosing a number removes exactly that file and leaves the rest of its group, and an empty or invalid answer leaves every file in place.
Concepts: deleting safely · paths, inodes and links
Handle symbolic links on purpose, whether you follow them or skip them, extend deletion beyond one prompt per group if you want to, and keep a log of every file the tool deletes.
Works whenA link to a parent folder doesn't make the scan loop, a link is never reported as a copy of its own target, and the log lists each deleted path.
Concepts: walking a directory tree that isn't quite a tree · paths, inodes and links · deleting safely