Хеширование данных

ГУАП КАФЕДРА № 43

ОТЧЕТ О ЛАБОРАТОРНОЙ РАБОТЕ ХЕШИРОВАНИЕ ДАННЫХ По дисциплине: СТРУКТУРЫ И АЛГОРИТМЫ ОБРАБОТКИ ДАННЫХ ПРЕПОДАВАТЕЛЬ Матьяш В.А.

РАБОТУ ВЫПОЛНИЛА СТУДЕНТКА ГР. ___4932К___Русанова А.А.

Санкт-Петербург 2011

Цель работы

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

Задание на лабораторную работу

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

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

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

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

где — код символа с индексом «i» ;

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

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

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

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

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

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

#include

#include

#include

#include

using namespace std;

#define b 2000

int h (char*);

int main ()

{

char current_key ={NULL};

int A [b];

int adress=0;

srand ((unsigned) time (0));

for (int i=0; i

A [i] =0;

for (int i=0; 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

os<<

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 % 1 000 000;

h= (int) (sum/100);

do

{

h=h % b;

}

while (h>b);

return h;

}

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

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

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

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

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

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

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

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

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

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

#include

#include

#include

#include

#include

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

{

Tab [i] ="" ;

}

for (;;)

{

system («cls»);

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

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 включительно!" <

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 % 1 000 000;

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<<" Введенные данные некорректны. Введите еще раз: «<

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<<" Введенные данные некорректны. Введите еще раз: «<

break;

}

}

else

{

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

{

correct = false;

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

break;

}

}

if (i==5)

correct=true;

}

}

while (correct==false);

}

void add ()

{

char key ={NULL};

bool correct = true;

system («cls»);

do

{

if (correct==true)

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

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<<" Такое значение уже есть в таблице, введите другое!" <

}

while (correct==false);

adress=h (key);

do

{

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

{

Tab [adress] =key;

break;

}

else

adress+=2;

}

while (adress

if (adress>=b)

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

else

{

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

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

{

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

continue;

if (i==5)

cout<<" «<<

else

cout<<<" «<<

}

cout<<". «<

}

output_in_file ();

system («pause»);

}

void find ()

{

char key ={NULL};

bool correct = true;

int try_count=0;

system («cls»);

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

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

if (flag==false)

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

else

{

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

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

{

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

continue;

if (i==5)

cout<<" «<<

else

cout<<<" «<<

}

cout<<". «<

}

system («pause»);

}

void del ()

{

char key ={NULL};

bool correct = true;

int try_count=0;

system («cls»);

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

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

if (adress>=b)

flag=false;

if (flag==false)

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

else

{

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

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

{

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

continue;

if (i==5)

cout<<" «<<

else

cout<<<" «<<

}

cout<<". «<

}

output_in_file ();

system («pause»);

}

void create_table ()

{

char key ={NULL};

int adress=0;

bool correct=true;

srand ((unsigned) time (0));

for (int i=0; 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

{

ofs<<" «<<

}

ofs. close ();

}