Закрытое хеширование

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

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

1. имеется изначально пустая хеш-таблица T размера m, массив A размера n (m≥n) и хеш-функция h(), пригодная для обработки ключей массива A;

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

· если h(key_i) – номер свободной ячейки таблицы T, то в последнюю записывается x_i;

· если h(key_i) – номер уже занятой ячейки таблицы T, то на занятость проверяется другая ячейка, если она свободна, то x_i заноситься в нее, иначе вновь проверяется другая ячейка, и так до тех пор, пока не найдется свободная или окажется, что все m ячеек таблицы заполнены.

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

Рассмотрим метод закрытого хеширования на примере построения хеш-таблицы. Положим, имеется целочисленный массив A, состоящий из 9 элементов:

{A[key]=data, здесь key – ключ, data – некоторые данные}

A[13]=8, A[56]=4, A[79]=1, A[37]=5, A[41]=2, A[76]=9, A[51]=3, A[93]=9, A[30]=1

Также есть хеш-таблица размера m=10, и хеш-функция h(key)=key % m (% – операция «остаток от деления»). Заполним хеш-таблицу элементами массив A:

Для расстановки элементов использовалась выбранная формула. Подставив ключ, например первого элемента в нее получим: h(13) = 13 % 10 = 3, поэтому его номер в хеш-таблице 3. Последовательное добавление элементов приведет к возникновению коллизии при обработке элемента A[76]. Хеш-значение его ключа 6, но в хеш-таблице ячейка с таким номером уже занята. Используя формулу линейного пробирования (один из типов последовательности проб) h_i(key)=(h(key) + i) % m (i – число проверок, после первой проверки i=0), продолжим поиск свободной ячейки. Применим функцию при i=1: h₁(76)=7; убедившись, что ячейка 7 занята, продолжаем поиск, увеличив i на 1: h₂(76)=8. Ячейка 8 свободна, помещаем в нее элемент. Этот же метод используем и для всех остальных элементов.