условно ты можешь прочитать первые несколько кбайт, последние несколько кбайт и например в середине и уже с большой вероятностью сказать одинаковые файлы или нет, а для подозрительно похожих - поблочно сравнить целиком
Я бы делал так:
1. Посмотрел размеры всех файлов
2. Сгруппировал
3. Пробежался, для каждой группы:
* если в ней пара файлов, то сразу бы сравнивал их
* если больше пары, то сначала чексумма, а потом для совпавших сравнение на равенство