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