Міністерство освіти і науки РФ
Академія управління В«ТИСБИВ»
Факультет інформаційних технологій
Курсова робота
по предмету В«Об'єктно-орієнтоване програмуванняВ»
тема: В«Об'єктна реалізація хеш-пошукуВ»
Виконав: студент групи І-311
Хуснутдінов А.І.
Викладач:
Козин А.Н
Казань 2006
Зміст.
1. Постановка завдання ................................................................ 3 p> 3. Пошук з використанням Хеш-функцій .................................... 3
2. Основні поняття об'єктної технології ............................... 5
5. Опис класів ............................................................... 9
4. Опис користувацького інтерфейсу .................................. 11
6. Лістинг і опис всіх класів бібліотеки на DP .................... 14
7. Список використаної літератури ....................................... 25
1. Постановка завдання.
Мета роботи: розробка набору взаємопов'язаних класів для реалізації Hash-пошуку як спеціалізованого контейнера. Вирішення конфліктів за допомогою методу відкритого хешування (Методом ланцюжків). p> Створення зручного користувача інтерфейсу і отримання навичок роботи з взаємозв'язаними класами. p> Набір операцій:
1. Додавання:
1.1.В початок списку;
1.2.В кінець списку;
2. Видалення всього контейнера;
3. Пошук заданого елемента;
4. Повний прохід по Hash таблицею;
5. Збереження таблиці в зовнішньому файлі;
6. Завантаження таблиці із зовнішнього файлу;
2.Поіск з використанням Хеш-функцій.
В
2.1. Основні поняття.
Метод хеш-пошуку можна вважати майже ідеалом у серед пошукових методів. Він полягає в наступному. Деякі елементи розподіляються в масиві спеціальним чином. Для обчислення індексу розміщення осередку по вхідному ключу використовується спеціальна функція, яка називається хеш-функцією.
Масив, заповнений елементами, обумовленою хеш-функцією, називається хеш-таблицею.
Проста хеш-функція:
h (ai) = (ai mod m) + 1;
Доброю є хеш-функція, яка задовольняє таким умовам:
В· Функція повинна бути дуже простий з обчислювальної точки зору
В· Функція повинна розподіляти ключі в хеш-таблиці якомога більш рівномірно.
Якщо два різних ключа претендують на одну і ту ж комірку масиву, то така ситуація називається конфліктом ключів. p> Важливим практичним прикладом без конфліктної ситуації є побудова таблиці ключових слів у програмах-трансляторах з мов програмування. Тут набір ключових слів є постійним, змінюючись тільки при зміні версії транслятора, а з іншого боку, обробка транслятором вхідного тексту на мові програмування вимагає багаторазового і дуже швидкого розпізнавання в цьому тексті ключових слів мови.
Для вирішення проблеми з конфліктуючими ключами були запропоновані декілька методів, які можна згрупувати на дві основні групи:
В· Відкрите хешування
В· Внутрішнє хеширование
У цьому курсової роботі ми подивимося відкрите хешування.
2.2.Откритое хешування.
Сама ідея відкритого хешування дуже проста: зв'язати всі елементи з одним і тим же значенням хеш-функції в допоміжний лінійний список.
індекс
ключ
покажчики
1
ai
h (ai) = 1
aj, h (aj) = 1
at, h (at) = 1
af, h (af) = 1
Початок
кінець
2
nil
nil
3
as
h (as) = ​​3
nil
nil
4
ak
h (ak) = 4
