Алгоритми і структури даних

Короткі теоретичні відомості

Питання для повторення

1. Реалізація лінійних списків.

Постановка задачі

žУ хеш-таблиці замість безпосереднього використання ключа як індексу масиву, індекс обчислюється за значенням ключа. Функція, що відображає елемент множини ключів {0, 1, ..., n-1} на множину індексів {0, 1, ..., m-1} (m <n), називається хеш-функцією. Якщо два ключі хешуються в одну й ту саму комірку, то говорять про виникнення колізії. За способом вирішення колізій розрізняють:

• відкрите хешування — усі елементи, що хешуються в одну комірку, об’єднуються у зв’язний список
• закрите хешування — усі елементи зберігаються безпосередньо у хеш-таблиці, при потраплянні у зайняту комірку обирається послідовність інших хеш-значень.

Необхідно забезпечити для хеш-таблиці реалізацію основних операторів:

• пошук елемента;
• запис елемента;
• читання елемента.

Опис алгоритмів

Опис структур даних

При закритому хешуванні хеш-таблиця є масивом, елементи якого занумеровані від 0 до m-1.

При відкритому хешуванні хеш-таблиця є масивом, кожна комірка якого містить покажчики на заголовок списку всіх елементів, хеш-значення ключа яких дорівнює індексу комірки.

1. Побудова хеш-функції методом ділення

Ідея

Значенням хеш-функції є остача від ділення ключа на розмір хеш-таблиці.

Псевдокод

2.Пошук елемента при відкритому хешуванні

Ідея

Знайти відповідне хеш-значення і здійснити пошук у списку, заголовок на який міститься у відповідній комірці хеш-таблиці.

Псевдокод

3.Запис елемента при відкритому хешуванні

Ідея

Якщо елемент не знайдено, то додати його на початку списку, що відповідає хеш-значенню.

Псевдокод

4.Вилучення елемента при відкритому хешуванні

Ідея

Вилучити елемент зі списку, заголовок на який міститься у відповідній комірці хеш-таблиці.

Псевдокод

5. Вставка елемента при закритому хешуванні

Ідея

При лінійному хешуванні використовується хеш-функція h(x, i)=(h1(x)+i) mod m, де h1(x) — звичайна хеш-функція, i — номер спроби розмістити елемент. Якщо комірка, відповідна хеш-значенню зайнята, то обчислюється значення для наступної спроби.

Псевдокод

Завдання для виконання

Постановка задачі

Скласти програми, що забезпечують виконання операцій з хеш-таблицями. Програми повинні забезпечувати

• реалізацію основних процедур із хеш-таблицею;
• заповнення хеш-таблиці послідовністю випадково згенерованих чисел;
• виведення на екран графа хеш-таблиці;
• виконання вказаних викладачем дій з хеш-таблицею.

Технічні умови

• розмір хеш-таблиці дорівнює 13;
• множина ключів містить 50 елементів.

Хід роботи

1. Скласти програму Hash.cpp для реалізації операцій з хеш-таблцею при відкритому хешуванні; хеш-фунція будується методом ділення.
2. Забезпечити виконання дій, зазначених викладачем.
3. Виконати програму в покроковому режимі.
4. Скласти програму Hash2.cpp для реалізації додавання елементів у хеш-таблицю при лінійному хешуванні і заповнення її випадково згенерованими числами.
5. Виконати програму в покроковому режимі для 8 випадкових чисел.

Запитання для самоконтролю

1. У чому особливість хеш-таблиці?
2. У чому відмінність відкритого і закритого хешування?.
3. Поясніть принципи виконання основних операцій при відкритому хешуванні.
4. Поясніть побудову хеш-функції при лінійному хешуванні.