Экспериментальное исследование проводится следующим образом:

формируются случайным образом ключи заданного формата в количестве, превышающем количество сегментов хеш-таблицы в 2…3 раза;

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

Реализация программы на языке С++ для формирования экспериментальных данных:

#include<iostream>

#include<fstream>

#include<string>

#include<ctime>

using namespace std;

#define b 2000

int h (char*);

int main ()

{

char current_key [7] ={NULL};

int A [b];

int adress=0;

srand ( (unsigned) time (0));

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

A [i] =0;

for (int i=0; i<b*3; i++)

{

for (int j=0; j<6; j++)

{

if ( (j>0) && (j<4))

current_key [j] = (char) (rand () %10+48);

else

current_key [j] = (char) (rand () %26+65);

}

adress=h (current_key);

A [adress] ++;

}

ofstream os ("result. txt");

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

os<<A [i] <<endl;

os. close ();

return 0;

}

int h (char current_key [6])

{

int h=0,sum=0;

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

sum+= (int) ( ( ( (int) current_key [i]) / (3* (i+1)))) * (int) current_key [i];

sum*=sum*2;

sum=sum % 1000000;

h= (int) (sum/100);

do

{

h=h % b;

}

while (h>b);

return h;

}

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

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

Ниже приведена программа, реализующая следующие режимы:

хеширование таблица функция программирование

1. Рандомное генерирование хеш-таблицы на основе заданной хеш-функции

(таблица нарочно сгенерирована так, чтобы оставались промежутки: это даст возможность добавлять в таблицу данные. Таблица сохраняются в файле Table. txt)

2. Добавление элементов

3. Поиск элементов

4. Удаление элементов

Листинг программы

#include<iostream>

#include<fstream>

#include<string>

#include<windows. h>

#include<ctime>

using namespace std;

#define b 2000

string Tab [b];

int adress=0;

int h (char [7]);

void input (char [7]);

void add ();

void find ();

void del ();

void create_table ();

void output_in_file ();

int main ()

{

SetConsoleCP (1251);

SetConsoleOutputCP (1251);

string smth;

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

{

Tab [i] ="";

}

for (;;)

{

system ("cls");

cout<<"МЕНЮ"<<endl<<endl<<"1. Рандомное генерирование хеш-таблицы"<<endl<<"2. Добавление элемента"<<endl<<"3. Поиск элемента"<<endl<<"4. Удаление элемента"<<endl<<"5. Выход из программы"<<endl;

cin>>smth;

if (smth=="1")

create_table ();

else

{

if (smth=="2")

add ();

else

{

if (smth=="3")

find ();

else

{

if (smth=="4")

del ();

else

{

if (smth=="5")

exit (0);

else

{

cout<<"Вводить нужно цифру от 1 до 5 включительно!"<<endl;

system ("pause");

}

}

}

}

}

}

return 0;

}

int h (char key [7])

{

int h=0,sum=0;

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

sum+= (int) ( ( ( (int) key [i]) / (3* (i+1)))) * (int) key [i];

sum*=sum*2;

sum=sum % 1000000;

h= (int) (sum/100);

do

{

h=h % b;

}

while (h>b-1);

return h;

}

void input (char key [7])

{

bool correct=true;

char smth [256];

do

{

cin>>smth;

if (smth [6]! =NULL)

{

correct=false;

cout<<"Введенные данные некорректны. Введите еще раз: "<<endl;

continue;

}

else

{

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

key [i] =smth [i];

}

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

{

if ( (i>0) && (i<4))

{

if ( ( (int) key [i] <48) || ( (int) key [i] >57))

{

correct = false;

cout<<"Введенные данные некорректны. Введите еще раз: "<<endl;

break;

}

}

else

{

if ( ( (int) key [i] <65) || ( (int) key [i] >90))

{

correct = false;

cout<<"Введенные данные некорректны. Введите еще раз: "<<endl;

break;

}

}

if (i==5)

correct=true;

}

}

while (correct==false);

}

void add ()

