Я пишу что-то, что суммирует файлы в файловой системе, хэшируя образец их содержимого.Он строит дерево каталогов и файлов.Каждая запись файла имеет хэш содержимого файла.Для каждой записи каталога я хочу сохранить хэш содержимого всех файлов в каталоге, включая файлы в подкаталогах - я назову это хэш содержимого каталога.
Сложность хэша содержимого каталога заключается в том, что я хочу, чтобы он не зависел от структуры каталога.То есть хэш должен быть одинаковым, если два каталога содержат одинаковые файлы, но организованы с разной структурой подкаталогов.
Единственные два метода, о которых я могу думать:
Рассчитать MD5 конкатенации всех хэшей содержимого файла.Чтобы получить нужные свойства хеша, мне нужно было бы перечислить все файлы в каталоге, отсортировать их по хешу, объединить отсортированные хеши, а затем запустить MD5 для объединения.Это кажется медленнее, чем хотелось бы.Я могу сделать сортировку довольно эффективно, используя сортировку слиянием при расчете хэшей содержимого каталога по всему дереву, но я не могу обойтись при вычислении большого количества хешей MD5 на больших входах.
Объединениесодержимое файла хэши с использованием XOR.Каждому каталогу нужно только XOR хэши содержимого файла и хэши содержимого каталога своих непосредственных потомков.Это очень быстро и просто, но не очень устойчиво к столкновениям.Он даже не может определить разницу между каталогом, который содержит 1 экземпляр файла, и каталогом, который содержит три экземпляра одного и того же файла.
Было бы неплохо, если бы была функция, которая может использоваться аналогично тому, как XOR используется в методе # 2, но является более устойчивой к столкновениям.Я думаю, что метод № 1 был бы достаточно быстрым для этого конкретного случая, но в интересах изучения всех вариантов / интеллектуального любопытства / будущих приложений, я хотел бы знать, есть ли функция, которая удовлетворяет описанию вназвание (у меня смутное воспоминание о том, что я уже несколько раз хотел такую функцию).
Спасибо.