Page 25 - 4761

організації таблиці ідентифікаторів. Другий недолік – необхідність роботи з динамічним
виділенням пам’яті при побудові дерева.
Середній час на заповнення – Т З = N*O(log 2(N)), на пошук Т П = O(log 2(N)).
В цілому, метод бінарного дерева є досить успішним механізмом для організації ТІ.
Він знайшов своє використання в ряді компіляторів. Деколи компілятори будують
декілька різних дерев для ідентифікаторів різних типів і різної довжини.

Хеш-функції та хеш-адресація

Логарифмічна залежність часу пошуку і часу заповнення ТІ – це самий хороший
результат, якого можна досягти за рахунок застосування різних методів побудови таблиць.
Кращих результатів можна досягти, якщо застосовувати методи, пов’язані з
використанням хеш-функцій та хеш-адресації.
Хеш-функцією F називають деяке відображення множини вхідних елементів R на
множину цілих невід’ємних чисел Z : F(r) = n, r  R, n  Z. (термін – від англійського
(hash function) – (hash – змішувати) мішати).
Множина допустимих вхідних елементів R називається областю визначення хеш-
функції. Множиною значень хеш-функції F називається підмножина М з множини цілих
невід’ємних чисел Z : M  Z, містить всі можливі значення, які повертає функція F :
 r  R: F(r)  M   m  M:  r  R : F(r) = m
Процес відображення області визначення хеш-функції на множину значень
називається «хешуванням».
При роботі з ТІ хеш-функція має виконувати відображення імен ідентифікаторів на
множину цілих чисел. Областю визначення хеш-функції буде множина всіх можливих
імен ідентифікаторів.
Хеш-адресація заключається у використанні значення, яке хеш-функція повертає,
як адресу комірки з деякого масиву даних. Тоді розмір масиву даних має відповідати
області значень хеш-функції, яка використовується. В реальному компіляторі область
значень хеш-функції не повинна перевищувати розмір допустимого адресного простору
компілятора.

Рисунок 2.5 – Організація ТІ з використанням хеш-адресації

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

23