Лабораторная работа сравнение данных с помощью хэш функции

Обновлено: 07.07.2024

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

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

Теоретические сведения.

Ознакомьтесь с материалом лекции 38.

Задания к лабораторной работе.

Выполните приведенные ниже задания.

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

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

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

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

Сравнить хэш-таблицы с различными способами разрешения коллизий: метод цепочек, метод двойного хэширования и метод линейного пробирования.

Хеширование – преобразование ключей к числам.

Хеш-таблица – массив ключей с особой логикой, состоящей из: 1. Вычисления хеш-функции, которая преобразует ключ поиска в индекс. 2. Разрешения конфликтов, т.к. два и более различных ключа могут преобразовываться в один и тот же индекс массива. Отношение порядка над ключами не требуется.

Хеш-функция ― преобразование по детерминированному алгоритму входного массива данных произвольной длины (один ключ) в выходную битовую строку фиксированной длины (значение). Результат вычисления хеш-фукнции называют «хешем».

Хеш-функция должна иметь следующие свойства:

Всегда возвращать один и тот же адрес для одного и того же ключа;
Не обязательно возвращает разные адреса для разных ключей;
Использует все адресное пространство с одинаковой вероятностью;
Быстро вычислять адрес.

Коллизией хеш-функции H называется два различных входных блока данных X и Y таких, что H(x) = H(y) .

Хеш-таблица – структура данных, хранящая ключи в таблице. Индекс ключа вычисляется с помощью хеш-функции. Операции: добавление, удаление, поиск. Пусть хеш-таблица имеет размер M , количество элементов в хеш-таблице – N .

Число хранимых элементов, делённое на размер массива (число возможных значений хеш-функции), называется коэффициентом заполнения хеш-таблицы (load factor). Обозначим его α = N/M .

Этот коэффициент является важным параметром, от которого зависит среднее время выполнения операций.

Парадокс дней рождений. При вставке в хеш-таблицу размером 365 ячеек всего лишь 23-х элементов вероятность коллизии уже превысит 50 % (если каждый элемент может равновероятно попасть в любую ячейку).

Хеш-таблицы различаются по методу разрешения коллизий. Основные методы разрешения коллизий:

Метод цепочек.
Метод открытой адресации.

Каждая ячейка массива является указателем на связный список (цепочку). Коллизии приводят к тому, что появляются цепочки длиной более одного элемента.

Вычисляем значение хеш-функции добавляемого ключа – h .
Находим A[h] – указатель на список ключей.
Вставляем в начало списка (в конец списка дольше). Если запрещено дублировать ключи, то придется просмотреть весь список.

Время работы: В лучшем случае – O(1) . В худшем случае – если не требуется проверять наличие дубля, то O(1) – иначе – O(N)

Вычисляем значение хеш-функции удаляемого ключа – h .
Находим A[h] – указатель на список ключей.
Ищем в списке удаляемый ключ и удаляем его.

Время работы: В лучшем случае – O(1) . В худшем случае – O(N) .

Вычисляем значение хеш-функции ключа – h .
Находим A[h] – указатель на список ключей.
Ищем его в списке.

Время работы: В лучшем случае – O(1) . В худшем случае – O(N) .

Среднее время работы операций поиска, вставки (с проверкой на дубликаты) и удаления в хеш-таблице, реализованной методом цепочек – O(1 + α) , где α – коэффициент заполнения таблицы.

Среднее время работы.

Среднее время работы операций поиска, вставки (с проверкой на дубликаты) и удаления в хеш-таблице, реализованной методом цепочек – O(1 + α), где α – коэффициент заполнения таблицы.

Доказательство. Среднее время работы – математическое ожидание времени работы в зависимости от исходного ключа. Время работы для обработки одного ключа T(k) зависит от длины цепочки и равно 1 + Nh(k) , где Ni – длина i-ой цепочки. Предполагаем, что хеш-функция равномерна, а ключи равновероятны.

Среднее время работы

Метод открытой адресации

Все элементы хранятся непосредственно в массиве. Каждая запись в массиве содержит либо элемент, либо NIL . При поиске элемента систематически проверяем ячейки до тех пор, пока не найдем искомый элемент или не убедимся в его отсутствии.

При поиске элемента систематически проверяем ячейки до тех пор, пока не найдем искомый элемент или не убедимся в его отсутствии.

Вычисляем значение хеш-функции ключа – h .
Систематически проверяем ячейки, начиная от A[h] , до тех пор, пока не находим пустую ячейку.
Помещаем вставляемый ключ в найденную ячейку. В п.2 поиск пустой ячейки выполняется в некоторой последовательности. Такая последовательность называется «последовательностью проб».

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

Важно, чтобы для каждого ключа k последовательность проб h(k, 0), h(k, 1), . , h(k, M − 1) представляла собой перестановку множества 0,1, . , M − 1 , чтобы могли быть просмотрены все ячейки таблицы.

Поиск ключа. Исследуется та же последовательность, что и в алгоритме вставки ключа. Если при поиске встречается пустая ячейка, поиск завершается неуспешно, поскольку искомый ключ должен был бы быть вставлен в эту ячейку в последовательности проб, и никак не позже нее.

