Лекция №22

Название лекции: Хешированные файлы.

План:

1. Основной принцип организации хешированных файлов.

2. Выбор функции хеширования.

3. Схема организации хешированного файла.

4. Организация поиска в хешированном файле.

5. Модификация в хешированном файле.

6. Включение в хешированном файле.

7. Удаление в хешированном файле.

1. Основной принцип организации хешированных файлов.

Решается задача: по ключу найти запись.

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

Пусть v есть значения ключа. Тогда значение h(v) есть номер участка, в котором должна находится запись с этим значением ключа, если она вообще присутствует в файле.

При выборе функции h желательно, чтобы h(v) принимала все её возможные значения (от 0 до N) примерно с равной вероятностью, когда v принимает всевозможные допустимые значения ключа.

2. Выбор функции хеширования сложная проблема (есть много литературы). Во многих ситуациях полезна следующая стратегия:

1) Интерпретируем значение ключа как последовательность бит, сформированную путем конкатенации значений всех полей ключа. Эта последовательность имеет фиксированную длину, поскольку каждое поле имеет фиксированную длину.

2) Делим последовательность бит на группы, состоящие из фиксированного числа бит. (из 16 бит). Последнюю группу при необходимости дополняем нулями.

3) Складываем полученные группы бит как целые числа.

4) Делим полученную сумму на число участков и используем остаток от деления как номер участка.

Пример: →как распределяется остаток от деления. m>n остаток [0, … n-1].

3. Схема организации хешированного файла.

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

Рассмотрим структуру блока:

В каждом блоке предусмотрено место для размещения фиксированного числа записей. Если запись требует r байт, то для чтения, например, пятой записи внутри блока требуется сделать смещение 4r байт, от первого байта, следующего за заголовком блока.

Пространство, используемое для хранения одной записи будем называть субблоком.

Во «время жизни» файл может оказаться, что некоторый субблок свободен (запись из него была удалена) в то время, как следующие за ним субблоки заняты. Для того, чтобы как-то различать записанные и свободные субблоки возможны два метода:

- в освобождаемый субблок помещают последовательность бит, которая никогда не может появиться в записи (это описано, т.к.…пути господни неисповедимы).

- в блоке отводят 1 бит на каждый субблок. Его нулевое значение – субблок свободен, 1– субблок занят.

Иногда отводят ещё один бит (в заголовке или в записи) который показывает была ли удалена запись, что бы избежать повторное использование субблоков, на которые была ссылка в случае закреплённых записей.

4. Организация поиска в хешированном файле.

Задача: найти запись с ключом v. (v– одно поле или список полей в фиксированном порядке– тогда vконкатенация полей).

Вычислим h(v) получая номер участка i. Прочтём справочник участков и найдем адрес первого блока участка i. Читаем первый блок, анализируем субблоки на совпадение ключа. Если найдено – поиск успешен – конец. Если нет – читаем следующий блок данного участка. Если его нет – поиск не успешно.

5. Модификация в хешированном файле.

Задача: изменить одно или несколько полей записи с ключом v.

1) Найти запись с ключом v. Если не найдена – аварийный останов.

2) Найдена запись:

а) среди модифицированных полей есть хотя бы одно, которое входит в ключ, следовательно, удалить найденную запись из базы и затем добавить измененную;

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

6. Включение в хешированном файле.

Задача: добавить запись с ключом v.

1) Найти запись с ключом v (вычисляется номер участка, куда надо добавить запись). Если запись найдена, аварийный останов. Иначе:

2) Найдем первый свободный субблок среди блоков участка h(v) (этот субблок может быть в середине, если ранее было удаление с освобождением субблока, т.е. записи не закреплены). Адрес этого субблока можно запомнить при поиски ключа v. Помещаем запись в данный субблок → записываем блок на место. Если свободного места нет → получаем свободный блок из OС. Организуем цепочку с последним блоком участка h(v) → пишем блок на диск.

7. Удаление в хешированном файле.

Задача: удаление записи с ключом v.

1) Найти запись с ключом v. Если не найдена, то аварийный останов. Иначе:

2) Если запись найдена, то:

а) если записи не закреплены →бит свободен/занят в состояние свободен (при следующем добавлении субблок будет использован);

б) если записи закреплены →бит свободен/занят не изменяется, а бит удалён установить в состояние 1– удалён.

Если записи не закреплены, то возможно для удаления использовать следующий алгоритм → последнюю запись файла переписать на место удаленной, а последний субблок освободить.