Организация хешированных файлов

1.5.1 Статическое хеширование

Основная идея хешированных файлов состоит в том, что записи разбиваются на бакеты согласно значению ключа.

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

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

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

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

Более популярный альтернативный метод основан на перемешивании на основе остатка от деления.

Таким образом, пусть имеется таблица сегментов, содержащая В указателей, по одному на каждый сегмент. Каждый указатель в таблице сегментов представляет собой физический адрес первого блока связного списка блоков для соответствующего сегмента. Сегменты пронумерованы от 0 до (В-1). Хеш-функция h отображает каждое значение ключа в одно из целых чисел от 0 до (В-1).

Если х - ключ, то h(x) является номером сегмента, который содержит запись с ключом х (при условии существования такой записи). Блоки, составляющие каждый сегмент, образуют связный список. Таким образом, заголовок i -го блока содержит указатель на физический адрес (i+1) -го блока. Последний блок сегмента содержит в своём заголовке NIL-указатель.

Рисунок 5 – Схема организации хешированного файла

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

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