{

char key [7] ={NULL};

bool correct = true;

system ("cls");

do

{

if (correct==true)

cout<<"Введите абракадабру формата "AцццAA", где"<<endl<<""ц" - это цифра 0…9; "<<endl<<""A" - это большая буква латиницы A…Z. "<<endl;

input (key);

adress=h (key);

correct=true;

while ( (Tab [adress]! ="") && (correct==true))

{

if (Tab [adress] ==key)

correct=false;

else

adress+=2;

}

if (correct==false)

cout<<"Такое значение уже есть в таблице, введите другое!"<<endl;

}

while (correct==false);

adress=h (key);

do

{

if ( (Tab [adress] =="") || (Tab [adress] =="deleted"))

{

Tab [adress] =key;

break;

}

else

adress+=2;

}

while (adress<b-1);

if (adress>=b)

cout<<"очень жаль, но данные в таблицу добавить нельзя по одной из двух причин: "<<endl<<"1. (маловероятно) Таблица переполнена"<<endl<<"2. Разработчик программы непроходимый тупица, запутавшийся в необьятном адресном пространстве"<<endl;

else

{

cout<<"Данные добавлены в таблицу"<<endl<<endl<<". "<<endl;

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

{

if (adress- (5-i) <0)

continue;

if (i==5)

cout<<endl<<adress<<" "<<Tab [adress] <<endl<<endl;

else

cout<<adress- (5-i) <<" "<<Tab [adress- (5-i)] <<endl;

}

cout<<". "<<endl<<endl;

}

output_in_file ();

system ("pause");

}

void find ()

{

char key [7] ={NULL};

bool correct = true;

int try_count=0;

system ("cls");

cout<<"Введите абракадабру формата "AцццAA", где"<<endl<<""ц" - это цифра 0…9; "<<endl<<""A" - это большая буква латиницы A…Z. "<<endl;

input (key);

adress=h (key);

bool flag=false;

do

{

if (Tab [adress] ==key)

{

flag=true;

break;

}

else

{

if (Tab [adress] =="")

break;

else

adress+=2;

}

}

while (adress<b-1);

if (flag==false)

cout<<"Элемент не найден"<<endl;

else

{

cout<<"Элемент найден!"<<endl<<endl<<". "<<endl;

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

{

if (adress- (5-i) <0)

continue;

if (i==5)

cout<<endl<<adress<<" "<<Tab [adress] <<endl<<endl;

else

cout<<adress- (5-i) <<" "<<Tab [adress- (5-i)] <<endl;

}

cout<<". "<<endl<<endl;

}

system ("pause");

}

void del ()

{

char key [7] ={NULL};

bool correct = true;

int try_count=0;

system ("cls");

cout<<"Введите абракадабру формата "AцццAA", где"<<endl<<""ц" - это цифра 0…9; "<<endl<<""A" - это большая буква латиницы A…Z. "<<endl;

input (key);

adress=h (key);

bool flag=true;

do

{

if (Tab [adress] ==key)

{

Tab [adress] ="deleted";

break;

}

else

{

if (Tab [adress] =="")

{

flag=false;

break;

}

else

adress+=2;

}

}

while (adress<b-1);

if (adress>=b)

flag=false;

if (flag==false)

cout<<"Элемент не найден"<<endl;

else

{

cout<<"Элемент удален!"<<endl<<endl<<". "<<endl;

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

{

if (adress- (5-i) <0)

continue;

if (i==5)

cout<<endl<<adress<<" "<<Tab [adress] <<endl<<endl;

else

cout<<adress- (5-i) <<" "<<Tab [adress- (5-i)] <<endl;

}

cout<<". "<<endl<<endl;

}

output_in_file ();

system ("pause");

}

void create_table ()

{

char key [7] ={NULL};

int adress=0;

bool correct=true;

srand ( (unsigned) time (0));

for (int i=0; i<b-100; i++)

{

for (int j=0; j<6; j++)

{

if ( (j>0) && (j<4))

key [j] = (char) (rand () %10+48);

else

key [j] = (char) (rand () %26+65);

}

adress=h (key);

if ( (Tab [adress] =="") || (Tab [adress] =="deleted"))

Tab [adress] =key;

else

continue;

}

output_in_file ();

}

void output_in_file ()

{

ofstream ofs ("Table. txt");

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

{

ofs<<i<<" "<<Tab [i] <<endl;

}

ofs. close ();

}

Размещено на Allbest.ru