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

При выборе этой стратегии область хранения разбивается на две части:

• основную область;

• область переполнения.

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

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

Содержание записей	Ссылка на синонимы
Петров	1
Сергеев	3

Область переполнения:

Содержание записей	Ссылка на синонимы
Петрова	2
Петровский
Сергиенко

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

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

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

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

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