6.4. Задание к лабораторной работе

1. Спроектировать, реализовать и провести тестовые испытания АТД «Хеш-таблица» для коллекции, содержащей объекты произвольного типа. Тип объектов задаётся клиентской программой.

АТД «Хеш-таблица» представляет ассоциативное, неупорядоченное множество элементов, доступ к которым выполняется с использованием ключа.

Коллекция проектируется в двух вариантах:

• АТД «Хеш-таблица с цепочками коллизий»,

• АТД «Хеш-таблица с открытой адресацией»,

Интерфейс АТД «Хеш-таблица» включает следующие операции:

• опрос размера таблицы,

• опрос количества элементов в таблице,

• опрос пустоты таблицы,

• очистка таблицы,

• поиск элемента по ключу,

• вставка элемента по ключу,

• удаление элемента по ключу.

• итератор для доступа к элементам в таблице с операциями:

• установка на первый элемент в таблице,

• переход к следующему элементу в таблице,

• проверка окончания просмотра,

• доступ по чтению и записи к данным текущего элемента.

Для тестирования коллекций интерфейс АТД «Хеш-таблица» включает дополнительные операции:

• вывод структуры хеш-таблицы на экран,

• опрос числа проб, выполненных операцией.

2. Выполнить отладку и тестирование всех операций АТД «Хеш-таблица с цепочками коллизий» и АТД «Хеш-таблица с открытой адресацией» с помощью меню операций.

3. Получить экспериментальную оценку качества хеш-функции ², усреднённую по нескольким экспериментам.

4. Выполнить сравнительное тестирование средней трудоёмкости операций поиска, вставки и удаления для коллекций «Хеш-таблица с цепочками коллизий», и «Хеш-таблица с открытой адресацией» в зависимости от коэффициента заполнения α.

5. Провести сравнительный анализ теоретических и экспериментальных показателей трудоёмкости операций.

6. Составить отчёт по лабораторной работе. Отчёт должен содержать следующие пункты:

1. пункты 1 – 5 (см. раздел 2.2),

6. описание методики получения экспериментальной оценки ² и полученная оценка ², усреднённая по нескольким экспериментам.

7. описание методики тестирования трудоёмкости операций,

8. таблицы и графики с полученными оценками трудоёмкости операций. Должны быть приведены графики трудоёмкости для операций поиска, вставки и удаления для АТД «Хеш-таблица с цепочками коллизий» и АТД «Хеш-таблица с открытой адресацией»,

9. сравнительный анализ теоретических и экспериментальных оценок эффективности операций АТД,

10. выводы,

11. список использованной литературы,

12. приложение с текстами программ:

• полное определение классов и текстов методов класса,

• текст программы получения оценки ²,

• текст программы тестирования трудоёмкости операций АТД.

6.4.1. Варианты заданий:

Тип ключа - строка текста произвольной длины.

Преобразование строки - конкатенация битовых образов кодов символов.

Метод хеширования - модульный.

Метод разрешения коллизий – двойное хеширование.

Тип ключа - вещественное число на интервале [-10 000.00 , +10 000.00].

Метод хеширования - мультипликативный.

Метод разрешения коллизий - квадратичный.

Тип ключа - целое число на интервале [0 , [phone]].

Метод хеширования – выбор цифр.

Метод разрешения коллизий - линейное хеширование.

Тип ключа - строка текста произвольной длины.

Метод преобразования числа – формирование значения числа из кодов символов по схеме Горнера.

Метод хеширования – мультипликативный.

Метод разрешения коллизий - линейное хеширование.

Тип ключа - вещественное число на интервале [100 000.00 , +150 000.00].

Метод хеширования - модульный.

Метод разрешения коллизий - квадратичное хеширование.

Тип ключа - строка текста произвольной длины.

Преобразование строки - конкатенация битовых образов символов.

Метод хеширования - мультипликативный.

Метод разрешения коллизий - квадратичный.

Тип ключа - вещественное число на интервале [-5 000.000 , +5 000.000].

Метод хеширования - свёртка.

Метод разрешения коллизий - квадратичный.

Тип ключа – 12-значное натуральное число.

Метод хеширования - свёртка, комбинированная с выбором цифр.

Метод разрешения коллизий - линейный.