Такая вещь, как алгоритм хеширования дайджеста постоянного качества (переменный бит)?

Ваша логика из комментария довольно здравая. Качественные хэш-функции не будут генерировать дубликат/ранее сгенерированный вывод до тех пор, пока длина входных данных не будет близка (или не превысит) длину дайджеста хэша.

Но ключевым фактором риска коллизий является размер входных данных, набор которых равен размеру хеш-дайджеста. При использовании качественной хэш-функции вероятность конфликта для двух файлов размером 1 ТБ существенно не отличается от вероятности конфликта для двух файлов размером 1 КБ или даже одного файла размером 1 ТБ и одного файла размером 1 КБ. Это связано с тем, что хэш-функция стремится к однородности; хорошие функции достигают этого в высокой степени.

Из-за проблемы дня рождения риск коллизии для хеш-функции меньше, чем разрядность его выход. В этой вики-статье о принципе сортировки, который лежит в основе проблемы дня рождения, говорится :

Принцип [pigeonhole] можно использовать для доказательства того, что любой алгоритм сжатия без потерь, при условии, что он уменьшает некоторые входные данные (как следует из названия сжатия), также увеличивает некоторые другие входные данные. В противном случае набор всех входных последовательностей до заданной длины L можно было бы преобразовать в (намного) меньший набор всех последовательностей длины меньше L и сделать это без коллизий (поскольку сжатие выполняется без потерь), что позволяет классифицировать Принцип исключает.

Таким образом, переход к хеш-дайджесту «VBR» не гарантирует экономии места. задача о днях рождения позволяет вычислить вероятность того, что две случайные вещи будут иметь одно и то же свойство ( хэш-код — это свойство в широком смысле), но эта статья дает лучшее резюме, включая следующую таблицу.

^{Источник: preshing.com}

В верхней строке таблицы указано, что для того, чтобы иметь 50%-ную вероятность коллизии с 32-битной хеш-функцией, вам нужно всего лишь хешировать 77 000 элементов. Для 64-битной хэш-функции это число возрастает до 5,04 миллиарда при том же 50%-м риске коллизий. Для 160-битной хеш-функции вам потребуется 1,42 * 10²⁴ входных данных, прежде чем появится 50%-ная вероятность того, что новый вход будет иметь тот же хэш, что и предыдущий вход.

Обратите внимание, что 1,42 * 10²⁴ 160-битных чисел сами заняли бы неоправданно много места; миллионы терабайт, если я правильно рассчитываю. И это без учета 10²⁴ значений элементов, которые они представляют.

Нижний конец этой таблицы должен убедить вас в том, что 160-битная хеш-функция имеет достаточно низкий риск коллизий. В частности, у вас должно быть 10²¹ хеш-вводов, прежде чем возникнет хотя бы 1 шанс на миллион хеш-коллизии. Вот почему ваш поиск так мало выдал: не стоит разбираться со сложностью.

Однако независимо от того, какую стратегию хеширования вы выберете, существует ненулевой риск столкновения. Любой тип системы идентификации, основанный на хэше, должен иметь резервное сравнение. Простая дополнительная проверка файлов — сравнение их размеров (хорошо работает для любых данных переменной длины, длина которых известна, например строк). В Википедии описано несколько различных стратегий предотвращения и обнаружения конфликтов для хеш-таблиц, большинство из которых можно расширен до файловой системы с небольшим воображением. Если вам требуется идеальная точность, то после того, как у вас закончатся быстрые проверки, вам нужно вернуться к самому простому компаратору: дорогостоящей побитовой проверке двух входов.

Если я правильно понимаю вопрос, у вас есть несколько элементов данных разной длины, и для каждого элемента вы вычисляете хэш (то есть дайджест), чтобы элементы можно было идентифицировать.

Предположим, вы уже хэшировали N элементов (без коллизий) и используете 64-битный хеш-код.

Следующий элемент, который вы хешируете, будет принимать одно из 2^64 значений, поэтому у вас будет N / 2^64 вероятность коллизии хэшей при добавлении следующего элемента.

Обратите внимание, что эта вероятность НЕ зависит от исходного размера элемента данных. Это зависит от общего количества элементов, которые вы должны хэшировать, поэтому вы должны выбрать количество битов в соответствии с вероятностью, которую вы готовы допустить хеш-коллизии.

Однако если вы разделили свой набор данных таким образом, что в каждом разделе имеется разное количество элементов, вы можете сэкономить небольшое количество места, используя хэши переменного размера.

Например, предположим, что вы используете диски емкостью 1 ТБ для хранения элементов, и все элементы > 1 ГБ находятся на одном диске, а элементы размером ‹1 КБ — на другом, а третий используется для промежуточных размеров. На первом диске будет не более 1000 элементов, поэтому вы можете использовать меньший хэш, в то время как на диске может быть миллиард элементов с небольшими файлами, поэтому больший хеш будет подходящим для той же вероятности коллизий.

В этом случае размер хеша действительно зависит от размера файла, но только косвенно, в зависимости от размера разделов.