Стратегия разрешения коллизий с областью переполнения

Первая стратегия условно может быть названа стратегией с областью переполнения. При выборе этой стратегии область хранения разбивается на 2 части:

О основную область; О область переполнения.

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

Основная область:

Если вновь заносимая запись имеет значение функции хэширования такое же, которое использовала другая запись, уже имеющаяся в БД, то новая запись за­носится в область переполнения на первое свободное место, а в записи-синони­ме, которая находится в основной области, делается ссылка на адрес вновь раз­мещенной записи в области переполнения. Если же уже существует ссылка в записи-синониме, которая расположена в основной области, то тогда новая запись получает дополнительную информацию в виде ссылки и уже в таком виде заносится в область переполнения.

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

Рассмотрим теперь механизмы поиска произвольной записи и удаления записи для этой стратегии хэширования.

При поиске записи также сначала вычисляется значение ее хэш-функции и счи­тывается первая запись в цепочке синонимов, которая расположена в основной области. Если искомая запись не соответствует первой в цепочке синонимов, то далее поиск происходит перемещением по цепочке синонимов, пока не будет обнаружена требуемая запись. Скорость поиска зависит от длины цепочки си­нонимов, поэтому качество хэш-функции определяется максимальной длиной цепочки синонимов. Хорошим результатом может считаться наличие не более 10 синонимов в цепочке.

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

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

Дата добавления: 2015-05-09