Find duplicate files without reading their full content

[kornelski]

You could use approach of https://github.com/kornelski/dupe-krill to hash only as little as necessary, instead of hashing whole files.

[qarmin]

I tried to read and understand what it going on with lazy hashing, but I failed because for now seems that I only can read my own code.

But if I correctly understand it opens n files which are in group with same size and read part of file, hashes it and compare it with other partial hashes. Next throw out unique hashes and repeat everything until data ends.

Looks that this should be very fast solution but isn't suitable for current Czkawka version:

• At first, Windows looks that have limit of 512 files opened at one time, current implementation opens maximal one file per available virtual processor but probably lazy hashing could exceed this limit with checking e.g. 1000 identical files .
• But the most important, that will really complicate caching data. Recently added feature base on saving/loading full file hash.

[kornelski]

It doesn't have to keep the files open. It's fine to close and reopen them when needed.

The key insight is that if you split a file into multiple hashes (array of hashes), and put these multi-hashes in a tree (btree or binary tree), then you don't need to know all of the hashes at once. You only need to compare them as bigger/smaller. This means you can stop reading files as soon as you find a difference. And when all of the files are in the same tree, you only compare the file against minimum number of other files as you go down the tree, and you only need to compare minimum number of hashes.

[x2es]

I'd like to link this thread with this idea #640