Хеширование таким образом – это способ, который подразумевает использование значения ключа для определения его позиции в специальной таблице

Однако функция расстановки может для нескольких уникальных значений ключа давать одинаковое значение позиции i в хеш-таблице. Ситуация, при которой два или более ключа получают один и тот же индекс (хеш-адрес) называется коллизией (конфликтом) при хешировании.. Поэтому схема хеширования должна включать алгоритм разрешения конфликтов, определяющий порядок действий, если позиция i = h(key) оказывается уже занятой записью с другим ключом.

Имеется множество схем хеширования, различающихся и используемой хешфункцией h(key) и алгоритмами разрешения конфликтов.

Наиболее распространенный метод задания хеш-функции: Метод деления.

Исходными данными являются: - некоторый целый ключ key и размер таблицы m. Результатом данной функции является остаток от деления этого ключа на размер таблицы. Общий вид такой функции на языке программирования С/С++:

int h(int key, int m) {

return key % m;

}

Для m = 10 хеш-функция возвращает младшую цифру ключа.

Для m = 100 хеш-функция возвращает две младших цифры ключа.

В рассмотренных примерах хеш-функция i = h(key) только определяет позицию, начиная с которой нужно искать (или первоначально - поместить в таблицу) запись с ключом key. Далее необходимо воспользоваться какой – либо схемой (алгоритмом) хеширования.

Схемы хеширования

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

Эти варианты и представляют собой две классические схемы хеширования:

- хеширование методом открытой адресацией с линейным опробыванием - linear probe open addressing.

- хеширование методом цепочек (со списками), или так называемое, многомерное хеширование - chaining with separate lists;

Метод открытой адресацией с линейным опробыванием.Изначально все ячейки хеш-таблицы, которая является обычным одномерным массивом, помечены как не занятые. Поэтому при добавлении нового ключа проверяется, занята ли данная ячейка. Если ячейка занята, то алгоритм осуществляет осмотр по кругу до тех пор, пока не найдется свободное место («открытый адрес»).

Т.е. элементы с однородными ключами размещают вблизи полученного индекса.

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

Метод цепочек является доминирующей стратегией.В этом случае i, полученной из выбранной хеш-функцией h(key)=i, трактуется как индекс в хеш-таблице списков, т.е. сначала ключ key очередной записи отображается на позицию i = h(key) таблицы. Если позиция свободна, то в нее размещается элемент с ключом key, если же она занята, то отрабатывается алгоритм разрешения конфликтов, в результате которого такие ключи помещаются в список, начинающийся в i-той ячейке хеш-таблицы. Например

В итоге имеем таблицу массива связных списков или деревьев.

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

- вычисление индекса i;

- поиск в соответствующей цепочке.

Для улучшения поиска при добавлении нового элемента можно использовать алгоритма вставки не в конец списка, а - с упорядочиванием, т.е. добавлять элемент в нужное место.

Пример реализации метода прямой адресации с линейным опробыванием. Исходными данными являются 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 до n-1 пробы на элемент, где n - размер хеш-таблицы..

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

struct zap {

int key; // Ключ

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

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

} data;

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

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

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