Операция включения элемента в таблицу.

Date: 2015-10-07; view: 472.

Перед включением элемента в таблицу определяют его адрес с помощью хеш-функции: A = h(K), где K – ключ, а А – адрес элемента таблицы, причем 0 £ А £ N-1, т.е. хеш-функция – отображение множества ключей на множество адресов.

A = K mod N = (C₁ * k + C₂) mod N, где N – количество адресов в таблице.

“Хорошая” хеш-функция – это функция, которая быстро вычисляется и минимизирует количество коллизий. Коллизия – это ситуация, когда для разных ключей адрес один и тот же, т.е. h(k_i) = h(k_j), где i ¹ j. Минимизации можно добиться, если равномерно распределить элементы по адресному полю таблицы.

После вычисления адреса элемента таблицы есть две возможности размещения элемента:

1) поместить этот элемент по адресу, если адрес свободен;

2) если вычисленный адрес занят, то повторить хеширование, т.е. совершить рехеширование по следующей формуле: A1 = (A+C) mod N.

Таким образом, алгоритм включения элемента в таблицу будет иметь следующий вид:

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

2. Если вычисленный адрес таблицы занят, то перевычисляем адрес (проводим рехеширование) и переходим к п.1.

Чтобы процесс размещения элементов был равномерным, адресное поле таблицы делается больше множества ключей на 10-15%.

Операция исключения элемента из таблицы:

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

2. Если по вычисленному адресу располагается искомый ключ, то запись найдена и ее удаляют. Конец алгоритма.

3. Если вычисленный адрес пуст, то элемента с заданным ключом в таблице нет. Конец алгоритма.

4. Если элемент таблицы содержит другой ключ, то перевычисляем (рехешируем) адрес и переходим к п.2.