Программная реализация алгоритма закрытого хэширования

const

n = 200;            {общее количество множеств}

type

Tcollection = set of byte;  {используем множества типа byte}

TsetOfCollect = array[1..n + 1] of Tcollection;

Tused = array[1..n + 1] of boolean;

var

totalEl : byte;     {количество элементов в текущем множестве}

hashTable : TsetOfCollect;

used : Tused;

Программа работает с множествами, состоящими из типа данных byte. Есть массив множеств, состоящий из 201 элемента (200 - принятое количество множеств, но необходимо иметь массив длиной превышающей общее количество анализируемых данных, поэтому я взяла 201, т к удовлетворяем условию 201 > 200).

{заполняем  различными значениями множестов состоящее из countEl элементов}

procedure fillSet(var currColl : Tcollection; countEl : byte);

var

currentValueEl : byte;  {значение текущего одного элемента, текущего множества}

i : byte;

begin

for i := 1 to countEl do

begin

currentValueEl := i;

include(currColl, currentValueEl);

end;

end;

Затем процедурой fillSet заполняю каждое множество элементами, количество которых генерирую при помощи случайных чисел (а сами значения вбиваю от 1 до количества элементов). В хэш-таблице привязываюсь к индексу элемента (индекс равен количеству элементов множества), т е например получила что в текущем множестве 34 элемента -> заполнила его значениями от 1 до 34 и в массив множеств в элемент с индексом 34 записала данное множество. Если вдруг так получилось, что ранее уже было сгенерировано число 34, то двигаюсь вправо (т е к элементу 35) и проверяю, не занято ли эта позиция, если занята, то операция поиска вставки продолжается иначе текущее множество заполняется в массив множеств. Если достигнут конец массива, то начинается поиск вставки с самого первого элемента. Так как количество элементов массива больше общего количества анализируемых множеств, то место для вставки будет обнаружено всегда.

{заполняем  массив имитирующий хеш - таблицу}

procedure fillHashTable(var currColl: Tcollection; index : byte);

var

i : byte;

begin

for i := index to (n + 1) do

begin

if(used[i] = false) then

begin

hashTable[i] := currColl;

used[i] := true;

break;

end;

if(i = (n + 1)) then

begin

i := 1;     {переходим на начало массива}

end;

…

Процедура показывает, как можно произвести поиск множества по заданному количеству элементов этого множества.

var

i : byte;

collection : Tcollection;

begin

clrscr;

for i := 1 to n do

begin

collection := [];       {обнуляем множество}

totalEl := random(255) + 1;

fillSet(collection, totalEl);

fillHashTable(collection, totalEl);

end;

В данном случае хэш-функцией является totalEl := random(255) + 1, так как максимальное количество элементов множества 255.

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

2.2 Руководство  пользователя и результаты тестирования  программы

В соответствии с ГОСТом 19.701-90 руководство пользователя должно содержит следующие разделы:

• общие сведения о программном продукте;
• описание логической структуры;
• описание запуска.

Общие сведения о программном продукте.

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

Описание  логической структуры.

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

Описание  запуска.

Для того чтобы  запустить программу необходимо:

-зайти в каталог, запустить файл с именем «Закрытое хэширование .pas»;

-если открытие программного приложения осуществляется непосредственно через Pascal, нужно нажать комбинацию клавиш Ctrl+F9;

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

Рис. 4. Программная реализация алгоритма закрытого хэширования

В хэш-таблице индекс равен количеству элементов множества, то есть массив заполнил его значениями (for i := 1 to 200) и в массив множеств в элемент с выбранным индексом  записал данное множество.

Тестирование  программы

Тестированием называется процесс выполнения программы с целью обнаружения ошибки, хотя никакое тестирование не может доказать полное отсутствие ошибок в программе (12: 72). Однако тестирование позволяет уменьшить (свести к минимуму) ошибки, допущенные при программировании.

В качестве стратегии тестирования будем использовать модульное тестирование.

Модульное тестирование — процесс в программировании, позволяющий проверить на корректность отдельные модули исходного кода программы.

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

Цель модульного тестирования — изолировать отдельные части программы и показать, что по отдельности эти части работоспособны.

При тестировании данного продукта соблюдались следующие  основные принципы:

• предполагаемые результаты должны быть известны до тестирования;
• необходимо проверять действия программы на неверных данных;
• необходимо проверить работу программы на наличие ошибок;
• необходимо досконально изучать результаты каждого теста.

Ниже в таблице  приведены тесты готового программного продукта по принципу «Модульного тестирования»:

 

Таблица 1

Тестирование  программного приложения

Номер Теста	Назначение  теста	Значения  исходных данных	Ожидаемый результат	Реакция программы	Вывод
1.	Проверить правильность работы процедуры, компоновки множества элементов.	Множество сгенерировано случайным образом.	Построение массива по заданному алгоритму.	Программное приложение генерирует множество, после чего выполняется операция поиска вставки элемента.	Система правильно  осуществляет построение массива.
2.	Проверить правильность работы хэш-функции.	Данные выводятся автоматически на экран монитора.	Вычисление индекса хеширования и вставка значения элемента.	Выстраивается логическая цепь, которая показывает осуществление алгоритма закрытого хэширования. Наличие ошибок отсутствует.	Приложение правильно выполняет заданную операцию. В результате тестирования ошибок не обнаружено.

 

 

 

 

 

 

 

 

ЗАКЛЮЧЕНИЕ

