Приложение - Динамическое хеширование

>

Цель программы:

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

Задание:

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

Формат ключа

Количество сегментов

Метод хеширования (разрешения коллизий)

AцццAA

2000

Линейное опробование

Где "ц" - это цифра 0...9; "A" - это большая буква латиницы A...Z.

Описание хеш-функции

Хеш-функция основана на возведении суммы кодов символов ключа в квадрат и извлечение из полученного квадрата нескольких средних цифр. При этом коды символов умножаем на частное кода и произведения тройки на порядковый номер символа в ключе (1ч6). Звучит убого, вот так выглядит формула суммы:

Где - код символа с индексом "i";

Возведенная в квадрат сумма колеблется от 7997584 до 22781529, а это семизначное или восьмизначное число. Для адресации сегментов хеш-таблицы необходимо четырехзначное число, не превышающее 2000. Откинем у квадрата суммы 2 первых и два последних разряда, так у нас получится трехзначное или четырехзначное число. Для того, чтобы адрес не превысил максимально допустимый адрес 1999, будем брать остаток от деления на 2000 до тех пор, пока он не попадет в нужный диапазон.

Экспериментальный анализ хеш-функции

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

Формируются случайным образом ключи заданного формата в количестве, превышающем количество сегментов хеш-таблицы в 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 ();

}

Похожие статьи




Приложение - Динамическое хеширование

Предыдущая | Следующая