6.4.2. Методические указания к выполнению задания

1. Коллекции «Хеш-таблица с цепочками коллизий» и «Хеш-таблица с открытой адресацией» разрабатываются, как отдельные шаблонные классы-контейнеры. Шаблонный класс «Хеш-таблица с цепочками коллизий» для организации цепочек использует внешний шаблонный класс «Список».

2. Параметрами шаблона являются тип ключа, тип данных.

3. Размер хеш-таблицы вычисляется конструктором коллекции в зависимости от заданного количества элементов с учётом типа хеш-таблицы, метода хеширования, указанного в варианте задания, и рекомендуемой величины α.

4. Для реализации операций АТД, рекомендуется использовать алгоритмы, приведённые в приложении 5.

5. Для тестирования разработанного класса – контейнера разрабатываются две программы - программа тестирования операций через меню, и программа тестирования трудоёмкости операций поиска, вставки и удаления.

6. Тестирование операций через меню выполняется для небольшого размера таблицы (до 10 элементов). Тип данных, хранящихся в нём, задаётся с клавиатуры перед началом тестирования. После выполнения операции необходимо выводить на экран содержимое структуры хеш-таблицы с помощью операции вывода её структуры. При выводе структуры следует отражать состояние, как свободных, так и занятых позиций хеш-таблицы, содержимое цепочек коллизий.

7. Для получения оценки ² использовать количество ключей, минимум в 20 раз превышающее размер хеш-таблицы.

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

9. Перед тестированием эффективности операций для обеих коллекций задаётся количество элементов, для хранения которых предназначена хеш-таблица. В качестве исходных данных для тестирования задаётся коэффициент заполнения α. Для коллекции «Хеш-таблица с цепочками коллизий» изменение α задаётся неравенством 0,1 α10. Для коллекции «Хеш-таблица с открытой адресацией» изменение α задаётся неравенством 0,1 α1. После тестирования на экран выводится коэффициент заполнения и полученные оценки трудоёмкости для операций поиска, вставки и удаления элементов.

6.5. Контрольные вопросы и упражнения.

1. Приведите размер хеш-таблицы с открытой адресацией, предназначенной для хранения 200 элементов, если она использует мультипликативный метод хеширования, модульный метод хеширования.

2. Приведите вид первоначально пустой хеш-таблицы с цепочками коллизий после вставки ключей 1, 89, 45, 76, 2, 13, 33, 4. Хеш-таблица предназначена для хранения 20 элементов, использует модульное хеширование.

3. Приведите вид первоначально пустой хеш-таблицы с открытой адресацией после вставки ключей 1, 89, 45, 76, 2, 13, 33, 4. Хеш-таблица предназначена для хранения 10 элементов, использует модульное хеширование.

4. Приведите соответствующий строке JKRSDS ключ, полученный методом конкатенация битовых образов для хеш-таблицы размером 1000.

5. Приведите соответствующий числу 1263454756 ключ, полученный методом свертки для хеш-таблицы размером 1000.

6. Какая последовательность ячеек получается в результате квадратичного зондирования, если h (k) = k mod 11 и k = 19.

7. Какая последовательность зондируемых ячеек получается в результате двойного хеширования: h (k) = k mod 11, h₁(k) = 1 + (k mod 10) и k = 19.