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

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

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

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

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

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

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

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

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

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

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

Коллизии

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

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

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

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

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

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

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

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

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

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

Или так:

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

См. калькулятор коллизий.

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

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

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

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

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

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

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

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

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

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)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• xxh3low,

• wyhash,

• umash,

• ahash64,

• t1ha2_atonce,

• a5hash,

• komihash,

• FarmHash,

• halftime_hash128,

• Spooky32,

• pengyhash,

• nmhash32,

• mx3,

• MUM/mir,

• fasthash32.

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

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

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