1 Постановка задачи
Цель работы: изучение возможности хэширования данных для организации поиска.
Порядок выполнения работы:
1.Разработать подпрограмму хеширования массива целых чисел методом прямого связывания и подпрограмму поиска в хэш-таблице элемента по заданному ключу. Вывести на экран построенную хэш-таблицу.
2.Реализовать подпрограмму хеширования массива целых чисел методом открытой адресации. Для разрешения коллизий использовать линейные и квадратичные пробы. Вывести на экран заполненные хеш-таблицы для m=11 в виде таблицы.
3.Подсчитать и сравнить количество коллизий при линейных и квадратичных пробах. Построить таблицу и проанализировать полученные результаты.
4.Организовать поиск элемента с заданным ключом для метода открытой адресации (линейные и квадратичные пробы).
2 Описание основных методов, используемых в работе
Функция
int hash(int key, int N)
реализует простой алгоритм хэширвоания основанный на взятии остатка от деления key % N.
Для реализации метода прямого связывания описаны следующие структуры и переменные:
int OpenN = 11; //Размер таблицы
struct OpenHash //Узел в таблице
{
int Size; //Количество элементов в списке
int * Data; //Сам список
};
OpenHash * OpenData; //Хэш-таблица
Для работы с этой хэш-таблицей описаны следующие функции:
void InitOpenHash(int N) //Начальная разметка таблицы для открытого хэширования
void AddOpenHash(int key) //Добавить
bool FindOpenHash(int key) //Найти
void PrintOpenHash() //Напечатать
Для реализации метода открытой адресации (линейные и квадратичные пробы) описаны следующие структуры и переменные:
struct CloseHash
{
int * key; //Ссылка на значение ключа
};
int CloseN; //размер таблицы
CloseHash * CloseData01 = NULL;
CloseHash * CloseData02 = NULL;
CloseHash * CloseData1 = NULL;
CloseHash * CloseData2 = NULL;
int Collisions; //коллизии
int Q = 3; //Шаг
Для работы с этой хэш-таблицей описаны следующие функции:
void InitCloseHash(int N, CloseHash * &CloseData) //Начальная разметка таблицы
bool AddCloseHash(int * key, int(*next)(int index,int probe), CloseHash * &CloseData) //Добавить
bool FindCloseHash(int key, int(*next)(int index, int probe), CloseHash * &CloseData) //Найти
void PrintCloseHash(CloseHash * &CloseData) //Напечатать
int Linear(int start, int probe) //Линейная проба с шагом Q
int Square(int start, int probe) //Квадратичная проба
3 Результат работы
В результате работы разработана программа.
На первом этапе в программе строится хэш-таблица методом прямого связывания для массива целых чисел и выводится на экран (рисунок 1).
На втором этапе в программе строится хэш-таблица методом открытой адресации. Для разрешения коллизий используются линейные и квадратичные пробы. На экран выводятся заполненные хеш-таблицы для m=11 (рисунок 2).
Рисунок 2 – Заполненные хеш-таблицы для m=11 (линейные и квадратичные пробы)
Далее на экран выводится результат подсчета и сравнения количества коллизий при линейных и квадратичных пробах (рисунок 3).
Рисунок 3 – Результат подсчета и сравнения количества коллизий при линейных и квадратичных пробах
После этого программа позволяет выполнить поиск элемента с заданным ключом для метода открытой адресации (линейные и квадратичные пробы). Результат показан на рисунке 4.
Рисунок 3 – Поиск элемента с заданным ключом для метода открытой адресации
4 Анализ результатов
В процессе работы рассмотрены алгоритмы хэширования: методом прямого связывания и методом открытой адресации (линейные и квадратичные пробы). Для метода открытой адресации проведено сравнение эффективности применения линейных и квадратичных проб для разрешения коллизий. Из полученной таблицы видно, что метод квадратичной пробы дает меньшее число коллизий, чем метод линейной пробы.