и 2 записи с ключами
- 4 957 397
- 0 597 397
Первая запись должна находиться в ячейке с номером 397 но и вторая запись имеет ото же адрес следовательно, запись с ключом 0 597 397 должна быть вставлена в другое место памяти. В этом случае методом разрешения коллизий является вычисление для этой записи нового адреса путем повторного применения хеш – функции в уже полученному адресу
zh [ h (key)] – т.е. вычисляется функция повторного хеширования.
В нашем случае zh (397,1000) = 970
т.к.
добавляется о при делении 3970 1000
1000 3
970 остаток
Если адрес 970 тоже занят, то хеширование выполняется до тех пор, пока не будет найден свободный адрес.
Повторное хеширование имеет ряд недостатков.
Во первых оно предполагает фиксированный размер таблицы. Если число записей, связанные с ростом базы данных, превысит этот размер, то необходимо выделять большую область памяти m1>m, а это ведет к новому отчислению всех адресов записей, уже находившиеся в базе.
Во вторых из таблицы трудно удалить запись.
Предположим, что в позиции р находиться запись z1. При добавлении некоторой записи z2, чей ключ к2 хешируется в р это запись должна быть вставлена в первую свободную позицию
zh (р), zh (zh (р)) и т.д.
Предположим, что z1 затем удаляется, т.е. позиция р становиться
свободной. Поиск записи z2 начинается с
позиции
с позиции р, но поскольку эта позиция уже свободна , то может быть вывод, что записи z2 нет вообще в базе.
Метод цепочек
В методе цепочек используется следующая структура:
Основная область Область переполнения
|
Адрес начала цепочки
|
|
|
|
в цепочкеУважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.