Методы рендомезации или хэширования

Методы 1-ой группы

Файловая организация данных.

Стратегия поиска данных в памяти ЭВМ

Современные СУБД облд-т высоким быстродействием поиска инф в БД. Это быстродействие реализ за счет 2х методов

– 1.Использование SQL для запросов. Это реляционный язык, кот использует элементы реляц алгебры и реляц исчисления кортежей. В реляционной системе запросов сущ возм-ть выбора эффективности стратегии д/вычисл реляцион выражения. Этот процесс выполняет оптимизатор. Он позволяет сократить кол-во операций, кот необходимы для выполнения запросов.

- 2. Работа с совр структурами таблиц.

Циклический список

Это связ лин список, замкнутый кольцом(кольцевая структура)

Голова списка – фиксированная стр-ра с заданным адресом. В ней располагается указатель на 1й узел, служебная инф, а именно идентификатор списка, колво узлов в списке.

Наряду с однонаправленными исп-ся 2х направл цикл списки, где вводятся указатели и можно проходить по этим спискам в обр сторону.

Существует 3 типа указателей – действительный, относительный и символический.

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

Оносит адреса – позволяют размещать узлы в люб месте памяти и на разл устройствах без изменений значений указателей, изменяется только базовый адрес.

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

В этом методе исп. Некотор. выч операция, котор. Преобраз значение ключа в соотв. Адрес памяти.

Эти методы дел-ся на 2 группы:

1) методы, в котор адресная фун-я реализует взаимно-однознач соотв адресов и ключей

2) методы рандемизации или хемирования в котор адресная фун-я реализ только однознач соотв вид ключа и адреса записи, обратное преобр-е – невозможно

а) методы адресации с помощью ключа, эквивал адресу.

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

Они основаны на вероятностных алгоритмах. Адресная фун-я которая строится на вероят-ых алгоритмах наз-ся хэш-функция.

Методы построения хэш-фун-ий:

- метод квадратов;

- деления;

- умножения;

- сдвига разрядов;

- преобр-я основания счисления;

- деления номиналов;

Метод постр-я хэш-фун-ий выбирают по 2 критериям:

1) плотность заполнения адресного простр-ва;

2) min кол-во поллизионных ситуаций

По этим признакам лучшим явл метод деления.

Метод деления

h(key)=mod(key, m)

h() – хэш-фун-я

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

m – число близкое к max размеру адресного пр-ва, отведённого для записи

mod – остаток от деления значения key на m

Метод разрешения коллизий

1. метод открытой адресации

2. метод цепочек

Метод открытой адресации

h(key)=mod(key, 1000)

key1=4957397

key2=0597397

h(key1)=397

h(key2)=397

rh(h(key2))=mod(397/1000)=mod(3970/1000)=970

Недостатки метода повторного хэширования

1) мы имеем фиксир-ый размер таблицы где размещаются значения

2) связан с удалением записи из адресного пр-ва

Если удалить r1 и попытаться найти r2, т о нам будет сказано, что в позиции P такой записи не сущ-ет.

Метод цепочек

В нём исп- ся след струк-ра:

Дата добавления: 2015-01-03