Хэш-табли́ца (перемешанная таблица) - это структура данных, которая позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию поиска и операцию удаления пары по ключу. Основное отличие таблиц от других динамических множеств – вычисление адреса элемента по значению ключа. Выполнение любой операции (поиск, добавление и удаление) в хэш-таблице начинается с вычисления хэш-функции от ключа. Ситуация, когда для различных ключей получается одно и то же значение хэш-функции, называется коллизией.
Существуют два основных варианта хеш-таблиц: с цепочками и открытой адресацией. Хеш-таблица содержит некоторый массив, элементы которого есть пары (хеш-таблица с открытой адресацией) или списки пар (хеш-таблица с цепочками).
| Задание
| Краткие теоретические сведения
| |
| 1. Пункты 1, 2, 3 содержат программный код проекта, в котором реализована хэш-таблица с открытой адресацией.
В правой части данного пункта записан заголовочный файл Hash.h.
Написать комментарии к программному коду.
| |
#pragma once
#define HASHDEL (void*)-1
struct Object
{ void** Data;
Object(int, int (*)(void*));
int Size;
int N;
int (*GetKey)(void*);
bool Insert(void*);
int SearchInd(int key);
void* Search(int key);
| void* Delete(int key);
bool Delete(void*);
void Scan(void(*f)(void*));
};
static void* DEL=(void*)HASHDEL;
Object Create(int size, int (*getkey)(void*));
#undef HASHDEL
| |
| 2. В правой части данного пункта представлена структура, главная функция проекта и две вспомогательных функции.
Написать комментарии к программе.
| | #include "stdafx.h"
#include "Hash.h"
#include <iostream>
using namespace std;
struct AAA
{ int key; char *mas; AAA(int k,char*z)
{ key=k; mas=z; } AAA() {}
};
int key(void* d)
{ AAA* f = (AAA*)d; return f->key;
}
void AAA_print(void* d)
{ cout<<" ключ "<<((AAA*)d)->key<<" - " <<((AAA*)d)->mas<<endl; }
int _tmain(int argc, _TCHAR* argv[])
{setlocale(LC_ALL, "rus");
AAA a1(1,"one"), a2(2,"two"),
a3(4,"three"), a4 (2,"fo");
int siz=10;
cout<<"Введите размер хэш-таблицы" <<endl; cin>>siz;
Object H=Create(siz,key);//создать
int choise; int k; for(;;)
{cout<<"Меню:"<<endl;
cout<<"1 - вывод хэш-таблицы"<<endl;
cout<<"2 - добавление элемента"<<endl;
| cout<<"3 - удаление элемента"<<endl;
cout<<"4 - поиск элемента"<<endl;
cout<<"0 - выход"<<endl;
cout<<"сделайте выбор"<<endl; cin>>choise;
switch(choise){
case 0: exit(0);
case 1: H.Scan(AAA_print); break;
case 2: {AAA *a = new AAA;
char *str = new char [20];
cout<<"введите ключ"<<endl; cin>>k;
a->key=k; cout<<"введите строку"<<endl;
cin>>str; a->mas=str;
if(H.N == H.Size)
cout<<"Таблица заполнена"<<endl;
else H.Insert(a); } break;
case 3: { cout<<"введите ключ для
удаления"<<endl; cin>>k;
H.Delete(k); } break;
case 4: {cout<<"введите ключ для
поиска"<<endl; cin>>k;
if (H.Search(k)==NULL)
cout<<"Элемент не найден"<<endl;
else AAA_print(H.Search(k)); }
break; } }
return 0; }
| |
| 3. В правой части записан программный модуль Hash.cpp.
Написать комментарии к программному коду.
Сформировать программный код в один проект и выполнить его.
| | #include "stdafx.h"
#include "Hash.h"
#include <iostream>
int HashFunction(int key, int size, int p)//хэш-функция
{ double key2=5*((0.6180339887499*key)-int((0.6180339887499*key)));
return (p+key)%size;
//return ((int)(p+fmod(((key*(sqrt(5.0)-1))/2), 1)))%size;
}
int Next_hash(int hash, int size, int p)
{ return (hash+5*p+3*p*p)%size;
}
Object Create(int size, int(*getkey)(void*))
{ return *(new Object(size,getkey));
}
Object::Object(int size,int(*getkey)(void*))
{ N=0; this->Size = size;
this->GetKey=getkey;
this->Data=new void*[size];
for(int i=0; i<size; ++i)
Data[i]=NULL;
}
bool Object::Insert(void* d)
{ bool b=false;
if(N!=Size)
for(int i=0, t=GetKey(d), j=HashFunction(t, Size, 0);
i!=Size&&!b;
//j=HashFunction(t,Size,++i))
j= Next_hash(j, Size, ++i))
if(Data[j]==NULL||Data[j]==DEL)
{ Data[j]=d; N++; b=true; }
return b;
}
| int Object::SearchInd(int key)
{int t=-1; bool b=false;
if(N!=0)
for(int i=0,j=HashFunction(key,Size,0);
Data[j]!=NULL&&i!=Size&&!b; j=HashFunction(key, Size, ++i))
if(Data[j]!= DEL)
if(GetKey(Data[j])==key)
{ t=j; b=true; }
return t;
}
void* Object::Search(int key)
{ int t=SearchInd(key);
return(t>=0)?(Data[t]):(NULL);
}
void* Object::Delete(int key)
{ int i=SearchInd(key);
void* t=Data[i];
if(t!=NULL)
{Data[i]=DEL; N--;}
return t;
}
bool Object::Delete(void* d)
{ return(Delete(GetKey(d))!=NULL);
}
void Object::Scan(void(*f)(void*))
{for(int i = 0; i < this->Size; i++)
{std::cout<<" Элемент"<<i;
if ((this->Data)[i]==NULL) std::cout<<" пусто"<<std::endl;
else if ((this->Data)[i]==DEL) std::cout<<" удален"<<std::endl;
else f((this->Data)[i]); }
}
| | |
4. Добавить в проект функцию расчета коэффициента заполнения хэш-таблицы (альфа = n/m – число хранимых элементов /размер массива хэш).
Использовать функции при моделировании. Провести исследование построения хэш-таблиц разного размера (например, 16, 32 или 32, 64, 128) с коллизиями. Исследовать время поиска в построенных в соответствии со своим вариантом хэш-таблицах.
| № варианта
| Условие задачи
|
| Варианты с 1по8
| Изменить функцию вычисления хэш для решения коллизии на квадратичную функцию, которая строится на основе формулы: h(key, i) = (h'(key) + с1*i+ c2*i2) mod hashTableSize.
|
| Вариантыс 9по16
| Изменить функцию вычисления хэш на мультипликативную функцию, которая строится на основе формулы: H(key) = [hashTableSize(key*A mod 1)], где key*A mod 1 – дробная часть key*A,
A = (sqrt(5) - 1) / 2 = 0,6180339887499
|
В начало практикума
