Лабораторная работа. Хеширование данных. Выбор хеш-функции. Разрешение коллизий. Анализ сложности хеширования с разными типами адресации
Лабораторная работа №5 предназначена для изучения построения функции хеширования и алгоритмов хеширования данных, а также для приобретения навыков разработки и применения алгоритмов открытого и закрытого хеширования при решении задач на языке Turbo Pascal.
Разработать программы, в соответствии с заданиями в пункте 6.2 и представить отчет в соответствии с приложением В.
Последовательность выполнения лабораторной работы №5 представлена в приложении Б.
Заканчивается работа защитой с оценкой «зачтено» или «незачтено» в виде экспресс-опроса в рамках теоретического и практического материала, отнесенного к пунктам 6.1 и 6.2. Примерный перечень вопросов приведен в пункте 6.3.
На выполнение и защиту лабораторной работы отводится 4 академических часа.
6.1 Краткие теоретические сведения
6.1.1 Хеширование данных
Для ускорения доступа к данным в таблицах можно использовать предварительное упорядочивание таблицы в соответствии со значениями ключей.
Для сокращения времени доступа к данным в таблицах используется так называемое случайное упорядочивание или хеширование. При этом данные организуются в виде таблицы при помощи хеш-функции h, используемой для вычисления адреса по значению ключа.
Рисунок 6.1 – Организация хеш-таблицы
Идеальной хеш-функцией является такая hash-функция, которая для любых двух неодинаковых ключей дает неодинаковые адреса.
Подобрать такую функцию можно в случае, если все возможные значения ключей заранее известны. Такая организация данных носит название совершенное хеширование. В случае заранее неопределенного множества значений ключей и ограниченной длины таблицы, подбор совершенной функции затруднителен. Поэтому часто используют хеш-функции, которые не гарантируют выполнение условия.
При заполнении таблицы возникают ситуации, когда для двух неодинаковых ключей функция вычисляет один и тот же адрес. Данный случай носит название коллизия, а такие ключи называются ключи-синонимы.
6.1.2 Методы разрешения коллизий
Для разрешения коллизий используются различные методы, которые в основном сводятся к методам цепочек (открытое хеширование) и открытой адресации (внутреннее хеширование).
Рисунок 6.2 – Разновидности методов разрешения коллизий
Методом цепочек, показанный на рисунке 6.3, называется метод, в котором для разрешения коллизий во все записи вводятся указатели, используемые для организации списков цепочек переполнения. В случае возникновения коллизии при заполнении таблицы в список для требуемого адреса хеш-таблицы добавляется еще один элемент.
Поиск в хеш-таблице с цепочками переполнения осуществляется следующим образом. Сначала вычисляется адрес по значению ключа. Затем осуществляется последовательный поиск в списке, связанном с вычисленным адресом.
Процедура удаления из таблицы сводится к поиску элемента и его удалению из цепочки переполнения.
Рисунок 6.3 – Разрешение коллизий при добавлении элементов методом цепочек
Данный метод реализуется на основе линейного однонаправленного списка в динамической памяти, где информационное поле будет являться ключом.
Type Hash = ^PHash;
PHash = record
Data: Datatype; {ключевое поле}
Next:hash;
End;
Объявление таблицы выглядит следующим образом:
Const
n = …; {размерность хеш-таблицы}
var
table = array [1..n] of hash; {хеш-таблица}
Метод открытой адресации состоит в том, чтобы, пользуясь каким-либо алгоритмом, обеспечивающим перебор элементов таблицы, просматривать их в поисках свободного места для новой записи.
Рисунок 6.4 – Разрешение коллизий при добавлении элементов методами открытой адресации
6.2 Задания на лабораторную работу
Дан текстовый файл tel.txt, который представляет из себя телефонный справочник, содержащий строки следующего вида:
Петров
333333
Иванов
111111
…
Используя метод хеширования с открытой адресацией, написать программу поиска записи по первым трем буквам фамилии.
Указания: в качестве хеш-функции использовать:
-
сумму кодов символов по модулю m;
-
сумму квадратов кодов символов по модулю m.
В качестве метода адресации использовать:
-
линейный;
-
квадратичный;
-
двойное хеширование.
Реализовать различные хеш-функции и методы открытой адресации.
-
То же условие задачи, что и в предыдущем задании, но использовать хеширование при помощи цепочек.
-
*Постройте хеш-таблицу для зарезервированных слов, используемого языка программирования (не менее 20 слов). При возникновении коллизий использовать любой из существующих методов их разрешения. Организовать поиск и добавление зарезервированного слова.
-
*В текстовом файле содержатся целые числа. Постройте хеш-таблицу из чисел файла. Осуществите поиск введенного целого числа в хеш-таблице. Сравните результаты количества сравнений при различном наборе данных в файле.
|