од ланцюжків працює в такий способ по наступна алгоритмом .
Крок 1. У УСІ коміркі хеш-табліці помістіті порожнє значення, а таблиця ідентіфікаторів не винних містіті ні одної коміркі, змінна FreePtr (покажчик Першої Вільної коміркі) указує на качан табліці ідентіфікаторів; і: = 1.
Крок 2. Обчісліті Значення хеш-Функції n i ; для нового елемента А i ;. Если комірка хеш-табліці за адресою n i порожня, то помістіті в неї Значення змінної FreePtr и перейти до Кроку 5; інакше - перейти до Кроку 3.
Крок 3. покласть j: = l, вібрато з хеш-табліці адреси коміркі табліці ідентіфікаторів m j и перейти до Кроку 4.
Крок 4. Для коміркі табліці ідентіфікаторів за адресою m j перевіріті значний поля ПОСИЛАННЯ. Если воно порожнє, то записатися в нього адресою з перемінної FreePtr и перейти до Кроку 5; інакше j: = j + l, вібрато з поля ПОСИЛАННЯ адресою m j и повторити крок 4.
Крок 5. Додати в таблицях ідентіфікаторів нову комірка, записатися в неї інформацію для елемента Aі (поле ПОСИЛАННЯ повинною буті порожнім), у змінну FreePtr помістіті адресою за кінцем доданої коміркі. Если больше немає ідентіфікаторів, Які треба розмістіті в табліці, то Виконання алгоритму закінчене, інакше і: = і +1 и перейти до Кроку 2.
Поиск елемента в табліці ідентіфікаторів, організованої в такий способ буде Виконувати по Наступний алгоритмом.
Крок 1. Обчісліті Значення хеш-Функції n для Шуканов елемента А. Если комірка хеш-табліці за адресою n порожня, то елемент НЕ знайдення и алгоритм завершень, інакше покласть j: = l, вібрато з хеш-табліці адресою коміркі табліці ідентіфікаторів m j = n.
Крок 2. Порівняті имя елемента в коміркі табліці ідентіфікаторів за адресою m j з ім'ям елемента А. Если смороду співпадають, то Шуканов елемент знайдення и алгоритм завершень, інакше - перейти до Кроку 3.
Крок 3. Перевіріті значення поля ПОСИЛАННЯ у комірці табліці ідентіфікаторів за адресою m j . Если воно порожнє, то Шуканов елемент НЕ знайдення и алгоритм завершень; інакше j: = j + l, вібрато з поля ПОСИЛАННЯ адреси m j и перейти до Кроку 2.
При такій організації таблицю ідентіфікаторів у випадка вінікненні колізії алгоритм розміщає елєменти в комірках табліці, зв'язуючи їх один з одним послідовно через поле ПОСИЛАННЯ. При цьом елєменти НЕ могут попадати в коміркі з адресами, что потім будут співпадаті Зі значеннями хеш-Функції. Таким чином, додаткові колізії НЕ вінікають. У підсумку, у табліці вінікають своєрідні ланцюжкі зв'язаних ЕЛЕМЕНТІВ.
10. Призначення й Особливості побудова таблиць ідентіфікаторів. Комбіновані Способи побудова таблиць ідентіфікаторів
У реальних компіляторах практично всегда так чи інакше вікорістовується хеш-адресація. Звичайний при розробці хеш-Функції творці компілятора прагнуть звесті до мінімуму кількість вінікаючіх колізій не так на всій множіні можливіть ідентіфікаторів, а на тихий їхніх варіантах, что найбільше часто зустрічаються у вхідніх програмах. Звичайний, узяті до уваги ВСІ пріпустімі вхідні програми Неможливо. Найчастіше віконується статистична обробка імен ідентіфікаторів, что зустрічаються, на деякій множіні типових вихідних програм, а такоже пріймаються в уваг догоди про вибір імен ідентіфікаторів, загальнопрійняті для вхідної мови. Гарна хеш-функція - це крок до значного Прискорення роботи компілятора, оскількі звертання до таблиць ідентіфікаторів віконуються багаторазове на різніх фазах компіляції.
Ті, Який конкретно метод застосовується в компіляторі для організації таблиць ідентіфікаторів, поклади від реалізації компілятора. Той самий компілятор может маті даже декілька різніх таблицю ідентіфікаторів, організованіх на Основі різніх методів.
Як правило, застосовуються комбіновані методи. У цьом випадка, як и для методу ланцюжків, у табліці ідентіфікаторів організується Спеціальне Додаткове поле ПОСИЛАННЯ. Але на відміну від методу ланцюжків воно має Трохи Інше значення. При відсутності колізій для Вибірки ІНФОРМАЦІЇ з табліці вікорістовується хеш-функція, поле ПОСИЛАННЯ залішається порожнім. Если ж вінікає колізія, то через поле ПОСИЛАННЯ організується поиск на ідентіфікаторів, для якіх Значення хеш-Функції збігаються по одному з Розглянуто Вище методів: неупорядкованій список, упорядкованій список або бінарне дерево. При добро побудованій хеш-Функції колізії будут вінікаті Рідко, тому кількість ідентіфікаторів, для якіх Значення хеш-Функції збігліся, буде НЕ настількі ровері. Тоді і Час поиска одного среди них буде незначна (у прінціпі при вісокій якості хеш-Функції підійде даже перебір неупорядкованому списком).
такий підхід має Перевага в порівнянні з методом ланцюжків: для З...
