В операционных системах и в системах управления базами данных широко используются способы размещения, основанные на преобразовании кода записи в ее адрес, которые обеспечивают прямой доступ к данным. Адрес хранения записи в этом случае определяется с помощью некоторой процедуры над кодом записи или ее ключом. При этом время обращения к памяти не зависит ни от расположения данных, к которым осуществлялось предыдущее обращение, ни от местоположения данных, к которым осуществляется текущее обращение.
Для вычисления адресов используют различные процедуры, осуществляющие линейные или нелинейные преобразования, в результате чего может определяться абсолютный или относительный адрес. Способ размещения по вычисляемому адресу используется как для организации данных в ОП — таблицы с прямым доступом, так и для организации данных на ВЗУ — файлы с прямым доступом.
Функции, осуществляющие процедуру над ключом и генерирующие адрес записи, называются функциями преобразования. В литературе по обработке данных эти функции называют часто рандомизирующими Основное требование, предъявляемое к функции преобразования, состоит в том, что она должна генерировать уникальный адрес.
Если все записи информационного массива имеют фиксированную длину и уникальные последовательные значения ключа, а диапазон возможных значений ключа не превышает диапазона адресов доступной памяти, то можно подобрать линейную функцию, обеспечивающую однозначность преобразования ключа в адрес хранения записи. Например, для вычисления адресов можно использовать следующее преобразование: ai = Кi - Р, здесь аi - номер или адрес записи, K i- значение ключа записи, Р ~ некоторое положительное число.
Пусть в массиве из 50 записей ключ принимает значения от 0201 до 0250. Выберем Р = 200. Тогда записи с ключами К = 0211 и К = 0241 будут занимать соответственно 11-ю и 41-ю позиции в массиве.
При использовании простейших линейных преобразований часть ячеек памяти останется незанятой. В этих случаях для вычисления адресов используют более сложные функции преобразования - функции хеширования или хеш-функции. Хеш-функция хеширует последовательность цифр или битов, определяющих значение ключа записи или ее кода, в результате чего получается хеш-адрес, по которому записи размещаются и ищутся. Так, например, хеш-функция разбивает ключ на несколько частей, которые затем суммируются таким образом, чтобы сформировалось число в требуемом диапазоне. Если мы, например, имеем восьмизначные ключи К = 97434658 и К = 31269857 и хотим отобразить их в трехзначные адреса, то можно проделать следующие операции:
h (97434658) = 974 + 346 + 58 = 378,
h (31269857) = 312 + 698 + 57 = 067.
Здесь символ h означает, что обработку ключа осуществляет хеш-функция. Для того чтобы вычисляемые адреса были трехзначными, сложение производится по модулю 1000. Результатом сложения по mod 1000 является остаток от деления суммы на 1000.
Функция хеширования должна обеспечивать однозначное преобразование ключа записи в ее адрес, причем адреса должны возможно более равномерно распределяться по области памяти, выделенной для хранения данных. В то же время хеш- функция не должна быть слишком сложной, поскольку время, необходимое для преобразований, добавляется к времени выполнения операций ведения, поиска или обработки. Хорошей считается такая хеш-функция, которая быстра и генерирует уникальные и достаточно равномерно распределенные адреса.
Известны различные хеш-функции, каждая из которых обеспечивает хорошие результаты при конкретном распределении значений ключа. Однако даже наилучшая хеш-функция не устраняет полностью возможность получения одинаковых адресов. Почти неизбежны коллизии, т.е. ситуации, когда различные записи получают один и тот же адрес.
Существуют различные методы разрешения коллизий. При использовании одного из них хеш-адрес подвергается рехешированию, заключающемуся в определенных преобразованиях адреса. Например, хеш-адрес, находящийся в коллизии, может быть умножен на константу, в результате чего получится новый адрес. Подобные преобразования могут выполняться неоднократно до тех пор, пока не будет сгенерирован адрес ячейки памяти, являющейся свободной. При поиске записи выполняется та же последовательность преобразований.
Другой метод устранения коллизий заключается в использовании сгенерированного адреса в качестве начальной точки для последовательного просмотра. С этого адреса начинается поиск свободного места в памяти.
На практике наиболее распространен следующий метод использования вычисленных адресов, позволяющий устранять коллизии. Адрес, генерируемый рандомизирующей процедурой, считается адресом хранения не одной конкретной записи, а области памяти, или страницы памяти, в пределах которой размещаются все записи, получившие этот адрес. В пределах страницы записи могут размещаться последовательно в порядке поступления или в соответствии с каким-либо установленным логическим порядком. Если со временем страница окажется заполненной, в памяти выделяется новая страница, связываемая с предыдущей указателем.
Хеш-функция может генерировать абсолютный адрес страницы или ее номер. В последнем случае создается справочник, в котором номерам страниц ставится в соответствие их абсолютный адрес на ВЗУ или в ОП. Справочник страниц хранится в ОП. Обычно предпочтение отдают относительной адресации, так как при этом обеспечивается большая независимость данных. Данные могут перемещаться в памяти без изменения программ обработки, необходима лишь соответствующая коррекция
справочника. На рис. 9.27 показана схема размещения записей при генерации хеш-функцией номеров страниц памяти.
При поиске, модификации и исключении записей над заданным ключом производятся те же преобразования, что и при размещении. Если на данной странице записи не оказалось, то просматриваются страницы переполнения.
При выполнении операции модификации в найденную запись вносятся необходимые изменения и запись размещается по прежнему адресу. Если модификации подвергается ключевое поле, то запись удаляется. Новое значение ключа обрабатывается рандомизирующей процедурой и запись размещается в соответствующей области памяти.