Лінійний пошук

Існує декілька стратегій проглядання списку символьних імен. Простим з них є лінійний пошук. Директорія є видимою із самого початку, поки не зустрінеться потрібне ім'я файлу. Хоча це найменш ефективний спосіб пошуку, виявляється, що в більшості випадків він працює з прийнятною продуктивністю. Наприклад, автори Unix стверджували, що лінійний пошуку цілком достатньо. Мабуть, це пов'язано з тим, що на тлі відносного повільного доступу до диска деякі затримки, що виникають в процесі сканування списку, неістотні.

Метод простий, але вимагає тимчасових витрат. Для створення нового файлу спочатку потрібно перевірити директорію на наявність такого ж імені. Потім ім'я нового файлу вставляється в кінець директорії (якщо, зрозуміло, файл з таким же ім'ям в директорії не існує, інакше потрібно інформувати користувача). Для видалення файлу потрібно також виконати пошук його імені в списку і помітити запис як невживану.

Реальний недолік даного методу - послідовний пошук файлу. Інформація про структуру директорії використовується часто, і неефективний спосіб пошуку буде помітний користувачами. Можна звести пошук до бінарного, якщо відсортувати список файлів. Проте це ускладнить створення і видалення файлів, оскільки потрібне переміщення великого об'єму інформації.

Хеш-кодування-таблиця

Хешування (див. наприклад [Ахо, 2001]) - інший спосіб, який може використовуватися для розміщення і подальшого пошуку імені файлу в директорії. У даному методі імена файлів також зберігаються в каталозі у вигляді лінійного списку, але додатково використовується хеш-кодування-таблиця. Хеш-кодування-таблиця, точніше побудована на її основі хеш-кодування-функція, дозволяє по імені файлу отримати покажчик на ймення файл в списку. Таким чином, можна істотно зменшити час пошуку.

В результаті хешування можуть виникати колізії, тобто ситуації, коли функція хешування, застосована до різних імен файлів, дає один і той же результат. Зазвичай імена таких файлів об'єднують в зв'язкові списки, припускаючи надалі здійснення в них послідовного пошуку потрібного імені файлу. Вибір відповідного алгоритму хешування дозволяє звести до мінімуму число колізій. Проте завжди є вірогідність несприятливого результату, коли непропорційно великому числу імен файлів функція хешування ставить у відповідність один і той же результат. У такому разі перевага використання цієї схеми в порівнянні з послідовним пошуком практично втрачається.