Алгоритмы и структуры данных на С++. Аксёнова Е.А - 78 стр.

78                                                      Глава 6. Поиск


возникнуть коллизия, т. е. ситуация, когда K1 6= K2 , а h(K1 ) = h(K2 ).
Существует несколько алгоритмов разрешения коллизий с использо-
ванием хеш-функции.




                               Рис. 6.4

     Хеш-функцию надо выбирать таким образом:
     1) хеш-функция должна быстро вычисляться;
     2) хеш-функция должна минимизировать число коллизий.
   Пусть элементы таблицы пронумерованы от 0 до n − 1. Можно вы-
брать в качестве хеш-функции h(K) = K%n, где n – размер таблицы.

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

     struct node{int p; int key; int link;},

где p – признак занятости узла (p = 0 – узел свободен, p = 1 – узел
занят), key – поле ключ, link – указатель на следующий элемент
связного списка (этот элемент в данной реализации имеет целый тип,
т. к. в качестве адресов мы используем индексы элементов массива
node table[n+1]).
    Узел table[0] в таблице всегда свободен. Для облегчения поиска
свободных мест в таблице будет использоваться переменная R. В на-
чале работы R = n + 1. В процессе работы table[i] заняты для всех
R ≤ i ≤ n.