Удаление ключа. Алгоритм удаления достаточен сложен. Нельзя при удалении ключа из ячейки i просто пометить ее значением NIL . Иначе в последовательности проб для некоторого ключа (или некоторых) возникнет пустая ячейка, что приведет к неправильной работе алгоритма поиска. Решение. Помечать удаляемые ячейки спец. значением «Deleted» . Нужно изменить методы поиска и вставки. В методе вставки проверять «Deleted» , вставлять на его место. В методе поиска продолжать поиск при обнаружении «Deleted» .

Вычисление последовательности проб. Желательно, чтобы для различных ключей k последовательность проб h(k, 0), h(k, 1), . , h(k, M − 1) давала большое количество последовательностей- перестановок множества 0,1. , M − 1 .

Обычно используются три метода построения h(k, i) :

Линейное пробирование.
Квадратичное пробирование.
Двойное хеширование.

h(k, i) = (h′(k) + i) mod M

Основная проблема – кластеризация. Последовательность подряд идущих занятых элементов таблицы быстро увеличивается, образуя кластер. Попадание в элемент кластера при добавлении гарантирует «одинаковую прогулку» для различных ключей и проб. Новый элемент будет добавлен в конец кластера, увеличивая его.

h(k, i) = (h1(k) + ih2(k)) mod M.

Требуется, чтобы последовательность проб содержала все индексы 0, .. , M–1 . Для этого все значения h2(k) должны быть взаимно простыми с M .

M может быть степенью двойки, а h2(k) всегда возвращать нечетные числа.
M простое, а h2(k) меньше M .

Общее количество последовательностей проб O(M^2) .

Лучший случай	В среднемю Метод цепочек.	В среднем. Метод открытой адресации.	Худший случай.
Поиск	O(1)	O(1 + a)	O(1 / 1 - a)	O(n)
Вставка	O(1)	O(1 + a)	O(1 / 1 - a)	O(n)
Удаление	O(1)	O(1 + a)	O(1 / 1 - a)	O(n)

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

Для запуска необходиа java версии 1.8 и Apache Maven версии 3.5.0. Для компиляции необходимо в корне проекта выполнить команду

А для запуска программы

Оба параметра являются обязательными.

Во время выполнения в консоль будут выведены выполненные команды.

Формат входных данных

Примеры: add 10 20 search 15 print min

Команда print отражает внутреннее строение структуры данных. Для хэш-таблицы с методом цепочек вывод команды print будет иметь следующий вид:

<> - отдельная ячейка массива, в которой храниться список ключей. А для хеш-таблиц с открытой адресацией вывод будет выглядеть так:

Hash table: [ 755 D __ 855 __ 942 __ 346 __ 588 __ 576 ]

__ - пустая ячейка, D - удаленная ячейка.

Формат выходных данных

В выходной файл выводятся результаты исполнения программы.

Команда print должна отражать внутреннее строение структуры данных

Команда search выводит error, в случае, когда значение не было найдено, или значение найденное по ключу в противном случае.

Команда add добавляет значение в таблицу (Ничего не выводит).

Команда delete удаляетя число, или ничего не делает, если значение не было найдено (Ничего не выводит).

Команда min выводит минимальное число в таблице, или empty, если таблица пустая.

Команда max выводит максимальное число в таблице,или empty, если таблица пустая.

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

1.Юнит тесты, проверящие корректность работы методов каждой хеш-таблицы

Тесты находятся в ./src/test/java/tests/

2.Юнит тесты для провеки времени выполнения большого числа операций добавления, поиска и удаления.

Тесты находятся в ./src/test/java/tests/

3.Файлы с входными данными и правильными ответами.

На вход программе подается два файла.

Заитем выходной файл с результатами исполнения программы сравнивается с файлом в котором находятся правильные ответы

Тесты находятся в ./tests/

Подробное описание тестов

1.Простая проверка всех операций кроме print

2.Проверка корректной работы add, delete(удаление элементов по несушествуюшему ключу) и print

3.Проверка корректной работы add, delete(удаление элементов по сушествуюшему ключу) и print

4.Проверка корректной работы search(поиск элементов по несушествуюшему ключу)

5.Проверка корректной работы search(поиск элементов по сушествуюшему ключу)

Сравнение времени работы

Время работы рачитываем тестом с 1000000 операций каждого типа.

Search time: 354

Delete time: 255

Search time: 281

Delete time: 365

Search time: 273

Delete time: 377

При использовании открытой адресации двойное хеширование обычно превосходит квадратичное пробирование. Единственным исключением является ситуация, в которой доступен большой объем памяти, а данные не расширяются после создания таблицы; в этом случае линейное пробирование несколько проще реализуется, а при использовании коэффициентов нагрузки менее 0,5 не приводит к заметным потерям производительности.

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

Если не уверены — используйте метод цепочек. У него есть свои недостатки — прежде всего необходимость в дополнительном классе связанного списка, но зато если в список будет внесено больше данных, чем ожидалось изначально, реализация по крайней мере не замедлится до полного паралича.

План выполнения домашнего задания

You can’t perform that action at this time.

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.

Читайте также: