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

АВТОНОМНАЯ НЕКОММЕРЧЕСКАЯ ПРОФЕССИОНАЛЬНАЯ ОБРАЗОВАТЕЛЬНАЯ ОРГАНИЗАЦИЯ

«КОЛЛЕДЖ ВОРОНЕЖСКОГО ИНСТИТУТА ВЫСОКИХ ТЕХНОЛОГИЙ»

Специальность: Программирование в компьютерных системах

Форма обучения: очная

КУРСОВАЯ РАБОТА

На тему: Методы поиска. Хеширование

по дисциплине «Основы программирования»

Выполнил (а) Чопикян Гегам Гарикович

Группа ПКС-019

Руководитель Яицкая Елена Владимировна



Оглавление

хэширование алгоритм программный обеспечение

Введение

1.1 Где мы сталкиваемся с хешированием

1.2 Что такое хеш-функции

1.3 Открытое хеширование

1.4 Алгоритмы построения и поиска хэш таблицы

1.5 Динамическое хеширование

1.6 Удаление элементов хеш-таблицы

Список литературы



Введение

Курсовое проектирование по дисциплине «Основы программирования» представляет собой заключительный этап изучения основ языка программирования C++. В рамках данного курса дисциплины ставится целью развитие практических навыков программирования задач на ЭВМ.

Задачами курсового проектирования являются:

· овладение навыками разработки программного обеспечения (ПО);

· приобретение навыков построения блок-схем, описания алгоритмов;

· выполнение непосредственно разработки ПО на языке программирования;

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

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



1.1 Где мы сталкиваемся с хешированием

С хешированием мы сталкиваемся едва ли не на каждом шагу: при работе с браузером (список Web-ссылок), текстовым редактором и переводчиком (словарь), языками скриптов (Perl, Python, PHP и др.), компилятором (таблица символов). По словам Брайана Кернигана, это «одно из величайших изобретений информатики». Заглядывая в адресную книгу, энциклопедию, алфавитный указатель, мы даже не задумываемся, что упорядочение по алфавиту является не чем иным, как хешированием. Хеширование есть разбиение множества ключей (однозначно характеризующих элементы хранения и представленных, как правило, в виде текстовых строк или чисел) на непересекающиеся подмножества (наборы элементов), обладающие определенным свойством. Это свойство описывается функцией хеширования, или хеш-функцией, и называется хеш-адресом. Решение обратной задачи возложено на хеш-структуры (хеш-таблицы): по хеш-адресу они обеспечивают быстрый доступ к нужному элементу. В идеале для задач поиска хеш-адрес должен быть уникальным, чтобы за одно обращение получить доступ к элементу, характеризуемому заданным ключом (идеальная хеш-функция). Однако, на практике идеал приходится заменять компромиссом и исходить из того, что получающиеся наборы с одинаковым хеш-адресом содержат более одного элемента. Термин «хеширование» (hashing) в печатных работах по программированию появился сравнительно недавно 1967 г, хотя сам механизм был известен и ранее. Глагол «hash» в английском языке означает «рубить, крошить». Для русского языка академиком А.П. Ершовым был предложен достаточно удачный эквивалент -- «расстановка», созвучный с родственными понятиями комбинаторики, такими как «подстановка» и «перестановка». Однако он не прижился. Как отмечает Дональд Кнут, идея хеширования впервые была высказана Г.П. Ланом при создании внутреннего меморандума IBM в январе 1953 г. с предложением использовать для разрешения коллизий хеш-адресов метод цепочек. Примерно в это же время другой сотрудник IBM - Жини Амдал - высказала идею использования открытую линейную адресацию. В открытой печати хеширование впервые было описано Арнольдом Думи (1956), указавшим, что в качестве хеш-адреса удобно использовать остаток от деления на простое число. А. Думи описывал метод цепочек для разрешения коллизий, но не говорил об открытой адресации. Подход к хешированию, отличный от метода цепочек, был предложен А.П. Ершовым 1957 г., который разработал и описал метод линейной открытой адресации. Среди других исследований можно отметить работу Петерсона 1957г. В ней реализовывался класс методов с открытой адресацией при работе с большими файлами. Петерсон определил открытую адресацию в общем случае, проанализировал характеристики равномерного хеширования, глубоко изучил статистику использования линейной адресации на различных задачах. В 1963 г. Вернер Букхольц опубликовал наиболее основательное исследование хеш-функций. К концу шестидесятых годов прошлого века линейная адресация была единственным типом схемы открытой адресации, описанной в литературе, хотя несколькими исследователями независимо была разработана другая схема, основанная на неоднократном случайном применении независимых хеш-функции. В течение нескольких последующих лет хеширование стало широко использоваться, хотя не было опубликовано никаких новых работ. Затем Роберт Моррис произвел обширный обзор по хешированию и ввел термин «рассеянная память» (scatter storage). Эта работа привела к созданию открытой адресации с двойным хешированием. Далее будут рассмотрены основные виды хеш-функций и некоторые их модификации, методы разрешения коллизий, проблемы удаления элементов из хеш-таблицы, а также некоторые варианты применения хеширования.



