Комбинация хэш-функции - существует ли значительное снижение риска столкновений?

Question

Кто-нибудь знает, есть ли реальная выгода относительно уменьшения вероятности столкновения, комбинируя хэш-функции? Мне особенно нужно знать это в отношении 32-битного хеширования, а именно для объединения Adler32 и CRC32. В принципе, будет ли adler32 (crc32 (data)) меньше вероятность столкновения, чем crc32 (данные)? Последний комментарий here дает некоторые результаты испытаний в пользу объединения, но источник не упоминается. Для моей цели столкновение не является критическим (т. Е. Задача не связана с безопасностью), но я бы скорее минимизировал вероятность, если это было возможно. PS: Я только начинаю в прекрасном мире хэширования, много читаю об этом. Извините, если я задал глупый вопрос, я еще не приобрел надлежащий «диалект хеширования», возможно, мои поисковые запросы Google также были плохо сформированы. Спасибо.

Answer 1

Это не имеет смысла комбинировать их последовательно. Вы смешиваете одно 32-разрядное пространство с другим 32-битным пространством.

В случае столкновения crc32 на первом этапе конечным результатом является столкновение. Затем вы добавляете любые потенциальные коллизии на этапе adler32. Так что он не может стать лучше, и может быть только тем же или худшим.

Для уменьшения коллизий, вы можете попробовать что-то, как с помощью двух хэшей самостоятельно создать 64-разрядный выходной пространство:

Adler32 (данные) < < 32 | crc32 (данные)

Есть ли существенная выгода в этом, я не уверен.

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

Какой алгоритм используется там будет какой-то шанс ложных срабатываний . Тем не менее, вы можете уменьшить эти шансы на значительный запас , используя два разных алгоритма хеширования . Если вы должны были рассчитать и сохранить как CRC32, так и Alder32 для каждого URL, вероятность одновременного столкновениядля обоих хешей для любой заданной пары URL-адресов значительно уменьшена.

Конечно, это означает, что вы храните дважды как много информации, которая является частью вашей исходной проблемы. Тем не менее, существует является способ хранения обоих наборов хэш данных таким образом, что оно требует минимального памяти (10КБ или около того) в то время давая почти такую ​​же производительность подстановки (15 microsecs/поиск по сравнению с 5 microsecs) в качестве хэш в Perl ,