rdfind does exactly what you ask for (and in the order johny why lists). Makes it possible to delete duplicates, replace them with either soft or hard links. Combined with symlinks you can also make the symlink either absolute or relative. You can even pick checksum algorithm (sha256, md5, or sha1).
Since it is compiled it is faster than most scripted solutions: time on a 15 GiB folder with 2600 files on my Mac Mini from 2009 returns this
9.99s user 3.61s system 66% cpu 20.543 total (using md5).
Available in most package handlers (e.g. MacPorts for Mac OS X).
Edit: I can add that rdfind is really easy to use/very pedagogic. Just use the -dryrun true flag and it will be very intuitive, not scary (which, IMO, tools that delete files usually are).