Стр. 65 - Основы алгоритмов и структур данных
Упрощенная HTML-версия
63
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
Без учета возможности коллизий, независимо от схем хеширования,
алгоритмы работы с хэш-таблицей имеют следующий вид:
включение Z.
M
h(z)
= z
(
M
с адресом
h
(
z
) принимает значение
z
),
исключение Z.
M
h(z)
=
λ,
поиск Z:
if M
h(z)
= z then <успех > else <неуспех >,
распечатка таблицы :
do i=1 to m-1;
if (Mi≠
λ
) then < печать i, Mi >6;
4.9.2. Разрешение коллизий
Пока хэш-таблица достаточно пуста (заполнена примерно на 50%),
коллизии возникают редко и общая производительность схемы хэширования
определяется прежде всего временем, требуемым на вычисление хэш-функции.
При большем заполнении таблицы число коллизий резко возрастает.
Поэтому для реальных задач эффективность разрешения коллизий становится
доминирующим фактором, т.е. выбор схемы разрешения коллизий важнее
выбора хэш – функции.
Любая схема разрешения коллизий каждому ключу
х
ставит в соответствие
некоторую последовательность адресов:
А
0
=
h
(
x
),
A
1
=
ω
1
(
A
0
,
x
),
A
2
=
ω
2
(
A
1
,
x
), и т.д.
4.9.3. Линейная схема разрешения коллизий
Например, часто используется линейная схема разрешения коллизий:
А
0
=
h
(
x
),
А
1
=
А
0
+1,
…,
А
i
+1
=
A
i
+1.
Во всех схемах разрешения коллизий каждый новый адрес следует брать
по модулю
n
, где
n
– размер таблицы.
Тогда
алгоритм включения
принимает следующий вид:
A = h(z);
while (M(A) < >
λ
) && (M(A) < > z)
{
A = A+
1
;
}
if M(A) == z then <неуспех – z уже есть в таблице>
else M(A) = z;
