Отчет по лабе 1

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение

Высшего профессионального образования

Уфимский государственный авиационный технический университет

Кафедра ВМиК

Отчёт

по лабораторной работе

«Построение хеш-таблицы»

31 Вариант

Выполнила: студентка гр. МО-204

Валиева Э.А.

Проверила:

Верхотурова Г.Н.

Уфа-2014

Постановка задачи

Построить хеш - таблицу, содержащую последовательность из m = 54 элементов размерности n = 5. Элементы генерируются с помощью датчика случайных чисел.

Хеш - функция - f(k) = ((k +13) / 31) % t, t – размер хеш-таблицы.

Метод разрешения конфликта - квадратичные пробы.

Переменные, используемые в программе

Входные данные

int n=54; //Количество генерируемых элементов

int n1=81; //Размер хэш-таблицы

long int mas[100]; //Массив генерируемых элементов

Выходные данные

int hash[100]={0}; //Хэш-таблица

int adress; //Хэш-адрес

int i0=1; //Номер пробы

int k1=0; //Коэффициент заполнения таблицы = n/n1

int k2=0; //Общее число проб

Реализация

Шаг 1. Генерируем элементы исходного массива, заданной размерности, с помощью функции генерации уникальных случайных чисел.

int flag=0;

int tmp=0;

int k=0;

srand((unsigned)time(&t));

while (k<n) {

flag=0;

tmp=(100000*(1+rand()%9))+(10000*(1+rand()%9))+(1000+rand()%8999);

for (int i=0; i<k; i++) {

if (mas[i]==tmp) {

flag=1;

break;

}

}

if (flag==0) {

mas[k]=tmp;

++k;

}

}

cout<<"Генерация неповторяющихся чисел: "<<endl;

for (int i=0; i<n; i++)

cout<<setw(2)<<i<<setw(7)<<mas[i]<<" ";

cout<<endl;

cout<<endl;

Шаг 2. Найдём ключ (номер ячейки в хеш-таблице) каждого элемента исходной матрицы, вычислив для него хеш-функции. Размещаем элемнты в хеш-таблице в соответствующей ключу позиции. В случае коллизии применяем метод квадратичных проб. Одновременно подсчитываем количество заполненных ячеек хеш-таблицы и общее число проб для следующего шага.

cout<<"Хэш-таблица: "<<endl;

for (int ht=0; ht<n; ht++) {

adress=((mas[ht]+13)/31)%n1;

k2++;

int adress0=adress;

if (hash[adress]==0) { //Если есть свободная ячейка

hash[adress]=mas[ht];

k1++;

}

else {

while (hash[adress]!=NULL) {

adress=(adress0+i0*i0)%n1;

i0++;

k2++;

}

hash[adress]=mas[ht];

}

i0=1;

}

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

for (int ht=0; ht<n1; ht++)

cout<<setw(2)<<ht<<setw(7)<<hash[ht]<<" ";

cout<<endl;

cout<<"Коэффициент заполнения таблицы: "<<double(n)/double(n1)<<endl;

cout<<"Среднее число проб:"<<double(k2)/double(n)<<endl;

getch();

return 0;

}

Шаг 4. В результате работы программы получим следующий результат:

Формулы расчёта требуемых параметров хеш-таблицы

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

n1= (1.5 * n) - размер хеш-таблицы, где n количество размещаемых элементов;

k1 = K_{занятые} / К _общие - коэффициент заполнения таблицы равен отношению занятых ячеек хеш-таблицы ко всем ячейкам;

k2= P_общ / n – среднее количество проб, требуемых для размещения одного элемента, где P_общ – общее количество проб.

Вывод

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