- •Глава 5
- •5. Операції логічного рівня
- •5.1. Пошук
- •5.1.1. Послідовний або лінійний пошук
- •5.1.2. Лінійний пошук з бар'єром
- •5.1.3. Бінарний пошук
- •5.1.4. Пошук у таблиці
- •5.1.5. Прямий пошук рядка в тексті
- •5.2. Прямий доступ і хешування
- •5.2.1 Таблиці прямого доступу
- •5.2.2. Таблиці з довідниками
- •5.2.3. Хешовані таблиці та функції хешування
- •5.2.4. Проблема колізій у хешованих таблицях
- •5.3. Сортування
- •5.3.1. Сортування вибіркою
- •5.3.2. Сортування включенням
- •5.4. Сортування розподілом
- •5.5. Сортування злиттям
- •5.5. Порівняння алгоритмів сортування масивів
5.2. Прямий доступ і хешування
У розглянутих вище методах пошуку число проб при пошуку було пропорційно N. Природно, виникає бажання знайти такий метод пошуку, при якому число проб не залежало б від розміру таблиці, а в ідеальному випадку пошук зводився б до однієї проби.
5.2.1 Таблиці прямого доступу
Найпростішою організацією таблиці, що забезпечує ідеально швидкий пошук, є таблиця прямого доступу. У такій таблиці ключ є адресою запису в таблиці або може бути перетворений на адресу, причому таким чином, що ніякі два різних ключі не перетворяться в ту саму адресу. При створенні таблиці виділяється пам'ять для збереження всієї таблиці та заповнюється порожніми записами. Потім записи вносяться в таблицю – кожна на своє місце, що визначається ключем даного запису. При пошуку ключ використовується як адреса і за цією адресою вибирається запис. Якщо обраний запис порожній, то запису з таким ключем взагалі немає в таблиці. Таблиці прямого доступу дуже ефективні у використанні, але, на жаль, область їхнього застосування дуже обмежена.
Назвемо простором ключів множину усіх теоретично можливих значень ключів запису. Назвемо простором записів безліч тих слотів у пам'яті, що виділяються для збереження таблиці. Таблиці прямого доступу можуть бути застосовані тільки для таких задач, у яких розмір простору записів може дорівнювати розміру простору ключів. У більшості реальних задач, однак, розмір простору записів набагато менше, ніж простір ключів. Наприклад, якщо ключ використовується як прізвище, то, навіть обмеживши довжину ключа 10-ма символами, виходить 3310 можливих значень ключів. В обчислювальній системі не може бути виділений простір записів такого розміру. Навіть якщо ресурси обчислювальної системи і дозволять це, то значна частина цього простору буде заповнена порожніми записами, тому що в кожному конкретному заповненні таблиці фактична множина ключів не буде цілком покривати простір ключів.
5.2.2. Таблиці з довідниками
Одним із способів усунення недоліку, властивого таблицям прямого доступу, який полягає в тому, що вони вимагають пам'ять значних розмірів, є метод довідників.
Основна таблиця містить записи в довільному порядку. На додаток до основного будується довідкова чи індексна таблиця, записи якої складаються усього з двох полів: ключа й адреси в основній таблиці. Пошук за ключем виконується в довідковій таблиці. Якщо довідкова таблиця є таблицею прямого доступу, то втрати пам'яті на порожні записи зменшуються. Однак, мабуть, що у випадку ключа-прізвища довідкова таблиця не врятує. Тому, звичайно довідкові таблиці містять тільки фактичні ключі і до них застосовуються будь які методи сортування і пошуку. При сортуванні довідкових таблиць, звичайно, досягається деяка економія на пересиланнях, але в цілому застосування довідників було б недоцільно, якби не дві їхні важливі властивості:
– по-перше, якщо основна таблиця розташована на зовнішній пам'яті, то довідкова таблиця (чи значна її частина) може бути розміщена в оперативній пам'яті і пошук ключа, таким чином, буде виконуватися в оперативній пам'яті, що набагато швидше;
– по-друге, для однієї основної таблиці можуть бути побудовані декілька довідників, що забезпечують використання в якості ключа різні поля записів основної таблиці.
Слід зазначити, що для таблиць прямого доступу і для таблиць з довідниками немає необхідності зберігати ключ у складі запису основної таблиці, тому що ключ може бути відновлений за адресою запису або за вмістом довідника.