Прямой метод доступа. Хеширование

Этот метод имеет наибольшую эффективность доступа, в то же время эффективность хранения наименьшая. Этот метод обеспечивает непосредственный прямой доступ к требуемой записи по действительному адресу памяти. Несмотря на то, что ключи упорядочены, они идут не подряд. Это объясняется тем, что в прямом методе доступа резервируются дополнительные места для записей ключей. Причем, они резервируются даже для отсутствующих ключей.

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

Преобразованному ключу ставится в соответствие адрес с 1001 до 1011. Все ячейки с 1002 до 1011 являются пустыми. Это и есть зарезервированная память. Чтобы избавиться от основного недостатка в прямом методе доступа (а именно, значительного резервирования памяти), применяют методы хеширования.

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

Отметим, что записи, имеющие одинаковые значения преобразованного ключа называются синонимами. Таким образом, в памяти записи-синонимы образуют так называемую цепочку. Отметим, что адрес записи занимает одну ячейку.

Исходные значения ключей	Преобразованные значения ключей
1-100 (синонимы) 201-400 401-600 601-800

Существует несколько способов хеширования. Например, память делится на основную область и область переполнения. Записи в основной области могут быть блокированы. Означает, что в основной области подряд располагается несколько записей-синонимов. Если коэффициент блокировки k_блок =3, то подряд можно размещать не более 3-х записей-синонимов. Все остальные записи будут размещаться в области переполнения. Таким образом, при этом избегаем резервирования памяти. Длина цепочки не должна быть большой т.к. из-за этого значительно ухудшается эффективность доступа к памяти.

В другом методе хеширования память не делится на основную и область переполнения. Если адрес занят в другой записи, то эта запись вытесняется. В этом варианте хеширования эффективность хранения выше, но ниже эффективность доступа.