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

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)=(aimodm) + 1;

Хорошей является хэш-функция, которая удовлетворяет следующим условиям:

· Функция должна быть очень простой с вычислительной точки зрения

· Функция должна распределять ключи в хэш-таблице как можно более равномерно.

Если два разных ключа претендуют на одну и ту же ячейку массива, то такая ситуация называется конфликтом ключей.

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

Для решения проблемы с конфликтующими ключами были предложены несколько методов, которые можно сгруппировать на две основные группы:

· Открытое хэширование

--> ЧИТАТЬ ПОЛНОСТЬЮ <--