Таблиці прямого доступу

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

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