Примеры реализации схем хеширования

Пример реализации метода прямой адресации с линейным опробыванием. Исходными данными являются 7 записей (для простоты информационная часть состоит из целых чисел) объявленного структурного типа:

struct zap {

int key; // Ключ

int info; // Информация

} data;

{59,1}, {70,3}, {96,5}, {81,7}, {13,8}, {41,2}, {79,9}; размер хеш-таблицы m = 10. Выберем хеш-функцию i = h(data) = data.key%10; т.е. остаток от деления на 10 – iÎ[0,9].

На основании исходных данных последовательно заполняем хеш-таблицу.

Хеширование первых пяти ключей дает различные индексы (хеш-адреса):

i = 59 % 10 = 9; i = 70 % 10 = 0;

i = 96 % 10 = 6; i = 81 % 10 = 1;

i = 13 % 10 = 3.

Первая коллизия возникает между ключами 81 и 41 – место с индексом 1 занято. Поэтому просматриваем хеш-таблицу с целью поиска ближайшего свободного места, в данном случае – это i = 2.

Следующий ключ 79 также порождает коллизию: позиция 9 уже занята. Эффективность алгоритма резко падает, т.к. для поиска свободного места понадобилось 6 проб (сравнений), свободным оказался индекс i = 4. Общее число проб – 1–9 проб на элемент.

Реализация метода цепочек для предыдущего примера. Объявляем структурный тип для элемента однонаправленного списка:

struct zap {

int key; // Ключ

int info; // Информация

zap *Next; // Указатель на следующий элемент в списке

} data;

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

Хеширование первых пяти ключей, как и в предыдущем случае, дает различные индексы (хеш-адреса): 9, 0, 6, 1, и 3.

При возникновении коллизии новый элемент добавляется в конец списка. Поэтому элемент с ключом 41 помещается после элемента с ключом 81, а элемент с ключом 79 – после элемента с ключом 59.