Задание 2. Тема Хеширование. Основные методы вычисления хешфункций метод деления, метод умножения, динамическое хеширование, расширяемое хеширование. Разрешение коллизий

• Название: Тема Хеширование. Основные методы вычисления хешфункций метод деления, метод умножения, динамическое хеширование, расширяемое хеширование. Разрешение коллизий
• Дата: 24.11.2022
• Размер: 19.26 Kb.
• Имя файла: Задание 2.docx
• Тип: Решение; #811120

Практическое задание 2

Тема 4.1. Хеширование. Основные методы вычисления хеш-функций: метод деления, метод умножения, динамическое хеширование, расширяемое хеширование. Разрешение коллизий

Цель работы: изучить построение функции хеширования и алгоритмов хеширования данных и научиться разрабатывать алгоритмы открытого и закрытого хеширования при решении задач на языке C++ .

Формулировка задания 2

1. 
   Разработка алгоритма хеш-функции для реализации таблиц идентификаторов:
   

1. 
   Разработайте программу на выбранном языке программирования, генерирующую 400 случайных идентификаторов (начинаются с символа латиницы и имеют случайную длину), и сохраните их в файл ID.txt.
   
2. 
   Выберите две любые хеш-функции на основе открытых источников или предложенной для практики литературы. Диапазон значений хеш-функций должен лежать в пределах от 1 до 1000.
   
3. 
   Реализуйте вычисление хеш-функций на выбранном языке программирования.
   
4. 
   Реализуйте чтение идентификаторов с файла ID.txt, вычисление для них хеш-функции и сохранение в массив M_ID в ячейку с номером полученного хеш-значения идентификатора (для которого вычислялась хеш-функция).
   
5. 
   Если в данном элементе массива уже есть идентификатор (коллизия), то добавьте новый идентификатор через разделитель к имеющемуся в элементе массива. Одновременно занесите оба идентификатора в отдельный массив M_Col в порядке их обнаружения.
   
6. 
   По окончании чтения всего списка входных идентификаторов выведите массивы M_Col и M_ID в отдельные файлы с расширением txt.
   

• 
  Файл M_ID должен иметь запись всех ячеек массива в порядке возрастания с указанием в первом столбце номера элемента массива. Пустые элементы также подлежат выводу в файл.
  
• 
  Файл M_Col должен содержать номер элемента массива, хеш-значение и список идентификаторов.
  
• 
  В конце файла должно быть вычислено отношение количества коллизий к количеству идентификаторов в %.
  
• 
  Расчет хеш-значений должен быть выполнен для двух хеш-функций.
  

g. Проведите сравнение полученных результатов на эффективность хеш-функций с точки зрения возникновения коллизий.

2. Разработка и реализация модуля по созданию таблицы идентификаторов:

1. 
   Разработайте программу, реализующую создание таблицы идентификаторов по заданным алгоритмам (один из них на основе хеш-функции, взятой из предыдущей работы). В качестве реализации возьмите за основу автоматное программирование.
   
2. 
   Добавьте в программу глобальный счетчик для подсчета затраченных элементарных тактов процессора с целью исследования эффективности разработанной программы.
   
3. 
   Выполните исследование эффективности работы разработанной программы с помощью подсчета затраченных элементарных операций при заполнении таблицы идентификаторов на 25, 50, 75 и 100 %.
   
4. 
   Представьте сравнительный анализ эффективности работы разработанной программы в виде электронной таблицы с получением выводов по данным алгоритмам реализации.
   

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

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

Задание нужно решать на основании изученных методов создания, вывода и обработки динамических данных в языке C++.

Выполнять задание необходимо в соответствии с указанными этапами:

• выбрать метод решения задачи;

• разработать графическую схему алгоритма;

• записать разработанный алгоритм на языке C++;

• разработать контрольный тест к программе;

• отладить программу;

• представить отчет по работе.

Требования к отчету

Структура отчета должна соответствовать приведенным выше этапам:

• титульный лист;

• алгоритм решения задачи. Схема алгоритма выполняется по ЕСПД (ГОСТ 19.003-80 и ГОСТ 19.002-80);

• листинг программы;

• контрольный тест;

• выводы.