1.2 Что такое хеш-функции

Хеш-функция - это некоторая функция h(K), которая берет некий ключ K и возвращает адрес, по которому производится поиск в хеш-таблице, чтобы получить информацию, связанную с K. Например, K - это номер телефона абонента, а искомая информация - его имя. Функция в данном случае нам точно скажет, по какому адресу найти искомое. Пример с телефонным справочником иллюстрируется демонстрационной программой на прилагаемом компакт-диске. Коллизия - это ситуация, когда h(K1) = h(K2), в то время как K1 ? K2. В этом случае, очевидно, необходимо найти новое место для хранения данных. Очевидно, что количество коллизий необходимо минимизировать. Хорошая хеш-функция должна удовлетворять двум требованиям:

· ее вычисление должно выполняться очень быстро;

· она должна минимизировать число коллизий.

Итак, первое свойство хорошей хеш-функции зависит от компьютера, а второе - от данных. Если бы все данные были случайными, то хеш-функции были бы очень простые (несколько битов ключа, например). Однако на практике случайные данные встречаются крайне редко, и приходится создавать функцию, которая зависела бы от всего ключа. Теоретически невозможно определить хеш-функцию так, чтобы она создавала случайные данные из реальных неслучайных файлов. Однако на практике реально создать достаточно хорошую имитацию с помощью простых арифметических действий. Более того, зачастую можно использовать особенности данных для создания хеш-функций с минимальным числом коллизий (меньшим, чем при истинно случайных данных). Возможно, одним из самых очевидных и простых способов хеширования является метод середины квадрата, когда ключ возводится в квадрат и берется несколько цифр в середине. Здесь и далее предполагается, что ключ сначала приводится к целому числу, для совершения с ним арифметических операций. Однако такой способ хорошо работает до момента, когда нет большого количества нолей слева или справа. Многочисленные тесты показали хорошую работу двух основных типов хеширования, один из которых основан на делении, а другой на умножении. Впрочем, это не единственные методы, которые существуют, более того, они не всегда являются оптимальными.

Метод деления

Метод деления весьма прост - используется остаток от деления на M:

h(K) = K mod M

Метод умножения (мультипликативный)

Для мультипликативного хеширования используется следующая формула:

h(K) = [M * ((C * K) mod 1)]

1.3 Открытое хеширование

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



индекс	ключ	указатели
1	ai h(ai)=1	aj, h(aj)=1 at, h(at)=1 af, h(af)=1 начало конец
2		nil nil
3	as h(as)=3	nil nil
4	ak h(ak)=4	ar, h(ar)=4 начало конец
…	…
m		nil nil

Рис 1



1.4 Алгоритмы построения и поиска хэш таблицы

Построение:

· Находим значение хэш функции и по этому значению входим в таблицу

· Если она пустая, то записываем в нее ключ

· Если она занятая, то сравниваем ключ с заданным ключом:

· если ключи совпадают, то обрабатываем повторный ключ

· иначе добавляем новый ключ в конец списка

Поиск:

· Находим значение хэш функции для искомого ключа и этому значению входим в таблицу

· Если ячейка пустая, то поиск заканчивается неудачей

· Если она не пустая, то выполняем сравнение ключей:

· Если ключи совпадают, то поиск заканчивается за одно сравнение

· Иначе организуем просмотр вспомогательного списка с положительным или отрицательным результатом.

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

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

1.5 Динамическое хеширование

Описанные выше методы хеширования являются статическими, т.е. сначала выделяется некая хеш-таблица, под ее размер подбираются константы для хеш-функции. К сожалению, это не подходит для задач, в которых размер базы данных меняется часто и значительно. По мере роста базы данных можно пользоваться изначальной хеш-функцией, теряя производительность из-за роста коллизий; выбрать хеш-функцию «с запасом», что повлечет неоправданные потери дискового пространства; периодически менять функцию, пересчитывать все адреса. Это отнимает очень много ресурсов и выводит из строя базу на некоторое время. Существует техника, позволяющая динамически менять размер хеш-структуры. Это - динамическое хеширование. Хеш-функция генерирует так называемый псевдоключ (“pseudokey”), который используется лишь частично для доступа к элементу. Другими словами, генерируется достаточно длинная битовая последовательность, которая должна быть достаточна для адресации всех потенциально возможных элементов. В то время, как при статическом хешировании потребовалась бы очень большая таблица (которая обычно хранится в оперативной памяти для ускорения доступа), здесь размер занятой памяти прямо пропорционален количеству элементов в базе данных. Каждая запись в таблице хранится не отдельно, а в каком-то блоке (“bucket”). Эти блоки совпадают с физическими блоками на устройстве хранения данных. Если в блоке нет больше места, чтобы вместить запись, то блок делится на два, а на его место ставится указатель на два новых блока.

Задача состоит в том, чтобы построить бинарное дерево, на концах ветвей которого были бы указатели на блоки, а навигация осуществлялась бы на основе псевдоключа. Узлы дерева могут быть двух видов: узлы, которые показывают на другие узлы или узлы, которые показывают на блоки. Например, пусть узел имеет такой вид, если он показывает на блок (рис 1).



Zero	Null
Bucket	Указатель
One	Null

Рис 1

Если же он будет показывать на два других узла, то он будет иметь такой вид (рис 2 )

Zero	Адрес a
Bucket	Null
One	Адрес b

Рис 2

1.6 Удаление элементов хеш-таблицы

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

Рассмотрим алгоритм удаления элемента i при линейной адресации.

Пометить TABLE[i] как пустую ячейку и установить j = i

i = i - 1 или i = i + M, если i стало отрицательным

Если TABLE[i] пуст, алгоритм завершается, т.к. нет больше элементов, о доступе к которым следует заботиться. В противном случае мы устанавливаем r = h(KEY[i]), где KEY[i] - ключ, который хранится в TABLE[i]. Это нам даст его первоначальный хеш-адрес. Если i ? r < j или если r < j < i либо j < i ? r (другими словами, если r циклически лежит между этими двумя переменным, что говорит о том, что этот элемент находится в цепочке, звено которой мы удалили выше).

Надо переместить запись TABLE[j] = TABLE[i] и вернуться на первый шаг.

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

Программа

/*При запуске программа должна отображать несортированный масив случайного размера со случайными целыми числами.

1. Затем, функция линейного поиска с барьером, будет искать случайное число внутри несортированного массива.

2. Массив будет отсортирован в новый массив, с использованием метода хеширования, с последующим поиском случайного числа.*/

// v1 = rand ()% 100; // v1 в диапазоне от 0 до 99

// v2 = rand ()% 100 + 1; // v2 в диапазоне от 1 до 100

// v3 = rand ()% 30 + 1985; // v3 в диапазоне 1985-2014

// v4 = rand ()% 1001 + 101; // v3 в диапазоне 1985-2014

#include <iostream>

#include <stdlib.h> /* srand, rand */

#include <time.h> /* time */

using namespace std;

//Объявляем пустой массив, который будет содержать случайные числа

int firstArray [1000];

int hashFunctionArray [1000];

int main ()

