Хэш-функции. Универсальное хэширование

Курс по структурам данных: https://stepik.org/a/134212

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

Как мы с вами уже говорили, на вход алгоритма хэширования подается некий ключ, например, «d». На выходе получаем индекс ячейки массива, куда записывается значение этого ключа:

Так вот, в качестве ключей хэш-таблиц можно использовать любую байтовую последовательность. На уровне компьютера – это она воспринимается, как конечная последовательность из целых чисел в диапазоне от 0 до 255 включительно, например (в соответствии с кодовой таблицей ASCII):

"for" – "102, 111, 114"
"53$%!" – "53, 51, 36, 37, 33"

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

i = h(k)

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

Способы построения хэш-функций

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

  • быть однозначной, то есть, для одного и того же ключа k выдавать одно и то же значение индекса i (свойство последовательности);
  • быстро вычисляться;
  • выходные значения (индексы) i должны находиться в диапазоне хэш-таблицы (массива);
  • множество ключей {k} должны равномерно распределяться по таблице.

Я думаю, здесь в целом все понятно, кроме, может быть последнего свойства: зачем требовать от хэш-функции равномерного распределения ключей по ячейкам таблицы? Смотрите. В общем случае, мы наперед не знаем, какие ключи k будут подаваться на вход хэш-функции. Очевидно, что возможное количество этих ключей K много больше текущего числа ячеек M в хэш-таблице. Значит, хэш-функция h(k) отображает большее множество K в меньшее M. И как бы мы ни выбирали функцию h(k), обязательно будет существовать пара ключей k1, k2, которым функция h(k) назначит один и тот же индекс. Лучшее, что мы здесь можем сделать – это минимизировать вероятность такого события. А это, в свою очередь, приводит к равномерности распределения хэш-функцией возможных ключей {k} по ячейкам таблицы. Вот отсюда и появляется последнее требование к хорошей хэш-функции. В этом случае можно доказать, что средняя длина цепочек в хэш-таблице будет равна коэффициенту заполнения:

α = n / m,

где n – число хранимых ключей; m – общее число ячеек в таблице. И алгоритмы поиска/удаления ключей, в среднем, будут выполняться за:

1 + α

операций. Это среднее минимальное число, которое может быть достигнуто.

Построение хэш-функции методом деления

Наверное, самое простое, что мы можем сделать, чтобы преобразовать множество целых неотрицательных чисел {k} (ключи) в диапазон значений [0; m-1] (индексы таблицы) – это взять и вычислить остаток от деления операцией:

Я напомню, что в языках С++ и Python функция mod реализуется оператором % следующим образом:

h(k) = k % m

На выходе имеем множество целых значений в нужном нам диапазоне [0; m-1].

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

Ключ

Хэш

Ключ

Хэш

Ключ

Хэш

111 1011

1011

0000 0101

0101

1111 0101

0101

1100 1001

1001

1000 0101

0101

1001 0101

0101

Смотрите, число m=16, фактически, выделяет последние 4 бита ключа k. И если вдруг так окажется, что все потенциальные ключи {k}, которые будут сохраняться в хэш-таблице, имеют одинаковые последние 4 бита, то всем им будет назначен один и тот же индекс. То есть, мы получим худший случай работы хэш-таблицы.

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

Построение хэш-функции методом умножения

Другой метод умножения для построения хэш-функций решает эту проблему:

Здесь A – некоторая константа, выбранная из диапазона 0 < A < 1 так, чтобы при умножении k на A формировалось дробное число, а затем, с помощью операции mod 1 выделяется эта дробная часть числа. Благодаря этому, мы как бы перемешиваем возможные значения ключей {k}, формируем случайные числа, зависящие от k, причем, эти числа находятся в диапазоне [0; 1). Все что нам остается – это расширить диапазон до [0; m-1] в целых числах. Для этого вещественное число умножается на m с округлением до наименьшего целого (оператор ).

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

Здесь только остается вопрос, как выбрать константу A? Дональд Кнут в своем известном труде «Искусство программирования» предложил значение этой константы брать равной:

Как показала практика, при таком значении A мультипликативная хэш-функция h(k) для произвольных ключей k дает более-менее равномерное распределение.

Другие алгоритмы хэширования

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

  • CRC – циклический избыточный код;
  • MD5 – 128-битный алгоритм хэширования;
  • SHA – семейство алгоритмов хэширования.

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

Универсальное хэширование

Итак, мы увидели каким образом можно выполнять построение хэш-функций. Но как бы хорошо не работал алгоритм хэширования остается одна важная проблема: для каждой конкретной функции h(k) всегда можно подобрать такой набор ключей {k}, что все они будут располагаться в одной ячейке хэш-таблицы, то есть, для всех них функция выдаст одно и то же значение. Этим обстоятельством, например, может воспользоваться злоумышленник, чтобы специально замедлить работу программы. В любом случае, это некая уязвимость, которую хотелось бы устранить. Давайте посмотрим, как с этим можно бороться?

Пусть у нас имеется несколько хеш-функций:

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

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

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

где p – некоторое простое число, которое больше размера таблицы m; ,  - целые числа, взятые из указанного диапазона. В результате, всего мы имеем:

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

Далее, доказывается, что для двух случайных ключей  любая выбранная хэш-функция выдаст одно и то же значение (индекс) с вероятностью 1/m, где m – размер хэш-таблицы. То есть, ключи распределяются равномерно.

Таким образом, если мы хотим реализовать универсальное хэширование, то достаточно определить простое число p > m, а затем, случайным образом выбрать значения a и b из их диапазонов. Эти значения определяют конкретный вид хэш-функции, которая используется для перевода ключей в индексы таблицы. В результате, злоумышленник не сможет наперед знать, какая именно будет использована хэш-функция, а значит, не сможет подготовить проблемный набор ключей {k} для образования длинных цепочек в хэш-таблице. В этом и состоит идея универсального хэширования.

Курс по структурам данных: https://stepik.org/a/134212

Видео по теме