Если каталог очень большой (несколько тысяч файлов), последовательное чтение каталога мало эффективно.
1 Использование хэш-таблицы для ускорения поиска файла.
Алгоритм записи файла:
· Создается хэш-таблица в начале каталога, с размером n (n записей).
· Для каждого имени файла применяется хэш-функция, такая, чтобы при хэшировании получалось число от 0 до n-1.
· Исследуется элемент таблицы соответствующий хэш-коду.
· Если элемент не используется, туда помещается указатель на описатель файла (описатели размещены вслед за хэш-таблицей).
· Если используется, то создается связный список, объединяющие все описатели файлов с одинаковым хэш-кодом.
Алгоритм поиска файла:
· Имя файла хэшируется
· По хэш-коду определяется элемент таблицы
· Затем проверяются все описатели файла из связного списка и сравниваются с искомым именем файла
· Если имени файла в связном списке нет, это значит, что файла нет в каталоге.
Такой метод очень сложен в реализации, поэтому используется в тех системах, в которых ожидается, что каталоги будут содержать тысячи файлов.