Page 29 - 4761

На основі цієї схеми можна реалізувати ще один спосіб організації тблиць
ідентифікаторів за допомогою хеш-функцій, він називається «метод ланцюжків». Для
методу ланцюжків в таблицю ідентифікаторів для кожного елементу добавляється ще
одне поле, в якому може міститися посиланняа на любий елемент таблиці. Спершу це
поле завжди порожнє (нікуди не указує). Також для цього методу необхідно мати одну
спеціальну змінну, яка завжди указує на першу вільну комірку основної таблиці
ідентифікаторів (спочатку – указує на початок таблиці).
Метод ланцюжків працює за наступним алгоритмом:
Крок 1. У всі комірки хеш-таблиці помістити порожні значення, таблиця
ідентифікаторів порожня, змінна FreePtr (показник першої вільної комірки) указує на
початок таблиці ідентифікаторів; і:=1.
Крок 2. Вирахувати значення хеш-функції n i для нового елементу А i. Якщо комірка
хеш-таблиці по адресу n i порожня, то помістити в неї значення змінної FreePtr і перейти
до кроку 5; якщо ні перейти до кроку 3.
Крок 3. Покласти j:=1, вибрати з хеш-таблиці адресу комірки ідентифікатора m j і
перейти до кроку 4.
Крок 4. Для комірки таблиці ідентифікаторів по адресу m j перевірити значення
поля ссилки. Якщо воно порожнє то записати в нього адрес з змінної FreePtr і перейти до
кроку 5; якщо ні то j:=j+1, вибрати з поля посилання адресу m j і повторити крок 4.
Крок 5. Добавити в таблицю ідентифікаторів нову комірку, записати в неї
інформацію для елемента А i (поле посилання повинно бути порожнім), в змінну FreePtr
помістити адресу за кінцем добавленої комірки. Якщо більше немає ідентифікаторів, які
треба розмістити в таблиці, то виконання алгоритму закінчено, якщо ні то і:=і+1 і перейти
до кроку 2.
Пошук елементу в таблиці ідентифікаторів, організованій таким чином, буде
виконуватись по наступному алгоритму:
Крок 1. Вирахувати значення хеш-функції n для шуканого елементу А. Якщо
комірка хеш-таблиці по адресу n порожня, то елемент не знайдений і алгоритм закінчений,
якщо ні то j:=1, вибрати з хеш-таблиці адресу комірки таблиці ідентифікаторів m j .
Крок 2. Порівняти ім’я елементу в комірці таблиці ідентифікаторів по адресу m j з
ім’ям шуканого елементу А. Якщо вони співпадуть, то шуканий елемент знайдений і
алгоритм закінчений, якщо ні то перейти до кроку 3.
Крок 3. Перевірити значення поля посилання в комірці таблиці ідентифікаторів по
адресу m j . Якщо воно порожнє, то шуканий елемент не знайдений і алгоритм закінчений,
якщо ні то j:=j+1, вибрати з поля посилання адресу m j і перейти до кроку 2.
При такій організації таблиць ідентифікаторів в випадку виникнення колізії
алгоритм розміщує елементи в комірках таблиці, зв’язуючи їх один з одним послідовно
через поле посилання. При цьому елементи не можуть попадати в комірки з адресами, які
потім будуть співпадати з значеннями хеш-функції. Таким чином , додаткові колізії не
виникають. В результаті в таблиці виникають своєобразні ланцюжки зв’язаних елементів,
звідки виникла назва даного методу – «метод ланцюжків».
На рисунку 2.7 показано заповнення хеш-таблиці і таблиці ідентифікаторів для
прикладу 2.4. Після розміщення елементів в таблиці для пошуку ідентифікатора А1
потрібно 1 порівняння, для А2 – 2 порівняння, для А3 – 1 порівняння, для А4 – 1
порівняння і для А5 – порівняння.

27