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