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

Методы хеширования данных и реализация хеш-таблиц. Разработка на языке программирования высокого уровня программы с функциями создания хеш-таблицы, добавления в нее элементов, их просмотра, поиска и удаления. Экспериментальный анализ хеш-функции.

Рубрика Программирование, компьютеры и кибернетика
Вид лабораторная работа
Язык русский
Дата добавления 18.06.2011
Размер файла 231,9 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

ГУАП

КАФЕДРА № 43

ОТЧЕТ О ЛАБОРАТОРНОЙ РАБОТЕ

ХЕШИРОВАНИЕ ДАННЫХ

По дисциплине: СТРУКТУРЫ И АЛГОРИТМЫ ОБРАБОТКИ ДАННЫХ

ПРЕПОДАВАТЕЛЬ Матьяш В.А.

РАБОТУ ВЫПОЛНИЛА

СТУДЕНТКА ГР. ___4932К___Русанова А.А.

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

Цель работы

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

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

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

Формат ключа

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

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

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 ();

}

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


Подобные документы

  • Использование хеширования для поиска данных. Хеширование и хеш-таблицы. Способы разрешения конфликтов. Использование средств языка программирования в работе с хеш-таблицами. Описание разработанного приложения. Структура программы. Инструкция пользователя.

    курсовая работа [1,1 M], добавлен 19.08.2016

  • Понятие таблицы, анализ способов ее формирования и организации, особенности создания доступа по имени. Сущность хеширования данных. Преимущества и недостатки связывания. Применение бинарного (двоичного) поиска и характеристика интерфейса программы.

    курсовая работа [307,6 K], добавлен 16.06.2012

  • Алгоритм работы программы. Анализ предметной области. Структура таблиц БД "Библиотека". Инфологическое и даталогическое проектирование. Запросы для поиска и извлечения только требуемых данных. Формы для просмотра, добавления, изменения данных в таблицах.

    курсовая работа [5,1 M], добавлен 14.06.2014

  • Создание программы, работающей с набором данных на внешнем устройстве. Описание программного комплекса. Обзор структуры главной программы. Процедура добавления новых элементов, поиска и создания на экране вертикального меню. Проверка работы программы.

    курсовая работа [265,6 K], добавлен 28.08.2017

  • Сравнительный анализ языков программирования высокого уровня Си и Паскаль. Реализация алгоритма обработки данных. Тестирование и отладка программы или пакета программ. Структура программы на языке Турбо Паскаль. Указатели и векторные типы данных.

    курсовая работа [233,5 K], добавлен 14.12.2012

  • Основные понятия объектно-ориентированного программирования, особенности описания функций и классов. Разработка программы для работы с универсальной очередью установленного типа, добавления и удаления ее элементов и вывода содержимого очереди на экран.

    курсовая работа [187,2 K], добавлен 27.08.2012

  • Изучение символьных и строковых типов данных, алгоритма задачи на языке программирования Паскаль. Описания получения и установки отдельного символа строки, изменения регистра символов. Анализ создания и просмотра файла, поиска и сортировки информации.

    курсовая работа [440,7 K], добавлен 13.06.2011

  • Хеширование как метод обеспечения быстрого доступа к большим объемам информации. Добавление в хеш-таблицу новой пары. Операции поиска, вставки и удаления по ключу. Практическое применение в теории баз данных, кодировании, банковском деле, криптографии.

    презентация [212,2 K], добавлен 22.10.2013

  • Объектно-ориентированное программирование как новый подход к созданию приложений. Разработка Windows-приложения для поиска информации в хэш-таблице. Анализ использования хеширования для поиска данных и линейного зондирования для разрешения конфликтов.

    курсовая работа [915,5 K], добавлен 06.03.2016

  • Разработка программного продукта - базы данных "Экскурсия" в интегрированной среде программирования C++ Builder 6. Определение порядка просмотра данных базы, их редактирования и удаления. Особенности руководства пользователя и общего интерфейса программы.

    курсовая работа [2,4 M], добавлен 03.11.2013

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.