Сущность понятия "хеширование" и его история, функции и свойства алгоритмов хеширования и их применение. Разработка справочно-информационной системы на языке программирования C#, который предоставляет способ организации данных в виде "хеш-таблицы".
Аннотация к работе
С хешированием мы сталкиваемся едва ли не на каждом шагу: при работе с браузером (список 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.