Page 28 - 4761

Рисунок 2.6 - Заповнення таблиці ідентифікаторів при використанні
найпростішого рехешування

У результаті розміщення елементів в таблиці для пошуку ідентифікатора А 1
потрібно зробити 1 порівняння, для А 2 – 2 порівняння, для А 3 – 2 порівняння, для А 4 – 1
порівняння, для А 5 – 5 порівнянь.

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

26