Головна |
Приклад реалізації методу прямої адресації з лінійним опробування. Вихідними даними є 7 записів (для простоти інформаційна частина складається з цілих чисел) оголошеного структурного типу:
struct zap {
int key; // Ключ
int info; // Інформація
} Data;
{59,1}, {70,3}, {96,5}, {81,7}, {13,8}, {41,2}, {79,9}; розмір хеш-таблиці m = 10. Виберемо хеш-функцію i = h(data) = data.key% 10; тобто залишок від ділення на 10 - iI [0,9].
На підставі вихідних даних послідовно заповнюємо хеш-таблицю.
Хешування перших п'яти ключів дає різні індекси (хеш-адреси):
i = 59% 10 = 9; i = 70% 10 = 0;
i = 96% 10 = 6; i = 81% 10 = 1;
i = 13% 10 = 3.
Перша колізія виникає між ключами 81 і 41 - місце з індексом 1 зайнято. Тому переглядаємо хеш-таблицю з метою пошуку найближчого вільного місця, в даному випадку - це i = 2.
Наступний ключ 79 також породжує колізію: позиція 9 вже зайнята. Ефективність алгоритму різко падає, тому що для пошуку вільного місця знадобилося 6 проб (порівнянь), вільним виявився індекс i = 4. Загальна кількість проб - 1-9 проб на елемент.
Реалізація методу ланцюжків для попереднього прикладу. Оголошуємо структурний тип для елемента односпрямованого списку:
struct zap {
int key; // Ключ
int info; // Інформація
zap * Next; // Покажчик на наступний елемент у списку
} Data;
На підставі вихідних даних послідовно заповнюємо хеш-таблицю, додаючи новий елемент в кінець списку, якщо місце вже зайнято.
Хешування перших п'яти ключів, як і в попередньому випадку, дає різні індекси (хеш-адреси): 9, 0, 6, 1, і 3.
При виникненні колізії новий елемент додається в кінець списку. Тому елемент з ключем 41 поміщається після елемента з ключем 81, а елемент з ключем 79 - після елемента з ключем 59.
схеми хеширования | ЗАВДАННЯ 8. Обробка списків
бінарні дерева | Вставка нового елемента | видалення вузла | Алгоритми обходу дерева | функція перегляду | Алгоритм, що використовує дерево | Алгоритм, що використовує стек | приклад реалізації | поняття хеширования | Приклади хеш-функцій |