Системное программное обеспечение. Лабораторный практикум. Алексей Молчанов

Чтение книги онлайн.

СКАЧАТЬ эффективной хэш-функции – это отдельная задача разработчиков компиляторов, и полученные результаты, как правило, держатся в секрете. Хорошая хэш-функция распределяет поступающие на ее вход идентификаторы равномерно на все имеющиеся в распоряжении адреса, чтобы свести к минимуму количество коллизий. В настоящее время существует множество хэш-функций, но, как было показано выше, идеального хэширования достичь невозможно.

      Хэш-адресация – это метод, который применяется не только для организации таблиц идентификаторов в компиляторах. Данный метод нашел свое применение и в операционных системах, и в системах управления базами данных [5, 6, 11].

      Требования к выполнению работы

      Порядок выполнения работы

      Во всех вариантах задания требуется разработать программу, которая может обеспечить сравнение двух способов организации таблицы идентификаторов с помощью хэш-адресации. Для сравнения предлагаются способы, основанные на использовании рехэширования или комбинированных методов. Программа должна считывать идентификаторы из входного файла, размещать их в таблицах с помощью заданных методов и выполнять поиск указанных идентификаторов по требованию пользователя. В процессе размещения и поиска идентификаторов в таблицах программа должна подсчитывать среднее число выполненных операций сравнения для сопоставления эффективности используемых методов.

      Для организации таблиц предлагается использовать простейшую хэш-функцию, которую разработчик программы должен выбрать самостоятельно. Хэш-функция должна обеспечивать работу не менее чем с 200 идентификаторами, допустимая длина идентификатора должна быть не менее 32 символов. Запрещается использовать в работе хэш-функции, взятые из примера выполнения работы.

      Лабораторная работа должна выполняться в следующем порядке:

      1. Получить вариант задания у преподавателя.

      2. Выбрать и описать хэш-функцию.

      3. Описать структуры данных, используемые для заданных методов организации таблиц идентификаторов.

      4. Подготовить и защитить отчет.

      5. Написать и отладить программу на ЭВМ.

      6. Сдать работающую программу преподавателю.

      Требования к оформлению отчета

      Отчет по лабораторной работе должен содержать следующие разделы:

      • задание по лабораторной работе;

      • описание выбранной хэш-функции;

      • схемы организации таблиц идентификаторов (в соответствии с вариантом задания);

      • описание алгоритмов поиска в таблицах идентификаторов (в соответствии с вариантом задания);

      • текст программы (оформляется после выполнения программы на ЭВМ);

      • результаты обработки заданного набора идентификаторов (входного файла) с помощью методов организации таблиц идентификаторов, СКАЧАТЬ