Приложение - Динамическое хеширование
>
Цель программы:
Целью работы является изучение методов хеширования данных и получение практических навыков реализации хеш-таблиц.
Задание:
Составить хеш-функцию в соответствии с заданным вариантом и проанализировать ее. При необходимости доработать хеш-функцию. Используя полученную хеш-функцию разработать на языке программирования высокого уровня программу, которая должна выполнять следующие функции: создавать хеш-таблицу; добавлять элементы в хеш-таблицу; просматривать хеш-таблицу; искать элементы в хеш-таблице; удалять элементы из хеш-таблицы.
Формат ключа |
Количество сегментов |
Метод хеширования (разрешения коллизий) |
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 ();
}
Похожие статьи
-
Удаление элементов хеш-таблицы - Динамическое хеширование
Многие программисты настолько слепо верят в алгоритмы, что даже не пытаются задумываться над тем, как они работают. Для них неприятным сюрпризом...
-
Разрешение коллизий - Динамическое хеширование
Составление хеш-функции - это не вся работа, которую предстоит выполнить программисту, реализующему поиск на основе хеширования. Кроме этого, необходимо...
-
Расширяемое хеширование (extendible hashing) - Динамическое хеширование
Расширяемое хеширование близко к динамическому. Этот метод также предусматривает изменение размеров блоков по мере роста базы данных, но это...
-
Применение хеширования - Динамическое хеширование
Одно из побочных применений хеширования состоит в том, что оно создает своего рода слепок, "отпечаток пальца" для сообщения, текстовой строки, области...
-
Заключение - Динамическое хеширование
Хеширование, которое родилось еще в середине прошлого века, активно используется в наши дни везде, где требуется произвести быструю выборку данных....
-
Введение - Динамическое хеширование
С хешированием мы сталкиваемся едва ли не на каждом шагу: при работе с браузером (список Web-ссылок), текстовым редактором и переводчиком (словарь),...
-
Описание разработанной структуры Описание структуры данных, используемой в программе, имеет вид: Struct Worker{ Char surname [20]; //фамилия Double...
-
Введение, Теоретические основы - Разработка консольного приложения на языке С++
Данная работа посвящена созданию своего рода базы данных на языке программирования С++. База данных содержит информацию о сотрудниках этого предприятия,...
-
Структура проекта Программа была реализована на языке Java в среде разработки AndroidStudio с помощью инструментов для разработки Android SDK. Разработка...
-
Исходя из того, что в программе необходимо предусмотреть запись базы в файл, вытекает следующее: - у пользователя должна быть возможность изначально...
-
Разработка приложения для базы данных - Разработка Windows-приложений в среде Borland Delphi
Цель Работы: Получить навыки создания приложения для базы данных. Пояснения к работе Для работы с базами в Delphi есть несколько наборов компонент,...
-
Разработка тестового приложения. - Разработка Windows-приложений в среде Borland Delphi
Цель Работы: Закрепить навыки программирования в Delphi. Постановка задачи: Текстовый файл содержит несколько вопросов и 4 варианта ответа, из которых...
-
Организация данных - Разработка программного приложения "Калькулятор коммунальных услуг"
Исходя из анализа предметной области, сделан выбор в пользу реляционной модели данных, формой представления которой является таблица, имеющая строки и...
-
Табличный процессор Excel фирмы Microsoft предназначен для ввода, хранения, обработки и выдачи больших объемов, данных в виде, удобном для анализа и...
-
Без установленных модулей приложение предоставляет следующие модели для работы с данными из базы данных: WorkspacesModel. Предоставляет данные о рабочих...
-
База данных приложения - Многопользовательский проектно-ориентированный планировщик задач
В приложении для постоянного хранилища данных используется SQL база данных, управляемая СУБД MySQL. В базе хранятся данные о рабочих пространствах,...
-
Структура входной информации должна соответствовать структуре данных, определенной на этапе проектирования базы данных, если речь идет о заполнении...
-
Геймификация Когда рестораны принимают решения встраивать инновационные услуги в свой бизнес для привлечения аудитории, следует учитывать не только...
-
На добавление Создадим запрос на добавление для формы "Режиссеры". На вкладке "СОЗДАНИЕ" жмем "Конструктор запросов", тип запроса выбираем "Добавление"....
-
Реализация базы данных - Разработка мобильного приложения расчета и учета оплаты коммунальных услуг
Для создания таблиц базы данных, структура которой представлена на рис. 21 в программе использовались следующие запросы: CREATE TABLE tariffs ( Tariff_id...
-
Совместная работа нескольких приложений - Информационные технологии
Система Windows исходно задумывалась как многозадачная. Это означает, что в ней одновременно могут работать несколько задач. Это действительно так....
-
В ходе разработки было создано пять форм, обеспечивающих взаимодействие между пользователем и приложением: - начальное окно выбора учебного года, курса и...
-
Понятия и особенности обмена данными в MS Windous Обмен данными в данной операционной системе производится очень просто. Этой цели служит буфер обмена...
-
-приложения - Компьютерные сети
CGI (Common Gateway Interface) -- стандарт обмена данными между прикладной программой, выполняемой по запросу пользователя, и HTTP-сервером, который...
-
Проектирование многооконных приложений - Разработка Windows-приложений в среде Borland Delphi
Цель Работы: Получить навыки добавления новых форм к проекту. Пояснения к работе Проект приложения, включающий несколько окон, создается поэтапно. Шаги...
-
Общие требования к разработке графического интерфейса. Под графическим интерфейсом пользователя (Graphical User Interface -- GUI) -- вид...
-
Рассмотрим иерархию компонентов (Рис. 26) и вид интерфейса (Рис. 27) на примере экрана "Информация о пользователе". Экран "Информация о пользователе"...
-
Компьютерный интерфейс аccess программный Цель работы: Разработать приложения для базы данных "Овощной магазин" Входная информация: Готовая база данных,...
-
Введение - Разработка приложения "Кинокомпания"
В общем смысле термин база данных - это совокупность сведения о конкретных объектах реального мира в какой-либо предметной области или разделе предметной...
-
Тестируемый программный продукт является высокопроизводительным приложением, которое предоставляет возможность создания и настройки сетей беспроводного...
-
Таблица 3.9 - Функции: логическая и физическая организация и элементы управления Функция Наименование элемента управления Элемент управления, за которым...
-
Решения по пользовательскому интерфейсу в части серверного приложения (вебсайт) Для реализации требований к серверному приложению (Сайту), объединяющему...
-
Программирование В соответствии со структурной схемой приложения (п.4.1.2), разработаны программные модули на языке Delphi 7. Кроме того разработаны...
-
Возможность использования формул и функций является одним из важнейших свойств программы обработки электронных таблиц. Это, в частности, позволяет...
-
Хранилище данных - Разработка аналитического приложения
Как система управления базами данных (СУБД) был выбран Microsoft SQL Management Studio. Данная СУБД обладает понятным интерфейсом, она проста в...
-
Хранилище данных, Рассмотрение источников данных - Разработка аналитического приложения
Рассмотрение источников данных Данные для работы были взяты с сайта Международного валютного фонда (МВФ). МВФ - это организация, которая состоит из 189...
-
Широкое распространение в операционной системе Windows имеет множество стандартных программ обеспечивающих работу устройств компьютера и служащих для...
-
Общие требования Прежде чем начинать формулировать требования к пользовательскому интерфейсу, было принято решение, что необходимо ознакомиться с...
-
Трансформация данных, Выводы - Разработка аналитического приложения
Процесс трансофрмации в целом соответствует ETL процессу. ETL расшифровывается как "Extract, Transform, Load", что переводится на русский примерно как...
-
Введение. - Приложения технологии системы электронных таблиц Excel к решению задач механики
История развития программ обработки электронных таблиц насчитывает немногим более десяти лет, но налицо значительный прогресс в области разработки такого...
Приложение - Динамическое хеширование