{

setlocale(LC_ALL, "Russian"); //Русский язык в консоли

int randArrayInt, randArrayLength, randSearchItem, pos, j, randArrayRealLength;

srand (time(nullptr));

//randArrayLength = rand() % 900 + 100;

//Генерируем случайное целое число от 100 до 1000

randArrayLength = rand() % 10 + 1; //Случайное число в диапазоне 1-10 для тестов

randArrayRealLength = randArrayLength - 1;

randSearchItem = rand() % 10 + 1; //randSearchItem = rand() % 900 + 100;

cout << "Массив будет содержать " << randArrayLength << " целые числа. \n" << endl;

cout << "randArrayRealLength " << randArrayRealLength << endl << "\n";

//Создаем цикл for для генерации случайных чисел и отправки их в массив

int i;

cout << "[ ";

for (i = 0; i < randArrayRealLength; i++)

{

//randArrayInt = rand() % 900 + 100;

randArrayInt = rand() % 10 + 1; //Генерируем случайное число для массива

firstArray[i] = randArrayInt; //Вставляем в позицию массива сгенерированное случайное число

cout << firstArray[i] << ", "; //Печатаем элемент массива в текущей позиции цикла

}

firstArray[randArrayLength] = randSearchItem; //Вставляем доступный для поиска номер в конец массива

cout << firstArray[randArrayLength] << ", "; //Печатаем доступное для поиска число как последний элемент массива

cout << "]\n" << endl;

cout << "Это случайный ключ для поиска в массиве: Это рандомный ключ " << randSearchItem << endl;

j = 0;

while (firstArray[j] != randSearchItem) {

j++;

}

pos = j + 1;

if (j == randArrayLength)

cout << "Номер не найден" << endl;

else

cout << randSearchItem << " найдено в позиции "<< pos << endl;

cout << endl << "\n";

//Цикл по первому массиву для его отображения

cout << "Первый массив" << endl;

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

{

cout << firstArray[i] << " ";

}

cout << endl << "\n";

//Цикл по массиву хеш-таблицы для его отображения

cout << "Отображение операций по модулю" << endl << endl;

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

{

cout << firstArray[i] << " Модуль " << randArrayRealLength << " Равно ";

hashFunctionArray[i] = firstArray[i] % randArrayRealLength;

cout << hashFunctionArray[i] << endl << "\n";

}

cout << "Массив с хеш-ключами" << endl << endl;

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

{

hashFunctionArray[i] = firstArray[i] % randArrayRealLength;

cout << hashFunctionArray[i] << " ";

}

return 0;

}

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

1. Затем, функция линейного поиска с барьером, будет искать случайное число внутри несортированного массива.

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



Блок Схема



Список литературы

1. Терехов А.Н. Технология программирования: Уч. пособ./ А.Н. Терехов. М.: Интернет-университет информационных технологий. 2007. 148 с. Рекомендовано УМО

2. Лабораторный практикум по технологии программирования: Учебное пособие /А.Ф. Рогачев и др. Воронеж: Научная книга. 2008. 188 с. Рекомендовано УМО

3. Павловская Т.А. С/С++. Программирование на языке высокого уровня. СПб.: Питер, 2002. 464 с. Рекомендовано УМО.

4. Смирнов, А.А. Технологии программирования [Электронный ресурс]: учебное пособие/ Смирнов А.А., Хрипков Д.В. Электрон. текстовые данные. М.: Евразийский открытый институт, 2011. 191 c.

5. Гаспариан, М.С. Информационные системы и технологии [Электронный ресурс]: учебное пособие/ Гаспариан М.С., Лихачева Г.Н. Электрон. текстовые данные. М.: Евразийский открытый институт, 2011. 370 c. Рекомендовано УМО

6. Брауде Э. Технология разработки программного обеспечения / Э. Брауде. СПб.: Питер, 2004. 655 с.

7. Вирт Н. Алгоритмы и структуры данных / Н. Вирт. 2-е изд. СПб.: Невский диалект, 2001. 352 с.

8. Кнут Д., Искусство программирования для ЭВМ. В 3 т. Т. 1. Основные алгоритмы / Д. Кнут. 2-е изд. М.: ИД “Вильямс”, 2002. 720 с.

9. Кнут Д., Искусство программирования для ЭВМ. В 3 т. Т. 2. Получисленные алгоритмы / Д. Кнут. 3-е изд. М.: ИД “Вильямс”, 2003. 832 с.

10. Кнут Д., Искусство программирования для ЭВМ. В 3 т. Т. 3. Сортировка и поиск / Д. Кнут. 2-е изд. М.: ИД “Вильямс”, 2001. 832 с.

11. Технология программирования: Учебное пособие/ А.Ф. Рогачев, С.А. Сазонова, А.В. Лемешкин; АНОО ВИВТ, РосНОУ. Воронеж: Научная книга. 2007. 207 с.

12. Сербулов Ю.С, Павлов И.О., Лемешкин А.В. Объектно-ориентированное программирование: Учебное пособие. Воронеж: Научная книга, 2005. 80 с.

13. Аляев Ю.А., Козлов О.А. Алгоритмы и языки программирования Pascal, C++, Visual Basic Учебно справочное пособие, М.: Финансы и статистика, 2004. 320 с.

14. Правила подготовки и защиты курсовой работы (проекта) / Преображенский Ю.П., Зеленина А.Н., Малышева Е.В., Бережная Т.В. // Методические указания, ВИВТ, 2013. 36 с.

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

...