Page 27 - 4761

Для розв’язку проблеми колізії можна використати метод рехешування
(розстановки). Згідно цього методу, якщо для елемента А адрес h(A),обчислений за
допомогою хеш-функції h вказує на вже зайняту комірку, то необхідно обчислити
значення функції n 1 = h 1(A), і перевірити зайнятість комірки за адресою n 1 . Якщо і вона
зайнята, то обчислюється значення h 2(A), і так до тих пір, поки або не буде знайдена
вільна комірка, або чергове значення h 1(A) співпаде з h(A). В останньому випадку
рахується , що ТІ заповнена і місця в ній більше немає – видається повідомлення про
помилку розміщення ідентифікаторів у таблиці.
Алгоритм заповнення такої таблиці наступний.
К1: Обчислити значення хеш-функції n = h(A) для нового елемента А.
К2: Якщо комірка за адресою n пуста, то помістити в неї елемент А і закінчити
алгоритм, інакше і := 1 і К3.
К3: Обчислити n і = h і(A). Якщо комірка за адресою n і пуста, то помістити в неї А і
END, інакше К4.
К4: Якщо n= n i, то ERROR I END, інакше – і := і+1 і К3.
Алгоритм пошуку елемента.
К1: Обчислити значення хеш-функції n = h(A) для шуканого елемента А.
К2: Якщо комірка за адресою n пуста, то елемент не знайдено, алгоритм закінчено,
інакше порівняти ім’я елемента в комірці n з ім’ям шуканого елемента А. Якщо вони
співпадають, то елемент знайдено і алгоритм завершено, інакше - і := 1 і К3.
К3: Обчислити n і = h і(A). Якщо комірка за адресою n і пуста, то або n=n i , то елемент
не знайдено і END, інакше порівняти ім’я елемента в комірці n і з ім’ям шуканого
елемента А. Якщо вони співпадають, то елемент знайдено і алгоритм завершено, інакше - і
:= 1 і К3.
При такій організації ТІ у випадку виникнення колізії алгоритм розміщує елементи
в пустих комірках таблиці, вибираючи їх деяким чином. При цьому елементи можуть
попадати в комірки з адресами, які потім будуть співпадати зі значеннями хеш-функцій,
що приведе до виникнення нових колізій. Таким чином , кількість операцій, необхідних
для пошуку і розміщення в таблиці елемента, залежить від заповненості таблиці.
Для організації заповнення ТІ за методом рехешування необхідно визначити всі
хеш-функції h i для всіх і. частіше за все функції h i визначають як деякі модифікації хеш-
функції h. Наприклад, самим простим методом обчислення функції h і(A) є її оформлення у
вигляді h і(A) = (h(A)+р і)mod N m , де р і – деяке ціле число, яке обчислюється, а N m –
максимальне значення з області хеш-функції h.
В свою чергу самим простим підходом буде прирівняти р і = і, тоді
h і(A) = (h(A)+і)mod N m.
В цьому випадку, якщо значення хеш-функції співпадають для якихось елементів,
пошук вільної комірки в таблиці починається послідовно від поточної позиції, заданої
хеш-функцією h(A).
Недолік: якщо співпадають хеш-адреси елементів, то елементи в таблиці
групуються навколо них, що збільшують число порівнянь при пошуку та розміщенні.
Середній час пошуку :
Т П = О((1-Lf/2)/(1-Lf)) ,
Lf – ступінь заповненості ТІ – відношення числа зайнятих комірок N таблиці до
технічно допустимого числа елементів у ній : Lf = N/N m.
Приклад 2.4. Є ряд послідовних комірок таблиці: n 1, n 2, n 3, n 4, n 5 і ряд
ідентифікаторів, які треба розмістити в ній: А 1, А 2, А 3, А 4, А 5 при умові, що h(А 1) = h(А 2) =
h(А 3) = h(А 4) = n 4. Послідовність розміщення ідентифікаторів в таблиці при використанні
найпростішого методу рехешування показана на рисунку 2.6.

25