Устройство хэш-таблицы

Предположим, имеется большое множество теоретически возможных ключей, состоящее из B элементов. Также, предположим имеется массив из N ячеек, при этом N несравнимо меньше чем B. Для организации хэш-таблицы необходимо подобрать некоторую функцию h(x) называемую ХЭШ-ФУНКЦИЕЙ, принимающую любой из ключей xB, и возвращающую целое неотрицательное число h[0; N-1], называемое ХЭШ-КОДОМ. Не имеет определяющего значения конкретная форма и сложность функции h(x), при условии, что она обладает следующими свойствами:

1. Функция h(x) не имеет состояния и всегда возвращает для одинаковых ключей одинаковый результат, сколько бы раз функция не вызывалась:

x1=x2h(x1)=h(x2).

2. Область значений функции h(x) распределяется приблизительно равномерно для всех возможных ключей. Т.е. для каждого хэш-кода h[0; N-1]существует приблизительно одинаковое количество ключей x[0; B-1], хэш-код которых равен h.

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

Например, пусть ключи x являются целыми числами, которые могут принимать любые значения в допустимом диапазоне типа int (от -2³¹ до 2³¹-1), т.е. B=2³². Очевидно, массив такого размера создавать непрактично даже на очень мощном компьютере, поскольку это бы потребовало нескольких гигабайт оперативной памяти (B возможных значений ключа * размер хранимого значения). Простейшей хэш-функцией для такого типа ключа является остаток от деления:

h(x)=x % N

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

Возьмем конкретный набор ключей x1..xMи соответствующих им значений y1..yM, где M - конечное число, сопоставимое с размером массива N, и несравнимо меньшее количества всех возможных ключей B. Для каждого ключа вычислим значение хэш-функции и получим набор хэш-кодов h1..hM. Предположим, M<N, и все полученные хэш-коды являются уникальными между собой. Тогда представляется возможным свободно поместить все пары ключ-значение (x,y) в массив A, называемый ХЭШ-ТАБЛИЦЕЙ, при этом пары ключ-значение попадут в ячейки, индекс которых соответствует хэш-коду ключа. Т.е. по индексу h(xi) в массиве A, соответствующему хэш-коду конкретного ключа xi будет находится ячейка с парой ключ-значение (xi,yi):

A[h(xi)]=(xi,yi).

Пусть N = 10, M = 5, и имеются следующие наборы ключей и соответствующих им значений:

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

Разместим все пары (x,y) в соответствующие ячейки массива и получим хэш-таблицу:

Теперь, для поиска в таблице значения по некоторому ключу xk необходимо:

1. Вычислить значение хэш-кода для ключа: hk=h(xk)=xk%N.
2. Если ячейка по индексуhkзанята, сравнить хранящийся в ней ключ с искомым xk, и если они равны, вернуть значение yk.
3. Если же ячейка по индексу hk не занята, или хранимый в этой ячейке ключ не равен xk, из этого следует, что искомый ключ в таблице не содержится.

Аналогичным образом должно реализовываться удаления пары ключ-значение по ключу xk:

1. Вычислить значение хэш-кода для ключа: hk=h(xk)=xk%N.
2. Если ячейка по индексуhkзанята, сравнить хранящийся в ней ключ с искомым xk, и если они равны, освободить ячейку.
3. Если же ячейка по индексу hk не занята, или хранимый в этой ячейке ключ не равен xk, из этого следует, что искомый ключ в таблице не содержится, и был инициирован некорректный запрос на удаление незарегистрированного ключа.

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

Коллизии

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

• число пар ключ-значение превышает число ячеек в массиве ( M >= N );
• хэш-функция является неудачной в принципе и выдает неравномерное распределение ключей по области возможных значений;
• множество ключей подобрано таким неудачным образом, что хэш-функция часто выдает одинаковые коды для конкретного набора ключей.

Ситуация, когда для двух различных ключей xiи xkв результате вычисления хэш-функции получены одинаковые хэш-коды, называется КОЛЛИЗИЕЙ.

Например, пусть необходимо расширить рассмотренное выше отображение новой парой (x,y):

Вычислим значение хэш-кода от нового ключа:

К сожалению, ячейка с индексом 5 уже занята парой с другим значением ключа, и такая ситуация представляет собой коллизию.

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

• открытое хэширование
• закрытое хэширование
• двойное хэширование

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

Частично, проблему частых коллизий может решить увеличение размера массива для хранения данных. Типично, если умножить число N на 2, т.е. использовать вдвое большую таблицу, вероятность возникновения коллизий также уменьшится вдвое, поскольку новая хэш-функция h1(x)=x % 2Nс высокой вероятностью даст более равномерное распределение множества ключей.

Как правило, хэш-таблица эффективна, если она заполнена не более чем на половину. Если число хранимых пар ключ-значение заранее неизвестно и динамически увеличивается, вероятность коллизий будет постепенно повышаться по мере вставки новых пар. В таком случае, когда динамически формируемая хэш-таблица становится заполненной более чем на половину, имеет смысл автоматически увеличить размер массива с данными, и выполнить процедуру ПОВТОРНОГО ХЭШИРОВАНИЯ, т.е. повторно вставить все уже имеющиеся в старой таблице пары (x,y) в новый массив большего размера, используя новую хэш-функцию h1(x).