Коллизии хэш-функций и парадокс дней рождения

Как работает хэш-функция? На вход подаются произвольные данные — слово, веб-сайт, файл или ДНК человека — а на выходе получаем 16-теричное число (hex). Очень удобно, чтобы стандартизировать различные объекты, присвоить им уникальные ID, цифровые отпечатки.

К сожалению, отпечатки иногда получаются одинаковыми — происходят коллизии.

Коллизии хэш-функций похожи на парадокс дней рождения, который недавно вызвал бурные дебаты на Хабре и на HN. Почему люди так горячо спорят? Наверное, потому что человеческая интуиция иногда не совпадает с математическими формулами. Другими словами, язык математики ≠ человеческому.

Интересно сравнить разные хэш-функции с математической точки зрения. Насколько часто встречаются «парадоксы»?

Читать далее