ення множини вхідніх ЕЛЕМЕНТІВ R на множини ціліх невід'ємніх чисел Z: F (r) = n, r ГЋ R, n ГЋ Z.
Існують Різні Варіанти хеш-функцій. Одержании результату хеш-Функції - В«хешуванняВ» - звичайна досягається за рахунок Виконання над ланцюжком сімволів Деяк простих Арифметичний и логічніх операцій. p> Ситуація, коли двома чи більш ідентіфікаторам відповідає ті самє Значення Функції назівається колізією.
Природно, что хеш-функція, что допускає колізії, що не может буті прямо Використана для хеш-адресації в табліці ідентіфікаторів. p> Очевидно, что для полного віключення колізій хеш-функція винна буті взаємно однозначна: шкірному елементами з области визначення хеш-Функції повинною відповідаті Одне Значення з ее множини значень, альо и шкірному значень з множини значень цієї Функції повинною відповідаті Тільки один елемент з области ее визначення. Тоді будь-яким двома довільнім елементами з области визначення хеш-Функції будут всегда відповідаті два Різні ее значення. p> Для решение проблеми колізії можна використовуват багатая способів. Одним З них є метод В«РехешуванняВ» (або В«размещенияВ»). Відповідно до цього методу, ЯКЩО для елемента А адреси h (А), обчислено за помощью хеш-Функції вказує на вже зайнятості комірку, то звітність, обчісліті Значення Функції n1 = h1 (А) i перевіріті зайнятість коміркі за адресою n1 . Если и вона зайнятості, то обчіслюється Значення h 2 (A), и так Доті, поки або не якщо знайдення вільна комірка, або Чергова Значення h i (А) співпаде з h (А). У последнего випадка вважається, что таблиця ідентіфікаторів Заповнена и місця в ній больше.
Таку таблицю ідентіфікаторів можна організуваті по Наступний алгоритмом размещения елемента.
Крок 1. Обчісліті Значення хеш-Функції n = h (A) для нового елемента А..
Крок 2. Если комірка за адресою n порожня, то помістіті в неї елемент А і Завершити алгоритм, інакше i: = l и перейти до Кроку 3.
Крок 3. Обчісліті n i = h i (А). Если комірка за адресою n i порожня, то помістіті в неї, елемент А і Завершити алгоритм, інакше перейти до Кроку 4.
Крок 4. Если n = n i , то повідоміті про помилки и Завершити алгоритм, інакше і: = і +1 и вернуться до Кроку 3.
Тоді поиск на елемента А в табліці ідентіфікаторів, організованої таким чином, буде Виконувати по наступна алгоритмом .
Крок 1. Обчісліті Значення хеш-Функції n = h (A) для нового елемента А.
Крок 2. Если комірка за адресою n порожня, то елемент НЕ знайдення, алгоритм завершень, інакше порівняті имя елемента в комірці n з ім'ям Шуканов елемента А. Если смороду збігаються, те елемент знайдення и алгоритм завершень, інакше і: = 1 і перейти до Кроку 3.
Крок 3. Обчісліті n i = h i (А). Если комірка за адресою n i порожня чі n = n i , те елемент НЕ знайдення и алгоритм завершень, інакше порівняті имя елемента в комірці n i з ім'ям Шуканов елемента А. Если смороду збігаються, те елемент знайдення и алгоритм завершень, інакше і: = і +1 и повторити крок 3.
9. Призначення й Особливості побудова таблиць ідентіфікаторів
Неповне Заповнення табліці ідентіфікаторів при застосуванні хеш-функцій веде до неефективно Використання Всього ОБСЯГИ пам'яті, доступного компілятору. Причому ОБСЯГИ невікорістовуваної пам'яті буде тим Вище, чім больше ІНФОРМАЦІЇ зберігається для шкірного ідентіфікатора. Цього недоліку можна унікнуті, ЯКЩО доповніті Таблицю ідентіфікаторів Деяк проміжною хеш-таблиці.
такий підхід дозволяє отріматі два позитивних результатів: по-перше немає необхідності заповнюваті порожнімі значень таблиць ідентіфікаторів - це можна сделать Тільки для хеш-табліці; по-друге, шкірному ідентіфікатору буде відповідаті Тільки одна комірка у табліці ідентіфікаторів (у ній не якщо порожніх невікорістовуваніх комірок). Порожні коміркі в такому випадка будут Тільки в хеш-табліці, и ОБСЯГИ невікорістовуваної пам'яті не якщо залежаться від ОБСЯГИ ІНФОРМАЦІЇ, збереженої для шкірного ідентіфікатора - для шкірного Значення хеш-Функції буде втрачають Тільки пам'ять, Необхідна для Збереження одного покажчика на основній таблиці ідентіфікаторів.
На Основі цієї схему можна реалізуваті ще один способ організації табліці ідентіфікаторів за помощью хеш-функцій, називаний В«метод ланцюжківВ». Для методу ланцюжків у Таблицю ідентіфікаторів для шкірного елемента додається ще Одне поле, у якому может містітіся посилання на агентство будь-який елемент табліці. Спочатку це поле всегда порожнє (нікуді НЕ вказує). Такоже для цього методу звітність, мати одну спеціальну змінну, котра всегда вказує на Першу вільну комірку ОСНОВНОЇ табліці ідентіфікаторів (спочатку - указує на качан табліці).
Мет...
