Хеширование. Методы разрешения коллизий.
Хеширование - технология быстрого прямого доступа к хранимой записи на основе заданного значения некоторого поля, которое может быть доже не ключевым.
Каждая запись БД размещается по адресу, вычисляемому путем применения к значению ключа некоторой функции свертки (хэш-функция), вырабатывающей значение меньшего размера. Для эффективного использования дискового пространства необходим подбор хэш-функции.
Свертка ключа используется и для доступа к записи. В самом простом случае свертка используется как адрес в таблице, содержащей ключи и записи.
Основным требование к хэш-функции является равномерное распределение значений свертки, где одному значению хэш-функция может соответствовать одно значение ключа. Если для нескольких значений ключа получается одно и то же значение хэш-функция – коллизия.
Значения ключей, которые имеют одно и то же значение хэш-функции – синонимы.
Методы разрешения коллизий
Метод последовательного перебора. Значение хэш-функции – отправная точка для дополнительного просмотра и поиска. Запись сохраняется в первом свободном месте.
Стратегия разрешения коллизий с областью переполнения. Область хранения разбивается на две части: основную и область переполнения. Значение хэш-функции – адрес записи, запись заносится в основную область. Если при вставке нового значения возникает коллизия, то новая запись заносится в область переполнения на первое свободное место, а записи-синониме в основной области делается ссылка на адрес вновь размешенной записи в области переполнения. Следующая новая запись-синоним будет располагаться на втором месте списка. Т. о. для размещения новой записи требуется не более двух обращений к диску. Хорошим результатом может считаться наличие не более 10 синонимов.
Организация стратегии свободного размещения. Одна общая область замещения. Записи-синонимы организуются в двухсвязный список.
Если при вставке новой записи ее адрес занят записью, которая не является заголовком списка, то она перемещается на свободное место с коррекцией указателей. А новая запись встает на ее место.
Если адрес занят заголовком списка, то новая запись располагается на свободном месте, и для нее устанавливаются соответствующие указатели.
Если адрес свободен, то новая запись размещается в заданном месте и становится заголовком в списке синонимов.