Хеширование, которое  родилось еще в середине прошлого века, активно используется в наши дни везде, где требуется произвести быструю выборку данных. Появились  новые методы хеширования, новые  модификации алгоритмов, написанных ранее. По мнению Дональда Кнута, наиболее важным открытием в области хеширования со времен 70 годов, вероятно, является линейное хеширование Витольда Литвина. Линейное хеширование, которое не имеет ничего общего с классической технологией линейной адресации, позволяет многим хеш-адресам расти и/или выступать в поли вставляемых и удаляемых элементов. Линейное хеширование может также использоваться для огромных баз данных, распределенных между разными узлами в сети.

Разумеется, методы и  сферы применения хеширования не ограничиваются тем, что представлено в этой работе. Основное внимание в данной рабте уделено методу закрытого хеширования. Помимо них можно отметить полиномиальное хеширование (М. Ханан и др., 1963), упорядоченное хеширование (О. Амбль, 1973), линейное хеширование (В. Литвин, 1980). Подробнее о методах хеширования см.

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

Программа предназначена для демонстрации применения алгоритма закрытого хеширования. Язык реализации – Паскаль.

Таким образом, цель курсовой работы была выполнена. Поставленные задачи полностью решены.

 

 

Список использованных источников

1. Абрамов, В.Г. Введение в язык Паскаль / В.Г. Абрамов — М.: Наука, 1998. 232 - с.
2. Бондарев, В.М. Основы программирования / В.М. Бондарев — Ростов н/Д: Феникс, 1999. 327 - с.
3. Вирт, Н. Алгоритмы + структуры данных = программы / Н. Вирт. – М.: Мир, 1995. 238 - с.
4. Гладков, В.П. Задачи по информатике на вступительном экзамене в вуз и их решения: Учебное пособие / В.П. Гладков — Пермь: Перм. техн. ун-т, 1997. 250 - с.
5. Грогоно, П. Программирование на языке Паскаль / П. Грогоно — М.: Мир, 1998. 182 - с.
6. Дагене, В.А. 100 задач по программированию / В.А. Дагене — М.: Просвещение, 1998. - 123 с.
7. Джон, Э. Х. Структуры данных и алгоритмы: Учебное пособие : Пер. с англ., 2000. – 421 с.
8. Епашников, A.M. Программирование в среде Турбо Паскаль / А.М. Епашников — М.: МИФИ, 1998. - 368 с.
9. Ершов, А.П. Избранные труды / А.П. Ершов. – Новосибирск: «Наука», 1994. – 223 с.
10. Зубов, В.С. Программирование на языке Turbo Pascal (версии 6.0 и 7.0) / В.С. Зубов — М.: Информационно-издательский дом «Филинъ», 1999. - 147 с.
11. Йенсен, К. Паскаль — руководство для пользователей и описание языка / К. Йенсен — М.: Мир, 1999. - 384с.
12. Керниган, Б. Практика программирования / Б. Керниган. – СПб.: Невский диалект, 2001. - 243 с.
13. Кнут, Д. Искусство программирования / Д. Кнут. – М.: Вильямс, 2000. – 145 с.
14. Кнут, Д. Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching / Кнут Д. – 2-е изд. — М.: «Вильямс», 2007. — 824 с.
15. Кормен, Т. Алгоритмы: построение и анализ / Т. Кормен. – М.: МЦНМО, 2001. – 185 с.
16. Чмора, А. Современная прикладная криптография / А. Чмора. – М.: Гелиос АРВ, 2001. – 320 с.
17. Шень, А. Программирование: теоремы и задачи. / А. Шень. – М.: МЦНМО, 1995. - 175 с.

 

Приложение1

Техническое задание  на создание программы 

«Реализация алгоритм закрытого хэширования»

1.ВВЕДЕНИЕ

Настоящее техническое  задание распространяется на разработку программы реализующей алгоритм закрытого хэширования.

Программа позволит графически отобразить методы трансформации.

2.ОСНОВАНИЯ ДЛЯ РАЗРАБОТКИ

Программа разрабатывается  на основании темы курсовой работы в соответствии с учебным планом.

3.НАЗНАЧЕНИЕ

Программа предназначена  для наглядного представления реализации алгоритма закрытого хэширования.

4.ТРЕБОВАНИЯ К ПРОГРАММЕ  ИЛИ ПРОГРАММНОМУ ИЗДЕЛИЮ

4.1.Требования к функциональным  характеристикам

4.1.1.Программа должна обеспечить возможность выполнения следующих функций:

• инициализацию модуля
• ввод и вывод текущей информации
• вывод информации

4.1.2.Исходные данные:

• случайные числа

4.1.3.Результат:

• хэш-таблица

4.2.Требования к надежности

4.2.1.Предусмотреть контроль вводимой информации

4.3.Требования к составу   и параметрам технических средств

4.3.1.Система должна  работать на IBMсовместимых персональных компьютерах.

4.3.2.Минимальная конфигурация:

• тип процессора IntelPentium и выше
• видеокарта – 128Мб
• оперативная память – 128 Мб
• место на жестком диске – 5Мб
• монитор
• клавиатура
• тип манипулятора – мышь

4.4. Требования к информационной  и программной совместимости

Система должна работать под управлением семейства операционных систем Win32(WindowsXP/Vista/7)

5. ТРЕБОВАНИЯ К ПРОГРАММНОЙ ДОКУМЕНТАЦИИ

5.1.Разрабатываемые программные  модули должны быть самодокументированы,  т.е. тексты программ должны  содержать все необходимые комментарии.