Головна

Приклади реалізації схем хешування

  1. II-2.4. Прикладні завдання. Приклади керованих процесів
  2. Аналіз відвантаження і реалізації продукції.
  3. Бухгалтерський облік реалізації нематеріального активу. Особливості обліку нематеріальних активів для цілей оподаткування.
  4. У реалізації ваших нових ідей і вашої нової реальності, абсолютно нової
  5. Взаємодія неалельних генів. Приклади розв'язання типових задач
  6. Питання 4. Облік реалізації товарів
  7. Генетичні основи селекції. Приклади розв'язання типових задач

Приклад реалізації методу прямої адресації з лінійним опробування. Вихідними даними є 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. Обробка списків


бінарні дерева | Вставка нового елемента | видалення вузла | Алгоритми обходу дерева | функція перегляду | Алгоритм, що використовує дерево | Алгоритм, що використовує стек | приклад реалізації | поняття хеширования | Приклади хеш-функцій |

© 2016-2022  um.co.ua - учбові матеріали та реферати