(4 часа)
Цель работы: Освоить на практике алгоритмы организации хеш-таблиц с открытой адресацией и хеш-таблиц с разрешением коллизий методом цепочек.
Домашнее задание:
1. Изучить алгоритмы организации хеш-таблиц с открытой адресацией, способы разрешения коллизий для таких таблиц, а так же алгоритмы поиска по ключу, добавления и удаления элемента.
2. Изучить организацию хеш-таблиц с разрешением коллизий методом цепочек.
Порядок выполнения работы.
1. Открыть проект Delphi Structures.
2. Добавить в управляющее главное меню пункт «Лабораторная работа №8», при выборе которого должно появляться окно модуля «Hesh» (модуль «Hesh» с формой добавить в проект).
3. Установить на форму модуля Hesh компоненты, обеспечивающие ввод исходных данных, управляющую кнопку (класса TButton или TBitBtn) и компоненты для вывода результатов на экране в соответствии с вариантом задания таблицы №8.1.
4. В обработчике события onClick управляющей кнопки на языке Object Pascal написать фрагмент программы для реализации алгоритма хеширования заданного ключа и дальнейшего поиска ключа в хеш-таблице в соответствии с вариантом задания.
5. Отладить обработчик на тестовых примерах и продемонстрировать работу приложения преподавателю.
6. произвести анализ запрограммированного алгоритма (по количеству сравнений).
7. Составить отчет и защитить работу преподавателю. В отчете обязательно представить блок-схему алгоритма решения задачи.
Таблица 8.1
| № вар. | Текст задачи |
| 1. | Организовать хеш-таблицу с открытой адресацией, используя хеш-функцию h(k)=trunc(M*Frac(k*d)), где d=(sqrt(5)-1)/2, M - размер хеш-таблицы. Организовать процедуру поиска по ключу в этой хеш-таблице. Результат поиска - номер ячейки с найденным ключом или (-1). |
| 2. | Организовать хеш-таблицу с открытой адресацией, используя процедуру поиска и вставки по ключу. Для формирования хеш-адреса использовать хеш-функцию универсального хеширования и процедуру линейного исследования для разрешения коллизии. |
| 3. | Организовать хеш-таблицу с открытой адресацией, используя процедуру поиска и вставки по ключу. Для формирования начального хеш-адреса использовать метод деления, а затем при возникновении коллизии процедуру квадратичного исследования. |
| 4. | Построить хеш-таблицу с открытой адресацией, используя двойное хеширование, как способ открытой адресации. Хеш-функция h1(k) и h2(k) организовать методом деления. Формирование таблицы - с помощью процедуры поиска и вставки по ключу. |
| 5. | Организовать хеш-таблицу, используя хеш-функцию h(k) по методу умножения для формирования хеш-адреса. разрешение коллизий - методом внешних цепочек. а) Написать процедуру поиска и вставки по ключу. б) Написать процедуру удаления ключа. |
| 6. | Организовать хеш-таблицу с помощью идеального хеширования - двухуровневая схема с универсальным хешированием на каждом уровне. Запрограммировать процедуру поиска и вставки по ключу. |
| 7. | Организовать программно хеширование 100 записей в таблицу. состоящую из 20 ссылок на линейные списки (стеки), первоначально пустые. записи имеют неотрицательные целые ключи k<50, формируемые случайным образом. Хеш-функцию организовать методом умножения в отдельной Function. |
| 8. | Организовать программно хеширование 50 записей в таблицу. состоящую из 10 ссылок на линейные списки (очереди), первоначально пустые. записи имеют неотрицательные целые ключи k<30, формируемые случайным образом. Хеш-функцию организовать методом деления в отдельной Function |
Контрольные вопросы
1. Что такое хеширование?
2. Какую структуру данных используют для формирования хеш-таблицы?
3.Что мы называем ситуацией конфликта или коллизией, возникающей при хешировании?
4. Как организована -таблица с прямой адресацией?
5. В чем заключается метод цепочек разрешения коллизии при хешировании?
6. Какие вы знаете хеш-функции?
7. Что такое хеш-таблица с открытой адресацией и каковы способы разрешения коллизий для нее?
8. Какова основная идея идеального хеширования?
9. Сформулируйте основное правило формирования вторичной хеш-таблицы.
Лабораторная работа № 9
