Здесь указатели удаляются из записей и организуются в специальные файлы-справочники (рис.10.1). Справочники занимают мало места, обычно полностью размещаются в оперативной памяти, что повышает скорость поиска данных.
Точка входа Файл-справочник Файл записей
К(а)
b1
b1
a1
^
a2 a 3 a4
a1
а
К(б)
b2
b2
a2
a1
a5 a6 a7
a2
б
К(в)
b3
b3
a3
a1
a8
a3
в
К(г)
b4
b4
a4
a1
a9 a10
a4
г
.....
.....
a5
д
a6
ж
a7
з
Указатели на основные Указатели на исходные Указатели на порож-
a8
и
записи
записи
записи
a9
к
a10
л
a11
м
Рис.10.1. Реализация древовидной структуры методом справочника
Для представления сетевых структур часто используют рассмотренные выше методы в определенной комбинации, позволяющей реализовывать сетевую структуру. Например, используют комбинацию методов с указателями на порожденные, подобные и исходные записи. Часто используют кольцевые структуры. Однако для сложных сетевых структур необходимо вводить для каждой записи переменный список указателей. При этом одни связи между записями в сети могут добавляться, другие устраняться. Это создает серьезные проблемы при создании соответствующих обслуживающих программ.
Сложность и трудоемкость организации и использования записей со встроенными указателями переменной длины приводит к целесообразности использования метода справочника (как и для древовидных структур). Чем сложнее структура данных, тем более целесообразно применять справочник.
Для реализации адресной функции "Ключ - Адрес памяти" возможны две группы методов: 1) адресная функция реализует взаимно однозначное соответствие адресов и ключей; 2) адресная функция реализует только однозначное преобразование ключа в адрес, но обратное преобразование не всегда имеет место (методы хеширования). Методы взаимно однозначного соответствия ключей и адресов используются двух видов.
1. Методы адресации с помощью ключа, эквивалентного адресу. Например, адрес записи счета печатается в расчетной книжке клиента Сбербанка и тогда при последующих обращениях к системе поиск записи счета клиента в БД осуществляется непосредственно по ключу-адресу.
2. Метод адресации с использованием алгоритма преобразования ключа в адрес. Предполагается линейная упорядоченность записей фиксированной длины в файле. В соответствии с размером записей и характером их упорядоченности составляется уравнение адресной функции. Недостаток метода - малое заполнение отведенной для файла памяти.
Методы хеширования называют еще методами перемешивания, методами рассеянной памяти, методами рандомизации. Здесь каждый экземпляр записи размещается с помощью программы хеширования в памяти по адресу, вычисляемому с помощью некоторой адресной функции (хеш-функции) по значению первичного ключа записи. При поиске записи выполняются те же самые вычисления и запись считывается из памяти по полученному адресу.
Недостатки методов хеширования: 1) последовательность расположения в памяти записей не совпадает с последовательностью, определяемой первичным ключом; 2) возможность коллизий, когда для двух различных записей (с разными значениями ключе) вычисляется один и тот же адрес памяти.
Хеш-функция h имеет не более М различных значений и удовлетворяет условию 0< h(k)<M для всех значений ключа kÎNк и однозначно определяет М по значению k. Обычно используются следующие методы построения хеш-функций.
1. Метод квадратов. Здесь значение ключа представляется целым двоичным числом и затем возводится в квадрат. Далее из ной части полученного результата выделяется l двоичных разрядов, которые интерпретируются как двоичный адрес памяти. Это можно промасштабировать по границам выделенного участка памяти умножением числа на подобранную константу. Недостаток метода квадратов: если в файле много ключей, заканчивающихся нулями, то воз ведение в квадрат вдвое увеличивает количество нулей и эти нули распространяются на среднюю часть квадрата ключа (адрес) и вызывают коллизии.
2. Метод деления. Здесь хеш-функция вычисляется по формуле h(k) = mod M. , т.е. ее значение равно остатку от деления значения ключа на число М . Рекомендуется в качестве М выбирать простое число, равное или близкое к размеру участка памяти. Например, если число записей равно 4096, то можно принять делитель 4093. Тогда для значений ключа 51844, 29100, 18, 37445, 37446 будут подучены следующие адреса: 2728, 449, 18, 608, 609.
3. Метод умножения. Он основан на следующем свойстве: если значения k равномерно распределены на отрезке [a,b], то и значения С-К равномерно распределены на отрезке [c-a, c-b]. Отрезок [c.a, c.b] отображается не пространстве адресов. Существует две способа построения схемы разрешения коллизий. 1. Метод открытой адресами. Он состоит в том, что при возникновении коллизий просматривается один за другим отведенные участки памяти до тех пор, рока не будет найден свободный ток, куда и помещается записью. При поиске записи последователь гость действий аналогична. Участки памяти просматриваются до тех пор, пока не будет найдена запись с нужным ключом. В данном методе обычно задается правило, согласно которому каждый ключ К определяет последовательность адресов в памяти) a0 =h(k), a1, a2 ..ank, которые надо просматривать каждый раз при вставке или поиске записи о ключом K. Если при поиске обнаружится свободная позиция, то это означает отсутствие записи в файле. Пример алгоритма формирования последовательности адресов ("линейное опробование): a0.=h(k); a1= h(k)-1; a2 = h(k)-2... aik=0; aik+1 = M-1; aik+2 = M-2;...; ank = h(k)+1.
Основной недостаток метода открытой адресации - вторичное скучивание. Первичное скучивание возникает, когда таблица содер жит много ключей о одинаковыми хеш-адресами. Вторичное окучивание возникает, когда имена о различными хеш-адресами имеют почти одинаковые последовательности адресов (в связи с работой алгоритма схемы разрешения коллизий), Чтобы избежать вторичное скучивание, принимают специальные меры. Например, алгоритм "двойное хеширование" в алгоритме "линейное опробование" формирует последовательность адресов о приращением Dk (а не "1"). 2. Метод цепочек. Здесь организуются М связанных линейных списков по одному на каждый возможный хеш-адрес.
После хеширования ключа, если участок памяти по вычисленному адресу свободен, выполняется размещение записи по этому адресу в основ ной области памяти. Если же указанный участок занят, то происходит обращение по указателю к следующему участку памяти (элементу списка из области переполнения), и так до конца списка. После это го запись помещается на свободный участок памяти и с помощью указателей подсоединяется к концу своего списка. При поиске записей действия выполняются в той же последовательности.
Точка входа Файл-справочник Файл записей
