Достаточна ли уникальность хэшей CRC-32 для уникальной идентификации строк, содержащих имена файлов?

Question

Я отсортировал списки имен файлов, соединенных со строками, и хочу идентифицировать каждую такую ​​строку по уникальной контрольной сумме.

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

CRC-32 подходит для этой цели?

Например, мне нужно, чтобы каждая из следующих строк имела различную контрольную сумму фиксированной длины (предпочтительно короткую):

"/some/path/to/something/some/other/path"
"/some/path/to/something/another/path"
"/some/path"
...
# these strings can get __very__ long (very long strings are the norm)

Увеличивается ли уникальность хэшей CRC-32 на длину ввода?

Есть ли лучший выбор контрольной суммы для этой цели?

Answer 1

Нет.

Если в ваших именах файлов не было четырех символов или меньше, нет никакой гарантии, что CRC будут уникальными. При 10000 именах вероятность того, что по крайней мере два из них имеют одинаковый CRC, составляет около 1%.

Это было бы верно для любого 32-битного хеш-значения.

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

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

Что касается хэша, я бы порекомендовал XXH64. Это очень быстрый 64-битный хеш. Для этого приложения вам не нужен криптографический хеш, который будет излишне медленным.