Стр. 71 - Основы алгоритмов и структур данных
Упрощенная HTML-версия
69
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
4.9.5. Метод цепочек
Все
вышеописанные
методы
реализовывали
включение
как
последовательность обращений к ячейкам с адресами
А
0
,
А
1
,
А
2
и т.д. При
поиске адреса
А
0
,
А
1
,
А
2
… также последовательно вычисляются, как и при
включении. Этого повторного вычисления адресов можно избежать, если
применить связные списки: каждому имени
x
i
хранящемуся в ячейке
M
(
A
k
)
будет сопоставлена ссылка на ячейку, в которой хранится следующий элемент
из данной коллизии.
Пример:
Пусть
A
k
=(
h
0
(
x
)+
k
)mod
m
;
0
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15
имена
h
–
функции
2
3
4
2
7
8
7
7
11 8
ссылки
5
-
9
12 10 -
-
-
Включаем элемент
z
с
h
0
(
z
)=7/
В ячейке
A
0
(
z
)=7 уже есть другое имя (т.е. имеем здесь коллизию).
Вместо того, чтобы анализировать, занята ли ячейка
A
1
=
A
0
+1=8, мы сразу
переходим к ячейке 9 (по ссылке). Далее к ячейке 10. Здесь уже нет ссылки.
Далее,
A
3
=
A
2
+1=10+1=11 – занята;
A
4
=
A
3
+1=11+1=12 – занята;
A
5
=
A
4
+1=12+1=13 – свободна.
Помещаем
z
в ячейку 13, а в ячейке 10 ставим ссылку 13.
Пример
Включение элемента
z
с
h
0
(
z
)=8 в связный список потребует двух итераций,
вместо пяти, в базовом варианте.
Алгоритм включения / исключения / поиска – самостоятельно!
