Лабораторная работа №3. Хеш-таблицы
Цель работы: изучение способов использования хеширования данных на ЭВМ: открытое и закрытое хеширование. Оценка быстродействия основных операций и объема памяти по сравнению со списками, массивами и двоичными деревьями.
Задание
1. Определить поля для записей, которые будут храниться в списке согласно своему варианту из лабораторной работы N1. Выбрать ключевое поле (уникальное для всех записей).
2. Разработать алгоритм для вычисления значения хеш-функции, которая должна разбивать исходное множество ключей на K подмножеств (сегментов).
3. Разработать алгоритмы операций для вставки, удаления записей, получения отдельной записи по ключу.
4. Разработать алгоритм для увеличения количества сегментов в 2 раза, когда степень заполнения хеш-таблицы превышает допустимую (число записей начинает превышать число сегментов) в M раз.
5. Реализовать алгоритмы на языке Паскаль или Си. Все функции и процедуры разбить на два типа: работающие с деревом и взаимодействующие с пользователем. Структура дерева должна содержать переменную – код ошибки, через которую процедуры, работающие с данными, будут сообщать об ошибках.
6. Составить и выполнить контрольный пример, проверяющий работу всех операций.
7. Оценить затраты памяти для хранения данных в виде хеш-таблицы и быстродействие операций вставки, поиска и удаления записей. Сравнить полученные данные с тем, что было в лабораторных работах NN 1, 2.
8. Составить отчет о проделанной работе.
Содержание отчета
1. Постановка задачи
2. Описание структур данных
3. Описание алгоритмов
4. Описание контрольного примера
5. Результаты оценки быстродействия
6. Текст программы
Варианты заданий
1. Закрытое хеширование – предел заполнения M = 0.9 (NN1-15 в группе)
2. Открытое хеширование – предел заполнения M = 2.0 (NN16-40 в группе)
Литература
1. Структуры данных и алгоритмы: Пер. с англ.- М.: Издательский дом "Вильямс", 20с. (глава 4. Основные операторы множеств)
2. Алгоритмы и структуры данных: Пер. с англ.- М.: Мир, 19с. (глава 5. Преобразование ключей)
