Коллизии хэш-функций и парадокс дней рождения
Как работает хэш-функция? На вход подаются произвольные данные — слово, веб-сайт, файл или ДНК человека — а на выходе получаем 16-теричное число (hex). Очень удобно, чтобы стандартизировать различные объекты, присвоить им уникальные ID, цифровые отпечатки.
К сожалению, отпечатки иногда получаются одинаковыми — происходят коллизии.
Коллизии хэш-функций похожи на парадокс дней рождения, который недавно вызвал бурные дебаты на Хабре и на HN. Почему люди так горячо спорят? Наверное, потому что человеческая интуиция иногда не совпадает с математическими формулами. Другими словами, язык математики ≠ человеческому.
Интересно сравнить разные хэш-функции с математической точки зрения. Насколько часто встречаются «парадоксы»?
Как работает хэш-функция? На вход подаются произвольные данные — слово, веб-сайт, файл или ДНК человека — а на выходе получаем 16-теричное число (hex). Очень удобно, чтобы стандартизировать различные объекты, присвоить им уникальные ID, цифровые отпечатки.
К сожалению, отпечатки иногда получаются одинаковыми — происходят коллизии.
Коллизии хэш-функций похожи на парадокс дней рождения, который недавно вызвал бурные дебаты на Хабре и на HN. Почему люди так горячо спорят? Наверное, потому что человеческая интуиция иногда не совпадает с математическими формулами. Другими словами, язык математики ≠ человеческому.
Интересно сравнить разные хэш-функции с математической точки зрения. Насколько часто встречаются «парадоксы»?
Скрытое содержимое могут видеть только пользователи групп(ы): Premium, Местный, Свои
