Общей идеей методов хэширования является применение к значению ключа некоторой
функции свертки (Хэш-функции), вырабатывающей значение меньшего размера. Свертка
значения ключа затем используется для доступа к записи. В самом простом случае свертка
ключа используется как адрес в таблице, содержащей ключи и записи.
В реальности записи файла разделяются между участками, каждый из которых
содержит один или несколько блоков памяти. В этом случае хеширование обеспечивает
прямую адресацию записи путем преобразования значения первичного ключа в абсолютный
или относительный адрес участка.
Пусть v есть значение ключа записи и h – Хеш-функция. Тогда h (v) - адрес участка, в котором должна находиться искомая запись (в том случае, если она присутствует вообще). Общая схема организации хешированного файла представлена на рис.26.
Проблема синонимов
при реализации Хеш-функции отношения 1:1 между значениями ключей и номерами участков размер справочника участков становиться неприемлемо большим, а величина самих участков неприемлемо малой=>к нерациональному расходу памяти.
Реальным выходом из этой ситуации является принятие соглашения, при котором в общем случае Хеш-функции осуществляет отображение типа 1:M; однако в этом случае фиксируется эффект возникновения синонимов, когда записи с различными значениями ключей направляются для хранения в один участок, что приводит, в конечном счете, к различной степени загруженности участков.
И, если при использовании связанной последовательной организации блоков внутри участков (именно такая организация представлена на рис.26.) наличие синонимов приводит, в основном, только к различию во времени поиска в пределах отдельных участков, то при использовании физически последовательной организации могут возникнуть дополнительные проблемы, связанные с необходимостью введения области переполнения (рис.27.).
Очевидно, что возникновение слишком большого количества цепочек переполнения ведет к потере главное преимущества хэширования - доступа к записи практически всегда за одно обращение. Переход на использование новой хэш-функции (со значением свертки большего размера) требует перестройки всех участков основного файла, что в случае баз данных являются абсолютно неприемлемым. Поэтому обычно вводят промежуточные таблицы-справочники, содержащие значения ключей и адреса записей, а сами записи хранятся отдельно. Тогда при переполнении справочника требуется только его переделка, что вызывает меньше накладных расходов.
Замечание. Конечно, структура самой области переполнения может быть связанной последовательной или физически последовательной.
