Earlier quoted context omitted.
I don't know exactly what Siracusa is doing here, but I can take an educated guess: For each candidate file, you need some "key" that you can use to check if another candidate file is the same. There can be millions of files so the key needs to be small and quick to generate, but at the same time we don't want any false positives. The obvious answer today is a SHA256 hash of the file's contents; It's very fast, not t…
You can start with the size, which is probably really unique. That would likely cut down the search space fast. At that point maybe it’s better to just compare byte by byte? You’ll have to read the whole file to generate the hash and if you just compare the bytes there is no chance of hash collision no matter how small. Plus if you find a difference in bytes 1290 you can just stop there instead of reading the whole t…
Wonder what the distribution is here, on average? I know certain file types tend to cluster in specific ranges.
>maybe it’s better to just compare byte by byte? You’ll have to read the whole file to generate the hash
Definitely, for comparing any two files. But, if you're searching for duplicates across the entire disk, then you're theoretically checking each file multiple times, and each file is checked against multiple times. So, hashing them on first pass could conceivably be more efficient.
>if you just compare the bytes there is no chance of hash collision
You could then compare hashes and, only in the exceedingly rare case of a collision, do a byte-by-byte comparison to rule out false positives.
But, if your first optimization (the file size comparison) really does dramatically reduce the search space, then you'd also dramatically cut down on the number of re-comparisons, meaning you may be better off not hashing after all.
You could probably run the file size check, then based on how many comparisons you'll have to do for each matched set, decide whether hashing or byte-by-byte is optimal.