Хэш поиск

Курсовой проект - Компьютеры, программирование

Другие курсовые по предмету Компьютеры, программирование

Скачать Бесплатно!
Для того чтобы скачать эту работу.
1. Подтвердите что Вы не робот:
2. И нажмите на эту кнопку.
закрыть



Министерство образования и науки РФ

Академия управления ТИСБИ

Факультет информационных технологий

 

 

 

 

 

 

 

 

Курсовая работа

по предмету Объектно-ориентированное программирование

тема: Объектная реализация хэш-поиска

 

 

 

 

 

 

Выполнил: студент группы И-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.Открытое хэширование.

 

Сама идея открытого хэширования очень проста: связать все элементы с одним и тем же значением хэш-функции во вспомогательный линейный список.

 

индексключуказатели1ai

h(ai)=1начало

конец2nil

nil3as

h(as)=3nil

nil4ak

h(ak)=4начало

конец……

mnil

nil

Алгоритмы построения и поиска хэш таблицы.

Построение:

  • Находим значение хэш функции и по этому значению входим в таблицу
  • Если она пустая, то записываем в нее ключ
  • Если она занятая, то сравниваем ключ с заданным ключом:

1. если ключи совпадают, то обрабатываем повторный ключ

2. иначе добавляем новый ключ в конец списка

 

Поиск:

  • Находим значение хэш функции для искомого ключа и этому значению входим в таблицу
  • Если ячейка пустая, то поиск заканчивается неудачей
  • Если она не пустая, то выполняем сравнение ключей:

1. Если ключи совпадают, то поиск заканчивается за одно сравнение

2. Иначе организуем просмотр вспомогательного списка с положительным или отрицательным результатом.

 

Для данного метода большое значение имеет равномерность распределения ключей по хеш-таблице, что гарантирует короткие вспомогательные списки и тем самым уменьшает число сравнений при поиске.Наихудшим является случай, когда для всех ключей хеш-функция дает одно и тоже значение, и все элементы выстраиваются в один длинный линейный список.

Другим фактором, влияющим на эффективность открытого хеширования, является размер хеш-таблицы по отношению к числу входных данных. Если эти величины равны, то теоретически можно обойтись без линейных списков, если между ключами нет конфликтов. На практике рекомендуют выбирать размер хеш-таблицы равным n/2.

3. Основные понятия объектной технологии

 

  1. Объекты и классы.

 

Объект это любая сущность, имеющая некоторые набор свойств и обладающее некоторым поведением.

Свойство объекта описывается как обычные поля данных. В этих полях хранятся значения соответствующих свойств.

Типы полей:

  1. Простейшие примитивные типы.
  2. Структурированные типы.
  3. Объектные свойства представляющие из себя объекты той же самой или другой природы. (наличие объектных сво

s