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

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

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

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

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

Хэш-функции используются во многих компьютерных задачах, например:

• Проверка корректности данных при передаче, обнаружение ошибок ^[5]. Например, есть удобные утилиты HashCheck ^[6] и OpenHashTab ^[7], которая поддерживает 28 алгоритмов для вычисления хэшей файлов.

• Идентификация объектов. Вычисление хэша позволяет быстро убедиться, что файл не повреждён при загрузке или копировании. У каждого файла или блока данных своя сигнатура, ID (хэш), что также используется в P2P-сетях, антивирусных базах и др.

• Генерация адресов для хранения данных (бэкапы, файловые системы и проч.) Удобно хранить объект по адресу, который соответствуют хэшу этого объекта. Это свойство применяется в хэш-таблицах и хэш-ключах для индексации баз данных. Хэш-таблицы гарантируют доступ к элементу за времени, независимо от размера базы.

• Приватность. Вместо хранения конфиденциальных данных (имена, пароли, бюллетени голосования) хранятся их хэши (с солью).

• Криптография. Цифровая подпись — это хэш документа, зашифрованный приватным ключом.

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

Коллизии

Хэш-коллизии ^[8] происходят, когда наша функция присваивает одинаковый ID разным объектам. Это неприятное событие в продакшне, потому что система тогда может перепутать пользователей, заказы, файлы или ещё что-нибудь.

Математики и программисты постоянно разрабатывают новые и более совершенные хэш-функции. Можно выбирать подходящую для каждого конкретного варианта использования, учитывая её производительность, вероятность коллизии и другие характеристики.

Поскольку хэш-функция уменьшает количество энтропии, то никогда нельзя полностью исключить вероятность коллизии. Например, взять известную хэш-функцию CRC32 ^[9]. Если передать ей две строки «plumless» и «buckeroo», то она сгенерирует одинаковое значение:

Можно вычислить ^[10] математическую вероятность коллизии для разных функций. По сути, это просто общая форма математического парадокса дней рождений ^[2]. Ответ в такой задаче не всегда очевиден, потому что интуитивно его тяжело угадать.

Парадокс дней рождения

Напомним парадокс дней рождения ^[2]:

В группе из 23 или более человек вероятность совпадения дней рождения (число и месяц) хотя бы у двух людей превышает 50%.

Например, если в классе 23 ученика, то более вероятно совпадение ДР у какой-то пары одноклассников, чем существование у всех учеников уникальных ДР.

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

Если вычислять хэши 500 книг и помещать каждую книгу в соответствующую ячейку в ряду из 100 000 ячеек, какова вероятность того, что хотя бы две книги окажутся в одной и той же ячейке? (~71,3%).

Или так:

Когда вы случайным образом раскладываете 50 шаров по 100 вёдрам, какова вероятность того, что хотя бы два шара окажутся в одном ведре? (~99,99997%).

См. калькулятор коллизий ^[11].

Вероятность коллизии

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

Учитывая случайно сгенерированных значений, где каждое значение является неотрицательным целым числом, меньшим , какова вероятность того, что как минимум два из них равны?

Задачу проще решить, если сформулировать обратный вопрос: какова вероятность того, что все сгенерированные значения уникальны? Затем вычесть ответ из единицы. Сделаем это по старой инструкции ^[10].

Учитывая пространство из возможных значений хэша, предположим, мы выбрали одно значение. После этого остаётся уникальных значений. Таким образом, вероятность случайного выбора двух целых чисел, отличающихся друг от друга, равна .

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

В общем случае вероятность случайной генерации целых чисел, все из которых являются уникальными, равна:

Что можно примерно приравнять к более оптимальной для вычисления формуле:

Скрипт для сравнения результата формул, чтобы оценить качество аппроксимации:

import math
N = 1000000
probUnique = 1.0
for k in xrange(1, 2000):
    probUnique = probUnique * (N - (k - 1)) / N
    print k, 1 - probUnique, 1 - math.exp(-0.5 * k * (k - 1) / N)

После вычитания этого значения из единицы мы получаем вероятность коллизии:

Такая аппроксимация снижает сложность вычислений с до .

Вот как выглядит график для :

На самом деле можно упростить ^[12] экспоненциальную аппроксимацию:

И ещё более упростить:

На графике ниже показаны относительные погрешности экспоненциальной аппроксимации (exp), упрощённой (simple) и ещё более упрощённой версии (simple-square):

Минимизация коллизий

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

В следующей таблице представлены диапазоны малых вероятностей коллизий для хэшей 32, 64 и 160 бит. Для простоты понимания в таблицу включены несколько реальных вероятностей, например, шансы выиграть в лотерею:

Сравнение функций

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

Для примера, ниже результаты тестирования ^[14] некоторых старых хэш-функций на процессоре Core i5. Задача включает добавление нескольких ключей в таблицу, а затем поиск их в том же порядке, в котором они добавлялись. Время замерялось инструкцией RDTSC ^[15]. В качестве набора данных использовались список слов английского языка ^[16] (words в таблице), список Win32 ^[17] и др.

Первая цифра в каждой ячейке соответствует времени выполнения, а в квадратных скобках указано количество коллизий.

Сравнение производительности ^[34] с помощью утилиты SMhasher ^[35] определяет такой список самых быстрых хэш-функций, у которых нет проблем с качеством:

• rapidhash (улучшенная wyhash),

• xxh3low,

• wyhash,

• umash,

• ahash64,

• t1ha2_atonce,

• a5hash,

• komihash,

• FarmHash,

• halftime_hash128,

• Spooky32,

• pengyhash,

• nmhash32,

• mx3,

• MUM/mir,

• fasthash32.

Новые функции

Практически каждый год становится известно о разработке новых хэш-функций, в том числе специализированных, которые созданы для решения конкретных задач. Например, в тестировании выше лучше всех проявил себя алгоритм хэширования rapidhash ^[36], который оптимизирован на максимальную производительность (скорость хэширования): более 70 ГБ/с ^[37] на процессоре M4. Семейство включает три хэш-функции: rapidhash, rapidhashMicro и rapidhashNano.

© 2025 ООО «МТ ФИНАНС»