Хеширование. Алгоритмы организации и обработки хеш-таблиц

(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