Page 30 - 4761

Рисунок 2.7 – Заповнення таблиці ідентифікаторів методом ланцюжків

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

28