Физическое представление данных, страница 5

и 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 нет вообще в базе.

Метод цепочек

В методе цепочек используется следующая структура:

                               Основная область                  Область  переполнения

К1                           a2

 
                               Адрес начала цепочки

Алгоритм хеширования

 
       Адрес следующего участка   

Запись

a1              K1            a1

a2              K2            a2

a7              K4            a14

a14              K5          ai

a1              K1            a1

 

Запись

 

К1,К2, К3

К2

 
                                                                                        в цепочке