Курсовая работа: Хэш поиск

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

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

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

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

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

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

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

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

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

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

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

Типы полей:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример: typeMyMasClass = class.