9.Способ хранения, основанный на преобразовании ключа записи в ее адрес.

Способы размещения данных в памяти, основанные на преобразовании ключа записи в ее адрес обеспечивает прямой доступ к данным по значению ключа, адрес хранения записи в этом случае определяется с помощью некоторой процедуры выполняемой над ключом записи или над кодом записи. Время обращения к любой записи при таком способе хранения не зависит от места расположения записи в памяти.

Способ размещения по вычисленному адресу используется для размещения данных как в ОП (таблицы с прямым доступом) так и хранение на ВЗУ ( файлы с прямым доступом).

Для вычисления адресов используются различные процедуры выполняющие линейные или нелинейные преобразования ключа записи или ее кода. В результате преобразования может определяться физический адрес записи, индекс элемента массива содержащего запись, номер в файле. Функцию, выполняющую процедуру над ключом и генерирующую адрес записи, называется функцией преобразования. В литературе по обработке данных такие функции часто называют рандомизирующими процедурами (random access). Основное требование, применяемое к функции преобразования, состоит в том, что она должна генерировать уникальный адрес для каждой записи. При выборе функции преобразования оценивается характер данных. В тех случаях, когда записи информационного массива имеют фиксированную длину, уникальное последовательное значение ключа, диапазоне возможных значений ключа не превышает диапазона адресов доступной памяти. В этом случае можно подобрать линейную функцию, обеспечивающую однозначное преобразование значения ключа в адрес хранения записи с этим ключом. Пусть, например, в основной памяти необходимо разместить 50 записей фиксированной длины ключи, которых принимают значения k=0201÷0250. Для хранения записей используем структуру массива. Объявим массив на 50 элементов. Таким образом, выделим для хранения записей адреса 1÷50. Используем следующие преобразования a_i=k_i-p,

a_i – номер или адрес записи

k_i – значение ключа записи

p – некоторое положительное число

Выбираем р=200, тогда запись с ключом 211 получит адрес 11, а запись с ключом 241 получит адрес 41.

Для размещения и последовательного доступа к любой записи потребуется значение ее ключа пересчитать в индекс массива, после этого к любой записи возможен прямой доступ по вычисленному адресу. Реальные данные не всегда удовлетворяют условиям и линейные функции преобразования оказываются непригодными, так например, если значения непоследовательны и имеют большой разброс значений, то при использовании линейной функции многие ячейки памяти останутся незанятыми. Для вычисления адресов в таких случаях используют более сложные функции преобразования, чаще всего для вычисления адресов оказываются пригодными хешированные функции (хеш-функции). Хеш-функция хеширует, т.е крошит на мелкие кусочки и определенным образом их перемешивает последовательность цифр или битов определяющих значение ключа записей или кода записей в результате получается значение ячейки памяти по которой размещается запись с этим ключом. Рассмотрим, как работает функция хеширования, преобразующая ключ по методу свертки. Эта функция разбивает ключ на несколько частей, которые затем суммируются таким образом, чтобы сформировалось число в нужном диапазоне, т.е. в диапазоне допустимых значений адресов. Пусть, например, записи имеют восьмизначные ключи

974 364 58

312 698 57

Их необходимо преобразовать в трехразрядные адреса. Выполним следующие операции

h(974 364 58)= 974 + 364 + 58=378

h(312 698 57)= 312 + 698 + 57=067

Для того чтобы вычисляемые адреса получились трехразрядными сложение выполним по модулю 1000, результатом такого сложения по модулю 1000 является остаток от деления полученной суммы на 1000. Функция хеширования должна удовлетворять следующим требованиям: генерировать уникальный адрес, обеспечивать однозначное преобразование ключа записи в ее адрес, т.е. данному ключу всегда должен соответствовать один и тот же адрес, полученные адреса должны, возможно, более равномерно распределяться по памяти, хеш-функция не должна быть слишком сложной т.к. время необходимое для ее вычисления добавляется ко времени выполнения операций ведения и поиска. Хорошей считается хеш-функция ,которая быстро генерирует уникальные и достаточно равномерно распределенные адреса. Известны различные хеш-функции, каждая из которых дает хорошие результаты при конкретном распределении значений ключа. Но даже самая лучшая хеш-функция не исключает возможности получения одинаковых адресов для различных значений ключа. Почти неизбежны ситуации когда различные записи получают один и тот же адрес, такая ситуация называется коллизией. Рассмотрим, как одна из наиболее распространенных функций хеширования основанная на методе деления приводит к возникновению коллизии. Эта функция имеет следующий вид h(K)=k mod m+1, m – делитель. Для вычисления h(K) ключ записи K делится на m и остаток увеличивается на 1. m=101

2000,2001,…,2017,…

82,83,…,99,…

Рассчитаем адреса записей с ключами:

3313,3314, …, 3330

82,83,…,99,…

Существуют различные методы разрешения коллизии при использовании одного из них хеш-адрес, вступивший в коллизию, подвергается рехешированию, т.е. определенным образом преобразуется. Например, полученный адрес может быть умножен на константу, в результате получится новый адрес, подобные преобразования могут выполняться неоднократно до тех пор, пока не будет сгенерирован свободный адрес.

На практике чаще используется следующий прием позволяющий разрешить коллизию. Адрес, генерируемый рандомизирующей функцией, считается адресом не одной конкретной записи, а адресом области памяти или адресом страницы памяти. В пределах этой страницы размещаются все записи, получившие одинаковый адрес (адрес этой страницы)

На странице записи могут располагаться последовательно в порядке поступления или в соответствии с каким-либо другим логическим порядком. Если со временем основная страница окажется заполненной в памяти выделяется новая страница – страница переполнения, которая связывается с основной страницей указателем. При поиске и удалении записи над ключом выполняются такие же преобразования, которые выполнялись при размещении записей. На странице записи просматриваются последовательно, если на основной странице нужной записи не оказалось, то просматривается страница переполнения. Рандомизирующая процедура может генерировать или физический адрес страницы памяти (А) или номер страницы (N). В последнем случае создается справочник, в котором указаны номера страниц и соответствующие им физические адреса ОП или ВП. При редактировании записи в нее вносят необходимые изменения, а затем размещают по прежнему адресу. Если редактируется ключевое поле, то адрес вновь вычисляется и запись размещается по новому адресу. С помощью функции преобразования может вычисляться не только адрес хранения записей, но и индекс элемента массива с нужной записью или порядковый номер записи в файле.