Хэш поиск

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

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

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

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

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

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

Выполнил: студент группы И-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	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	ar, h(ar)=4   начало конец
…	…
m		nil nil

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

Построение:

·          Находим значение хэш функции и по этому значению входим в таблицу

·          Если она пустая, то записываем в нее ключ

·          Если она занятая, то сравниваем ключ с заданным ключом:

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

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

Поиск:

·          Находим значение хэш функции для искомого ключа и этому значению входим в таблицу

·          Если ячейка пустая, то поиск заканчивается неудачей

·          Если она не пустая, то выполняем сравнение ключей:

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

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

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

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

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

 

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

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

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

Типы полей:

1.         Простейшие примитивные типы.

2.         Структурированные типы.

3.         Объектные свойства представляющие из себя объекты той же самой или другой природы. (наличие объектных свойств является проявлением одного из способов взаимодействия объектов, а именно композицией объектов, которая используется в курсовой программе)

Набор свойств объекта создается при описании объекта и в дальнейшем изменяется. Поведение объекта описывается набором методов. Каждый метод представляет из себя программный код.

Объединение вместе обрабатываемых данных и программного кода их обработки называется признаком инкапсуляции.

Можно выделить следующие типичные методы объектов:

1.          Конструкторы, деструкторы

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

Деструктор отвечает за разрушение объекта т.е освобождение выделенной объекту памяти.

2.          Методы, с помощью которых можно узнать текущее значение тех или иных свойств. Обычно для каждого свойства создается свой такой метод. Такие методы принято называть с префикса Get. (Пример: GetFIO)

3.          Методы, которые изменяют значение одного или нескольких свойств. Такие методы принято называть с префикса Set . (Пример: SetFIO).

Использование Set и Get методов объясняется следующим:

По принципам объектного подхода свойства объекта должны быть закрыты для постороннего прямого доступа. Доступ к свойствам разрешается только через вызовы Get и Set методов. Это является еще одним проявлением принципа инкапсуляции: сокрытие информации об объекте. В этом случаи внутренне хранилище данных объекта полностью закрыто от постореннего воздействия. Набор методов доступа образуют открытый интерфейс объекта.

Кроме перечисленных методов объект может иметь уникальные методы, определяющие его функциональность.

Класс представляет из себя шаблон описания однотипных объектов.

На основе одного класса можно создать любое число объектов, называемых экземплярами классов. Именно при описании класса перечисляются свойства и методы соответствующих объектов. С описания класса начинается написание любой объектной программы.

2.   Описание классов

Описание классов включает в себя:

1.          Заголовок класса с именем класса

Пример: type MyMasClass = class.

2.          Тело класса, содержащее перечень свойств (поля данных) и перечень методов обычно задаваемых только своими заголовками.

Пример:

private

 mas:array [1..10]of TList;// свойство

 public

 Constructor Create(aKey:string);// методы

***

еnd;