drs-dedup

What it does

drs-dedup is a filesystem deduplication tool, written in bash and Python.
It can produce a report of which files are unique and which files are duplicates, or it can hardlink duplicates - or both.

How it works

It does not attempt to hold all metadata in memory. That is, it is not limited by available RAM or Virtual Memory.
Instead, it stores metadata in files on disk, and uses GNU sort in combination with some Python to detect duplicates. GNU sort is very well optimized, BTW, so even though drs-dedup's algorithm is O(c*n*log(n) + d*n), d is much larger than c making its performance practically limited by d*n in actual use, not c*n*log(n) - particularly on a magnetic, spinning disk.
GNU Sort is an "external sort", so if it runs low on memory, it is smart enough to switch to a disk-based algorithm.
It does hold all filenames of a given hash in memory at a time, but that's pretty small, comparatively speaking.

Caveats

drs-dedup does not compare files; it only compares hashes. There is an infinitesimal chance of a rogue hash collision. However, the odds of this happening are lower than the odds of a magnetic tape going bad.
Please note that the report has a limitation: if there is a group of preexisting hardlinked files, only one of the files in the group will be reported! This is a performance optimization that cuts down on the number of hardlinks to (re)create.

FYI: although drs-dedup can hardlink many files, there is a practical limit on the number of files a given file can be hardlinked to, imposed by the filesystem implementation:

Filesystem	Limit on number of hardlinks to a single file allowed by the filesystem's design
ZFS	2^64 - 1
APFS	2^32 - 1
Bcachefs	2^32 - 1
BTRFS	2^32 - 1
XFS	2^31 - 1
EXT4	2^16 - 1
NTFS	2^10 - 1

Suitability by storage media type:

Storage Media Type	Suitability
Spinning, magnetic disk	drs-dedup is pretty slow unless you have high hundreds of millions or billions of files - try fclones first and come back if fclones thrashes.
SSD	drs-dedup is not terribly slow. It might actually be a tool of first-resort for collections of hundreds of millions or billions of files.

How to install it:

sudo apt install subversion
svn checkout https://stromberg.dnsalias.org/svn/drs-dedup/trunk drs-dedup
cd drs-dedup
make install

For the latest specifics on how to use it, run "drs-dedup --help". Or for your convenience, see below:

Usage: /usr/local/bin/drs-dedup
    --input-dir /dir/to/dedeup
    --work-dir /dir/for/temp/data/and/output
    --sort-buffer-size 20%
    --report
    --hardlinks
    --skip-cleanup
    --help

Replace duplicate regular files under /dir/to/dedup with hardlinks to each other (or merely report).
Output will be left in /dir/for/temp/data/and/output. You will be given the precise filenames when the script
completes.

Note that --work-dir is used for GNU sort temporary files, not just your output.
Performance tip: if you put --input-dir and --work-dir in different filesystems, that should be slightly faster.

--sort-buffer-size can be anything GNU sort understands, EG 1G or 25%. Only one sort will be run at a time.