Перед началом работы имеем две таблицы (можно иметь одну таблицу, разделенную на две части). Первая таблицы называется адресуемой. Вторая – областью переполнения. При вычислении адреса ключа мы можем попасть только в первую таблицу. Если получена коллизия, то новый ключ записывается в область переполнения. Адресная ссылка в первой таблице всегда указывает адрес в области переполнения.
Пусть адресуемая таблица имеет 10 строк. Область переполнения - 6 строк.
Следует записать ключи 11, 21, 22, 2, 26, 6, 31.
Адресуемая таблица:
Адрес Ключ Адресная ссылка
0
1 11 0
2 22 1
3
4
5
6 26 2
7
8
9
Область переполнения:
Адрес Ключ Адресная ссылка
0 21 3
1 2 -1
2 6 -1
3 31 -1
4
5
После удаления ключа 11 имеем.
Адресуемая таблица:
Адрес Ключ Адресная ссылка
0
1 21 3
2 22 1
3
4
5
6 26 2
7
8
9
Область переполнения:
Адрес Ключ Адресная ссылка
0
1 2 -1
2 6 -1
3 31 -1
4
5
Если вновь добавим ключ 11, то в области переполнения получим следующую картину:
Адрес Ключ Адресная ссылка
0 11 -1
1 2 -1
2 6 -1
3 31 0
4
5
ХУЙ ПИЗДА УПЯЧКА