Page 26 - 4761

обчислена для цього елемента. Тоді в ідеальному випадку для розміщення будь-якого
елемента в ТІ достатньо тільки обчислити його хеш-функцію і звернутися до потрібної
комірки масиву даних. Для пошуку елемента в таблиці необхідно обчислити хеш-функцію
для шуканого елемента і перевірити, чи не є задана нею комірка пустою (якщо не пуста –
елемент знайдено, якщо пуста - ні).
Ідентифікаторам А 1, А 2, А 3 відповідають три значення хеш-функцій n 1 , n 2 , n 3 . В
комірки, які адресують n 1 , n 2 , n 3 поміщається інформація про А 1, А 2, А 3 . При пошуку
ідентифікатора А 2 , обчислюється значення адреси n 2 і вибираються дані з відповідної
комірки таблиці.
Цей метод ефективний, бо час розміщення та пошук елемента в таблиці
визначається часом на обчислення хеш-функції.
Недолік : неефективне використання об’єму пам’яті під ТІ: розмір масиву для її
зберігання повинен відповідати області значень хеш-функції, а реальних даних в ТІ може
бути менше.

Побудова ТІ на основі хеш-функцій
Є різні варіанти хеш-функцій «хешування» - як правило, можна досягти за рахунок
виконання над ланцюгом символів деяких простих арифметичних і логарифмічних
операцій.
Найпростіша хеш-функція для символу – це код внутрішнього представлення в
компіляторі літери символа. Її можна використовувати і для ланцюга символу, вибираючи
перший символ.
Наприклад, двійкове представлення символу А – це двійковий код 001000012, то
результат хешування ідентифікатора А Table – код 00100012.
Але ця хеш-функція не є задовільною: при її виконанні двом різним
ідентифікаторам, які починаються з однієї і тієї ж букви, буде відповідати одне значення
хеш-функції. Тоді при хеш-адресації в одну комірку ТІ по одній і тій же адресі мають бути
поміщені два різні ідентифікатори, що неможливо. Ситуація, коли двом або більше
ідентифікаторам відповідає одне і те ж значення функції, називається колізією.
Природно, що хеш-функція, яка допускає колізію, не може напряму бути
використана для хеш-адресації ТІ.
Отже, для повного виключення колізії хеш-функція має бути взаємно однозначною:
кожному елементу з області визначення хеш-функції має відповідати одне значення з її
множини значень, і кожному значенню з множини значень цієї функції має відповідати
тільки один елемент з її області визначення.
Теоретично для ідентифікаторів таку хеш-функцію побудувати можна, так як
область визначення хеш-функції (всі можливі імена ідентифікаторів) і область її значень
(цілі невід’ємні числа) є ∞ множинами, але практично дуже важко. Наприклад,
відображення для рядка символів – двійкове число, отримане шляхом конкатенації кодів
символів, що утворюють рядок.
Існує обмеження, яке робить створення взаємно однозначної хеш-функції для
ідентифікаторів неможливим. Область значень будь-якої хеш-функції обмежена розміром
доступного адресного простору в даній архітектурі компілятора. (Може організувати
адресацію з використанням зовнішніх накопичувачів для організації віртуальної пам’яті,
але накладені затрати для такої адресації будуть дуже великі). Множина адрес будь-якого
компілятора з традиційною архітектурою може бути великою, проте обмеженою. Можна
врахувати, що довжина частини імені ідентифікатора, яка береться до уваги, теж
обмежена (від 32 до 128 символів). Але й тоді кількість елементів у кінцевій множині, яка
складає область визначення функції, будуть перевищувати їх кількість в кінцевій множині
області значень функції (кількість всіх можливих ідентифікаторів все рівно більша
кількості допустимих адрес в сучасних компіляторах).

24