Системное программное обеспечение. Лабораторный практикум - [9]
Хэш-адресация – это метод, который применяется не только для организации таблиц идентификаторов в компиляторах. Данный метод нашел свое применение и в операционных системах, и в системах управления базами данных [5, 6, 11].
Требования к выполнению работы
Порядок выполнения работы
Во всех вариантах задания требуется разработать программу, которая может обеспечить сравнение двух способов организации таблицы идентификаторов с помощью хэш-адресации. Для сравнения предлагаются способы, основанные на использовании рехэширования или комбинированных методов. Программа должна считывать идентификаторы из входного файла, размещать их в таблицах с помощью заданных методов и выполнять поиск указанных идентификаторов по требованию пользователя. В процессе размещения и поиска идентификаторов в таблицах программа должна подсчитывать среднее число выполненных операций сравнения для сопоставления эффективности используемых методов.
Для организации таблиц предлагается использовать простейшую хэш-функцию, которую разработчик программы должен выбрать самостоятельно. Хэш-функция должна обеспечивать работу не менее чем с 200 идентификаторами, допустимая длина идентификатора должна быть не менее 32 символов. Запрещается использовать в работе хэш-функции, взятые из примера выполнения работы.
Лабораторная работа должна выполняться в следующем порядке:
1. Получить вариант задания у преподавателя.
2. Выбрать и описать хэш-функцию.
3. Описать структуры данных, используемые для заданных методов организации таблиц идентификаторов.
4. Подготовить и защитить отчет.
5. Написать и отладить программу на ЭВМ.
6. Сдать работающую программу преподавателю.
Требования к оформлению отчета
Отчет по лабораторной работе должен содержать следующие разделы:
• задание по лабораторной работе;
• описание выбранной хэш-функции;
• схемы организации таблиц идентификаторов (в соответствии с вариантом задания);
• описание алгоритмов поиска в таблицах идентификаторов (в соответствии с вариантом задания);
• текст программы (оформляется после выполнения программы на ЭВМ);
• результаты обработки заданного набора идентификаторов (входного файла) с помощью методов организации таблиц идентификаторов, указанных в варианте задания;
• анализ эффективности используемых методов организации таблиц идентификаторов и выводы по проделанной работе.
Основные контрольные вопросы
• Что такое таблица символов и для чего она предназначена? Какая информация может храниться в таблице символов?
• Какие цели преследуются при организации таблицы символов?
• Какими характеристиками могут обладать лексические элементы исходной программы? Какие характеристики являются обязательными?
• Какие существуют способы организации таблиц символов?
• В чем заключается алгоритм логарифмического поиска? Какие преимущества он дает по сравнению с простым перебором и какие он имеет недостатки?
• Расскажите о древовидной организации таблиц идентификаторов. В чем ее преимущества и недостатки?
• Что такое хэш-функции и для чего они используются? В чем суть хэш-адресации?
• Что такое коллизия? Почему она происходит? Можно ли полностью избежать коллизий?
• Что такое рехэширование? Какие методы рехэширования существуют?
• Расскажите о преимуществах и недостатках организации таблиц идентификаторов с помощью хэш-адресации и рехэширования.
• В чем заключается метод цепочек?
• Расскажите о преимуществах и недостатках организации таблиц идентификаторов с помощью хэш-адресации и метода цепочек.
• Как могут быть скомбинированы различные методы организации хеш-таблиц?
• Расскажите о преимуществах и недостатках организации таблиц идентификаторов с помощью комбинированных методов.
Варианты заданий
В табл. 1.1 перечислены методы организации таблиц идентификаторов, используемые в заданиях.
В табл. 1.2 даны варианты заданий на основе методов организации таблиц идентификаторов, перечисленных в табл. 1.1.
Пример выполнения работы
Задание для примера
В качестве примера выполнения лабораторной работы возьмем сопоставление двух методов: хэш-адресации с рехэшированием на основе псевдослучайных чисел и комбинации хэш-адресации с бинарным деревом. Если обратиться к приведенной выше табл. 1.1, то такой вариант задания будет соответствовать комбинации методов 2 и 7 (в табл. 1.2 среди вариантов заданий такая комбинация отсутствует).
Выбор и описание хэш-функции
Для хэш-адресации с рехэшированием в качестве хэш-функции возьмем функцию, которая будет получать на входе строку, а в результате выдавать сумму кодов первого, среднего и последнего элементов строки. Причем если строка содержит менее трех символов, то один и тот же символ будет взят и в качестве первого, и в качестве среднего, и в качестве последнего.
Будем считать, что прописные и строчные буквы в идентификаторах различны.[2] В качестве кодов символов возьмем коды таблицы ASCII, которая используется в вычислительных системах на базе ОС типа Microsoft Windows. Тогда, если положить, что строка из области определения хэш-функции содержит только цифры и буквы английского алфавита, то минимальным значением хэш-функции будет сумма трех кодов цифры «0», а максимальным значением – сумма трех кодов литеры «z».
