 |
|
Приклади застосування хеш-таблиць
Лабораторна робота № 5
"Розробка та дослідження ефективності методів пошуку даних"
МЕТА РОБОТИ
Дослідити ефективність методів пошуку на прикладі різних методів організації хеш-таблиць. Вивчити основні методи побудови хеш-таблиць, дослідити переваги і недоліки, властиві різним методам, оцінити ефективність і провести порівняння ефективностей.
ТЕОРЕТИЧНІ ВІДОМОСТІ
Приклади застосування хеш-таблиць
Одним з поширенних прикладів застосування хеш-таблиць є побудова і пошук в таблиці ідентифікаторів програми. Головною характеристикою будь-якого елемента вхідної програми є його ім'я. Саме з іменами змінних, констант, функцій і інших елементів вхідної мови оперує розробник програми - тому і компілятор повинен вміти аналізувати ці елементи по їхніх іменах.
Таким чином, завдання компілятора полягає в тому, щоб зберігати деяку інформацію, пов'язану з кожним елементом вхідної програми, і мати доступ до цієї інформації за ім'ям елемента. Для рішення цього завдання компілятор організує спеціальні сховища даних, що називаються таблицями ідентифікаторів або таблицями символів. Таблиця ідентифікаторів складається з набору полів даних (записів), кожне з яких відповідає одному елементу вхідної програми. Запис містить всю необхідну компілятору інформацію про даний елемент і ця інформація може доповнюватись під час роботи компілятора. Кількість записів залежить від способу організації таблиці ідентифікаторів, але їх не може бути менше, ніж елементів у програмі. В принципі, компілятор може працювати не з однією, а з декількома таблицями ідентифікаторів - їх кількість і структура залежать від реалізації компілятора.
Компілятор поповнює записи в таблиці ідентифікаторів під час аналізу вхідної програми і знаходження в ній нових елементів, що вимагають розміщення в таблиці. Пошук інформації в таблиці виконується щоразу, коли компілятору потрібні відомості про той або інший елемент програми. Причому варто помітити, що пошук елемента в таблиці буде виконуватися компілятором значно частіше, ніж розміщення в ній нових елементів. Так відбувається тому, що опис нових елементів у вхідній програмі, як правило, зустрічаються набагато рідше, ніж ці елементи використовуються. Крім того, кожному додаванню елемента в таблицю ідентифікаторів завжди буде передувати операція пошуку - щоб переконатися, що такого елемента в таблиці немає.
На кожну операцію пошуку елемента в таблиці компілятор буде затрачати час, і оскільки кількість елементів у вхідній програмі може бути достатньо велика (від одиниць до сотень тисяч залежно від обсягу програми), цей час буде істотно впливати на загальний час компіляції. Тому таблиці ідентифікаторів повинні бути організовані таким чином, щоб компілятор мав можливість максимально швидко виконувати пошук потрібного йому запису в таблиці по імені елемента, з яким зв'язаний цей запис.
Можна виділити наступні способи організації таблиці ідентифікаторів:
□ прості і впорядковані списки;
□ бінарне дерево;
□ хеш-таблиця з рехешуванням;
□ хеш-таблиця з використанням методу ланцюжків;
□ комбінація хеш-таблиці зі списком або з бінарним деревом.
З невеликими модифікаціями метод хешування придатний для зберігання дуже великих словників на диску. Ця версія хешування називається розширюваним хешуванням (extensible hashing). Оскільки звертання до диска значно дорожче досліджень в оперативній пам'яті, краще здійснювати виконання більшої кількості досліджень, ніж звертань до диска. Відповідно, значення, що обчислюються за допомогою хеш-функції в розширюваному хешуванні, вказують адресу на диску, де перебуває блок (bucket), в якому може зберігатися до b ключів. Після того як визначений блок для шуканого ключа, всі ключі блоку зчитуються в оперативну пам'ять і серед них виконується пошук шуканого ключа.