Elaborating a bit on Snowman's answer, I think I would go for a hierarchy of hash values over (exponentially) increasing subsets of the file, computed on-demand whenever collisions occur, and memorized in a suitable data structure (hash table, but even a simple prefix tree would do) for quick future access. This should ensure quick failure in case of 'almost identity', and retain the worst-case complexity (up to a log factor) and achieve good average-case complexity.
It would go as follows in pseudo-Python, taking as input a file
f, a set of files
D and a dictionary
H (again, one could do better here, but it should not matter too much) acting as a cache for previously computed hash values:
collisions = [fc for fc in D if size(fc)==size(f)]
size_hash = 4*1024
while (len(collisions) > 0) and (size_hash<=size(f)):
H[(f,size_hash)] = md5(f,size_hash)
for fc in collisions:
if (fc,size_hash) not in H:
H[(fc,size_hash)] = md5(fc,size_hash)
collisions = [fc for fc in collisions if H[(fc,size_hash)]==H[(f,size_hash)]]
size_hash *= 2
for fc in collisions:
# Painstakingly read and compare content to that of f...
Worst-case complexities: In the worst case, all of the files have equal length
n, and have different yet MD5 identical (unlucky!) contents, so one ends up computing MD5 hashes for chunks of size 4k, 8k, 16k...
n in each of the files, only to read them in full afterward.
In term of time, the first 4k of each file are read to compute the first hash, then the first 8k for the second, 16k for the third ... then the full size n. Computing an MD5 can be done in linear time, so the total time-consumption is (up to a constant) 4k+8k+16k+...+n < 2n operations, i.e. it remains in the order of magnitude of the final (unavoidable) comparison of the files.
In term of memory, log(n) MD5 hash values (one for 4k, one for 8k...), each of constant size will be stored, so the overhead should be reasonable.
Average-case complexities: I won't detail the analysis (maths are not permitted by the markdown system here anyway :) ), but even assuming a large number of files having equal size, the expected number of computed hash values should be constant on average, so this algorithm will neither read significant chunks of the files, nor clotter the memory.