В операционных совокупностях и в совокупностях управления базами данных активно применяются методы размещения, основанные на преобразовании кода записи в ее адрес, каковые снабжают прямой доступ к данным. Адрес хранения записи в этом случае определяется посредством некоей процедуры над кодом записи либо ее ключом. Наряду с этим время обращения к памяти не зависит ни от размещения данных, к каким осуществлялось прошлое обращение, ни от расположения данных, к каким осуществляется текущее обращение.
Для вычисления адресов применяют разные процедуры, осуществляющие линейные либо нелинейные преобразования, в следствии чего может определяться полный либо относительный адрес. Метод размещения по вычисляемому адресу употребляется как для организации данных в ОП — таблицы с прямым доступом, так и для организации данных на ВЗУ — файлы с прямым доступом.
Функции, осуществляющие процедуру над ключом и генерирующие адрес записи, именуются функциями преобразования. В литературе по обработке данных эти функции именуют довольно часто рандомизирующими Главное требование, предъявляемое к функции преобразования, пребывает в том, что она обязана генерировать неповторимый адрес.
В случае, если все записи информационного массива имеют фиксированную длину и неповторимые последовательные значения ключа, а диапазон вероятных значений ключа не превышает диапазона адресов дешёвой памяти, то возможно подобрать линейную функцию, снабжающую однозначность преобразования ключа в адрес хранения записи. К примеру, для вычисления адресов возможно применять следующее преобразование: 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 продемонстрирована схема размещения записей при генерации хеш-функцией номеров страниц памяти.
При поиске, модификации и исключении записей над заданным ключом производятся те же преобразования, что и при размещении. В случае, если на данной странице записи не выяснилось, то просматриваются страницы переполнения.
При исполнении операции модификации в отысканную запись вносятся запись и необходимые изменения размещается как и раньше адресу. В случае, если модификации подвергается главное поле, то запись удаляется. Новое значение ключа обрабатывается рандомизирующей процедурой и запись размещается в соответствующей области памяти.