Хеширование - Курсовая работа

С хешированием мы сталкиваемся едва ли не на каждом шагу: при работе с браузером (список Web-ссылок), текстовым редактором и переводчиком (словарь), языками скриптов (Perl, Python, PHP и другие), компилятором (таблица символов). Хеширование есть разбиение множества ключей (однозначно характеризующих элементы хранения и представленных, как правило, в виде текстовых строк или чисел) на непересекающиеся подмножества (наборы элементов), обладающие определенным свойством. Решение обратной задачи возложено на хеш-структуры (хеш-таблицы): по хеш-адресу они обеспечивают быстрый доступ к нужному элементу. В идеале для задач поиска хеш-адрес должен быть уникальным, чтобы за одно обращение получить доступ к элементу, характеризуемому заданным ключом (идеальная хеш-функция).Такие преобразования также называются хеш-функциями или функциями свертки, а их результаты называют хешем, хеш-кодом или сводкой сообщения (message digest). Хеширование применяется для построения ассоциативных массивов, поиска дубликатов в сериях наборов данных, построения достаточно уникальных идентификаторов для наборов данных, контрольного суммирования с целью обнаружения случайных или намеренных ошибок при хранении или передаче, для хранения паролей в системах защиты (в этом случае доступ к области памяти, где находятся пароли, не позволяет восстановить сам пароль), при выработке электронной подписи (на практике часто подписывается не само сообщение, а его хеш-образ).Дональд Кнут относит первую систематическую идею хеширования к сотруднику IBM Хансу Петеру Луну, предложившему хеш-кодирование в январе 1953 года. Думи рассматривал хеширование, как решение «Проблемы словаря», а также предложил использовать в качестве хеш-адреса остаток деления на простое число.Разрешение коллизий в хеш-таблице, задача, решаемая несколькими способами. Можно использовать списки, а можно открытую адресацию (рисунок 1.1).В курсовом проекте поставленной задачей является разработать справочно-информационную (Windows-приложение) систему на языке программирования C# выполняющее следующие функции: 1) чтение из текстового файла информации об объектах класса согласно варианту (таблица 2.1). Предусмотреть наличие в файле не корректных записей, которые в процессе работы программы не будут обрабатываться. Использовать регулярные выражения (предусмотреть проверку по возможности всех полей); Использовать регулярные выражения;Исходными данными задачи являются: 1) название предметной области, а точнее название класса и его основные поля указаны в таблице 2.1, которое выбирается согласно варианту выданному преподавателем; 3) хеш-таблица с использованием подходящей функции хеширования (алгоритм разрешения конфликтов и ключ указаны в таблице 2.2). На основе указанных исходных данных требуется выполнить следующее: 1) создать класс согласно варианту. Класс должен содержать следующие элементы: а) описание полей класса (выделенное жирным курсивов поле оформить как перечисление); в) перегрузку одного из бинарных операторов (указать точно какой выбран самостоятельно бинарный оператор и что реализует);Последовательности индексов, возникающие при зондировании с двойным хешированием, близки к равномерному хешированию. При двойном хешировании хеш-функция имеет вид обычной хеш-функции. Чтобы последовательность зондируемых ячеек охватывала всю таблицу, значение h1(k) должно быть взаимно простым с размером хеш-таблицы m. Простой способ добиться этого условия - выбрать в качестве m степень двойки, а функцию h1(k) взять такую, чтобы она принимала только нечетные значения. Значения этой хеш-функции должны быть ненулевыми и взаимно-простыми с размером хеш-таблицы, что проще всего достичь, взяв простое число в качестве размера, и потребовав, чтобы вспомогательная хеш-функция принимала значения от 1 до N - 1.Класс «Hash_Table» - хеш-таблица, содержит в себе следующие методы: 1) «Add» - метод добавления элемента в хеш-таблицу; 2) «Find» - метод поиска элемента в хеш-таблице, с помощью «Двойного хэширования», по заданному ключу (введенным пользователем в отдельном окне); 5) «Max» - метод, осуществляющий поиск максимального элемента в хеш-таблице по средством операторов отношения и алгоритма организации хеш-таблиц; 6) «Visit» - метод, осуществляющий проверку ячейки с ключом, ячейка находиться с помощью прохешированного ключа (введенного пользователем).Метод «Add» - вызывается при нажатии пунктов меню «Файл - Открыть» и «Функции с данными - Вставка». Сам алгоритм работы данного метода представлен на рисунке 3.1. Рисунок 3.1 - Блок схема метода «Add» Метод «Visit» - осуществляет так сказать обход хеш-таблицы. Данный метод не вызывается посредством меню, а выполняет роль второстепенного метода (подпрограммы) для остальных методов.Программа состоит из двух классов: 1) класс «Hash_Table» - хэш-таблица, элементы класса отображены в таблице 3.1; 2) класс «Hash_Cell» - ячейка хэш-таблицы, элементы описаны в таблице 3.

СОДЕРЖАНИЕ

Введение

1. Хеширование

1.1 Определение хеширования

1.2 История

1.3 Разрешение коллизий

2. Описание задачи и исходных данных

2.1 Постановка задачи

2.2 Описание исходных данных

2.3 Анализ поставленной задачи

3. Описание разработанного Приложения

3.1 Описание программных модулей

3.2 Описание работы методов

3.3 Структура программного продукта

4. Описание интерфейса

Заключение

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

Приложение А Листинг программы