Примеры реализации схем хеширования
Пример реализации метода прямой адресации с линейным опробыванием. Исходными данными являются 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.
Дата добавления: 2014-12-30; просмотров: 1025;