Глава 7. Хеширование

7.1. Исходные понятия

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

Задача поиска элемента по ключу, в конечном счёте, сводится к определению адреса, по которому этот элемент хранится в массивесущественно меньшего размера.

Определение этого адреса, может осуществляться с помощью промежуточного ключа (хеша, хеш-кода) , которому уже однозначно соответствует адрес:

,

так что

.

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

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

при .

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

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

7.2. Методы хеширования

Пусть значения ключа являются неотрицательными целыми числами (так всегда можно интерпретировать представляющую ключ битовую строку).

7.2.1. Хеширование методом деления

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

.

В этом случае хеш-коды ключей образуют множество , и их количество.

Для того чтобы в формировании участвовали все разряды двоичного представления, рекомендуется выбирать в качестве модуляпростое число, далёкое от степени двойки.

Максимально возможное число коллизий на единицу больше целой части дроби:

.

Например, если , то

,

и семь чисел имеют одинаковый остатокпо модулю.

7.2.2. Хеширование методом умножения

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

,

то есть — целая часть произведенияна дробную часть числа. Например, если, то,,,.

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

.

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

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

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

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

.

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

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

,

где — остаток целочисленного деленияна. Количество таких функций.

Убедимся, что множество универсально.

Из теории чисел известно ([19], с. 41), что если пробегает полную систему вычетов по модулю, то соответствующие значения, в силу взаимной простотыи, также пробегают полную систему вычетов. Значения параметровилинейной функцииоднозначно определяются её значениями на двух различных вычетахиз полной системы. Действительно, если, то , и это сравнение первой степени имеет решением единственный класс вычетов, посколькуивзаимно просты. Итак,определено однозначно. Поскольку, то по свойствам сравнений, то есть по модулюсвободный члентакже определён однозначно.

В результате получается взаимно однозначное отображение множества пар на множество пар, причём количество пар в обоих случаях равно.

Для любой пары параметров вероятность коллизии присовпадает с вероятностью попадания ключей в один класс вычетов по модулю:

.

Для ключа в множествеимеется не более чем˥ значений , сравнимых спо модулюи отличных от. (Например, присреди чиселимеетсязначений, сравнимых спо модулючисел:; исключая, получаем˥ значений). Применяя к выражению ˥неравенство (14) (см. гл. 1), получаем, что количество подходящих для коллизии ключейне превосходит числа

.

Поскольку общее количество ключей в , отличных от , есть, то

.

.