-приложению, среди которых: расширяемость, универсальность и легкость применения, модульность, совместимость, устойчивость и защищенность.
В результате разработано программное средство, полностью удовлетворяющее этим требованиям.
Областью возможного практического применения являются базы данных, различные справочники, в защите информации, текстовые редакторы.
Содержание
Введение
1. Методы разработки программных комплексов
.1 Структура программы и языков программирования
.2 Классификация языков программирования
.3 Объектно-ориентированное программирование
2. Использование хеширования для поиска информации
2.1 Таблицы с прямой адресацией
2.2 Хеш-функции
2.3 Открытая адресация
.4 Алгоритмы работы с хеш-таблицей
.5 Постановка задачи
.6 Исходные данные
. Описание разработанного приложения
.1 Структура программного комплекса
.2 Инструкция пользователя
Заключение
Список использованных источников
Приложение А. Текст программы класса Kafedra.cs
Приложение Б. Текст программы класса Lecturer.cs
Приложение В. Текст программы класса HashTable.cs
Приложение Г. Руководство программиста
Приложение Е. Руководство пользователя
Приложение Ж. Схема классов
Введение
Каждый человек хранит какую-либо интересующую его информацию либо в виде записей на бумажных носителях, либо в электронном виде. Объемы хранимой информации у каждого свои.
В настоящее время остро стоит вопрос об удобном хранении информации, с целью быстрого получения доступа к определенным данным. Информация может храниться как на локальном компьютере, так и в сети интернет. В приложениях, работающих с хранилищами информации, используются схожие алгоритмы поиска.
Множество компаний различного масштаба держат всю информацию в виде документов или в таблицах баз данных. Это может использоваться в процессе работы риэлтерских контор, университетах, школах, почтовых отделений и др. Например, директору школы требуется быстрый поиск информации о преподавателях, работающих в его школе. Поэтому быстрый поиск очень важен.
Как правило, компании работают с большим количеством информации. Это могут быть и планы мероприятий, и прайсы, и списки услуг. К примеру, в прайсах интернет-магазина записано много товаров, и, чтобы найти нужный, продавец может отсортировать их по имени и найти вручную, что на практике довольно долго. Именно для этого создаются удобные приложения для организации и работы с подобного типа данными.
Для организации информации в приложениях широко используются такие структуры данных, как: хеш-таблицы, бинарные, красно-черные деревья поиска. Данные методы намного быстрее всем известного последовательного перебора.
В данной работе речь идет о хешировании и его применении при работе с большими объемами данных.
Целью работы являлось создание Windows-приложения на языке C# для удобства в работе различных университетах, что позволило бы быстро осуществлять поиск информации о нужном преподавателе и, при необходимости, вносить определенные изменения.
В процессе выполнения работы решаются следующие задачи:
изучение методов разработки программных комплексов;
изучение алгоритмов хеширования;
разработка Windows-приложения на языке С#.
1. Методы разработки программных комплексов
.1 Структура программы и языков программирования
Изучение программирования нельзя начать не ответив на ряд вопросов: что же такое программа, алгоритм, данные, язык программирования. В этом списке основным термином является алгоритм, который, как и большинство понятий общего вида, имеет множество определений. Например:
"Алгоритм - это конечный набор правил, который определяет последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: конечность, определённость, ввод, вывод, эффективность". (Д.Э. Кнут)
"Алгоритм - это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату". (А. Марков).
В самых общих чертах алгоритм - это однозначное описание порядка (последовательности) выполнения действий из заданного набора, позволяющее получить требуемый результат за конечное число шагов. Можно сказать, что компьютерная программа - это один из способов реализации понятия алгоритма, а язык программирования - средство описания алгоритмов. Однако в определении алгоритма не говорится, над чем производятся действия, выполняемые в нем. В принципе, это могут быть управляемые объекты внешней среды, но тогда они тоже входят в состав понятия алгоритм.
Компьютерная программа, в отличие от абстрактного алгоритма, имеет собственные элементы, над которыми она совершает действия, и которые являются ее составной частью. Это - данные. Таким образом, она представляет собой замкнутую систему, отделенную от внешней среды. Посмотрим, из каких еще частей состоит компьютерная программа. Все они должны выражаться в соответствующих компонентах языка программирования:
−прежде всего, программа работает не с пользователем, а с данными. Эта первая и основная компонента программы - предметы (объекты), над которыми реализуется алгоритм. Данные состоят из отдельных переменных, связанных как между собой непосредственно (через указатели), так и косвенно (как входные данные - результат);
−в языке программирования имеются средства описания данных, которые позволяют программисту конструировать различные формы их представления - типы данных;
−программа базируется на наборе операций (системе команд), которые можно выполнять над данными. В этот набор входят арифметические операции, присваивание (сохранение результата в переменной), ввод-вывод, проверка значения переменной и т.п.;
−как уже отмечалось, программа работает исключительно с данными, что и определяет сущность алгоритма. В наборе операций имеются команды ввода-вывода, осуществляющие обмен данными между переменными и внешней средой (посредством устройств ввода-вывода). С "программно-эгоцентрической" точки зрения это выглядит чистой формальностью и не является существенной частью программы;
Любая программа выполняется в компьютере. Посмотрим, как соотносятся между собой компоненты программы и компьютерной архитектуры:
−компоненты программы находятся в памяти. В принципе, память является общей для них всех, но логически она разделяется на области, именуемые сегментами. Прежде всего, это сегмент данных, содержащий, естественно, данные программы. Алгоритмическая компонента (выражения, операторы) также находится в памяти в собственном сегменте команд;
−одновременное нахождение в памяти "алгоритма" и данных соответствует принципу хранимой программы. Перед загрузкой в память эти же компоненты находятся в программном файле, который представляет собой точную копию представления программы в памяти - "образ памяти". Это позволяет рассматривать всю программу (в том числе и алгоритм) как данные для работы других программ, например, трансляторов;
−набор операций, выполняемый в программе, соответствует системе команд процессора, на котором она выполняется. Сюда же входят команды, которые обеспечивают заданный в программе порядок действий (операторов).
И, наконец, язык программирования также содержит в себе компоненты, предназначенные для описания соответствующих частей программы:
−средства описания данных: определение типов данных (форма представления) и переменных;
−набор операций над основными типами данных (включая ввод-вывод), а также средства записи выражений;
−набор операторов, определяющих различные варианты порядка выполнения выражений в программе (последовательность, условие, повторение, блок);
−средства разбиения программы на независимые части - модули (функции, процедуры), взаимодействующие между собой через программные интерфейсы [1].
1.2 Классификация языков программирования
Существуют различные классификации языков программирования.
По наиболее распространенной классификации все языки программирования, в соответствии с тем, в каких терминах необходимо описать задачу, делят на языки низкого и высокого уровня.
Если язык близок к естественному языку программирования, то он называется языком высокого уровня, если ближе к машинным командам, - языком низкого уровня.
В группу языков низкого уровня входят машинные языки и языки символического кодирования: Автокод, Ассемблер. Операторы этого языка - это те же машинные команды, но записанные мнемоническими кодами, а в качестве операндов используются не конкретные адреса, а символические имена. Все языки низкого уровня ориентированы на определенный тип компьютера, т. е. являются машинно-зависимыми.
Машинно-ориентированные языки - это языки, наборы операторов и изобразительные средства которых существенно зависят от особенностей ЭВМ (внутреннего языка, структуры памяти и т.д.).
К языкам программирования высокого уровня относят Фортран (переводчик формул - был разработан в середине 50-х годов программистами фирмы IBM и в основном используется для программ, выполняющих естественно - научные и математические расчеты), Алгол, Кобол (коммерческий язык - используется, в первую очередь, для программирования экономических задач), Паскаль, Бейсик (был разработан профессорами Дармутского колледжа Джоном Кемени и Томасом Курцом), Си (Деннис Ритч - 1972 год), Пролог (в основе языка лежит аппарат математической логики) и т.д.
Эти языки машинно-независимы, т.к. они ориентированы не на систему команд той или иной ЭВМ, а на систему операндов, характерных для записи определенного класса алгоритмов. Однако программы, написанные на языках высокого уровня, занимают больше памяти и медленнее выполняются, чем программы на машинных языках.
Программу, написанную на языке программирования высокого уровня, ЭВМ не понимает, поскольку ей доступен только машинный язык. Поэтому для перевода программы с языка программирования на язык машинных кодов используют специальные программы - трансляторы.
Языки программирования также можно разделять на поколения:
−языки первого поколения: машинно-ориентированные с ручным управлением памяти на компьютерах первого поколения.
−языки второго поколения: с мнемоническим представлением команд, так называемые автокоды.
−языки третьего поколения: общего назначения, используемые для создания прикладных программ любого типа. Например, Бейсик, Кобол, Си и Паскаль.
−языки четвертого поколения: усовершенствованные, разработанные для создания специальных прикладных программ, для управления базами данных.
−языки программирования пятого поколения: языки декларативные, объектно-ориентированные и визуальные. Например, Пролог, ЛИСП (используется для построения программ с использованием методов искусственного интеллекта), C++, C#, Visual Basic, Delphi.
Можно выделить еще один класс языков программирования - объектно-ориентированные языки высокого уровня. На таких языках не описывают подробной последовательности действий для решения задачи, хотя они содержат элементы процедурного программирования. Объектно-ориентированные языки, благодаря богатому пользовательскому интерфейсу, предлагают человеку решить задачу в удобной для него форме.
Первый объектно-ориентированный язык программирования Simula был создан в 1960-х годах Нигаардом и Далом [2].
1.3 Объектно-ориентированное программирование
Объектно-ориентированное программирование является относительно новым подходом к созданию компьютерных приложений, который призван устранить многие из проблем, существующих в традиционных методиках программирования. Вид программирования, с которым мы пока имели дело, называется функциональным (или процедурным) программированием и часто приводит к созданию так называемых монолитных приложений, все функции которых сконцентрированы в нескольких модулях кода (а то и вовсе в одном). В ООП обычно используется гораздо больше модулей, каждый из которых обеспечивает конкретные функции и может быть изолирован или даже полностью отделен от всех остальных. Такое модульное программирование обеспечивает гораздо большую гибкость и возможности для многократного использования кода.
Чтобы нагляднее показать, о чем идет речь, представьте, что высокопроизводительное компьютерное приложение является мощным гоночным автомобилем. При создании с помощью традиционных приемов программирования этот автомобиль будет представлять собой одно целое. Если понадобится что-то улучшить в этом автомобиле, его придется заменить целиком, т.е. отправить обратно изготовителю для переделки профессиональным механиком или вообще купить новый автомобиль. А технология ООП позволяет, например, купить у изготовителя новый двигатель и самостоятельно заменить его, следуя инструкциям изготовителя и не углубляясь в тонкости проведения ремонтных работ.
В традиционном приложении поток выполнения обычно прост и линеен. Приложения загружаются в память, начинают выполняться в точке А, завершают работу в точке Б и затем выгружаются из памяти. Попутно могут использоваться и другие разнообразные сущности, вроде файлов на носителе данных или возможностей видеокарты, но основная часть обработки выполняется все-таки в одном месте. Сама обработка данных обычно несложная, использует различные математические и логические средства, а для построения более сложных представлений данных применяются простые типы вроде целочисленных или логических.
В ООП подобная линейность встречается редко. Результаты достигаются те же, но способ их получения зачастую выглядит совершенно по-другому. В ООП основной акцент делается на структуру и смысл данных, а также на взаимодействие этих данных с другими данными. Это обычно требует больше усилий на этапах проектирования приложения, но обеспечивает возможность его расширения. После принятия решения о представлении конкретных типов данных это представление может применяться в последующих версиях данного приложения и даже в совершенно новых приложениях. Наличие подобного соглашения может значительно сократить время разработки. Этим можно объяснить пример с гоночным автомобилем, где таким соглашением является структурирование кода "двигателя", который позволяет легко подставлять новый код (новый двигатель), не возвращая его изготовителю. Помимо этого, двигатель после создания можно использовать и для других целей - например, в другом автомобиле или вовсе в подводной лодке.
ООП часто упрощает программирование с помощью соглашений по представлению и применению более абстрактных объектов. Например, соглашение может приниматься не только по формату данных, используемых для отправки выходных данных на устройство вроде принтера, но и по методам обмена данными с этим устройством, т.е. инструкциям, которые оно должно понимать, и т.д. В автомобилестроении такое соглашение касалось бы способа подключения двигателя к топливной системе, трансмиссии и т.п.
Как видно из названия этой технологии, достигается это все с помощью объектов.
Объект - это "строительный блок" в ООП-приложении. Такой строительный блок инкапсулирует часть приложения - процесс, порцию данных или какой-то более абстрактный объект.
Простейшие объекты могут быть очень похожи на знакомый нам тип структуры, который содержит члены типа переменных и функций. Содержащиеся переменные представляют хранимые в объекте данные, а содержащиеся функции обеспечивают доступ к возможным действиям этого объекта. Чуть более сложные объекты могут вообще не содержать данных, а представлять процесс и содержать только реализующие этот процесс функции. Примером такого объекта может служить принтер с функциями управления (распечатка документа, вывод тестовой страницы и т.д.).
Объекты в языке C# создаются из типов, как и хорошо знакомые составные переменные. Для типа объекта в ООП имеется специальное название - класс. Определения классов позволяют создавать объекты, т.е. реальные именованные экземпляры класса. Понятия "экземпляр класса" и "объект" эквивалентны, но термины "класс" и "объект" означают совершенно разные вещи.
Свойства и поля обеспечивают доступ к содержащимся в объекте данным. Эти данные как раз и являются тем, что отличает отдельные объекты друг от друга, поскольку в свойствах и полях разных объектов одного и того же класса могут храниться разные значения.
Различные фрагменты содержащихся в объекте данных вместе образуют состояние этого объекта. Например, пусть имеется класс объектов, представляющий чашку кофе и потому имеющий имя CupOfCoffee. При создании экземпляра (т.е. объекта) этого класса необходимо обеспечить его состояние, чтобы он был осмысленным. Для этого использующий данный объект код может с помощью свойств и полей задать сорт используемого кофе, содержится ли в кофе молоко и/или сахар, является ли кофе быстрорастворимым, и т.д. Тогда каждый конкретный объект CupOfCofee будет иметь определенное состояние, например: "Чашка колумбийского кофе с молоком и двумя кусочками сахара".
Поля и свойства имеют типы, поэтому информация может в них храниться в виде значений string, int и т.д. Свойства отличаются от полей тем, что они не предоставляют непосредственный доступ к данным. Объекты могут ограждать пользователей от внутренних деталей своих данных, которые не обязательно взаимно однозначно представлены в существующих свойствах. Скажем, в поле для хранения информации о количестве кусочков сахара в экземпляре CupOfCoffee пользователи смогут помещать любые значения, ограниченные лишь пределами типа этого поля. То есть, например, в случае использования для хранения этих данных типа int пользователи смогут помещать в это поле любое значение в диапазоне от - 2 147 483 648 до 2 147 483 647. Очевидно, что не все такие значения будут иметь смысл, особенно отрицательные, да и для слишком больших положительных может понадобиться чашка необычайно больших размеров. Использование свойства для хранения этой информации легко позволяет ограничить данное значение, скажем, только числами от 0 до 2.
В общем случае для доступа к состоянию лучше предоставлять свойства, а не поля, поскольку они позволяют управлять многими аспектами их поведения. Этот выбор никак не влияет на код, где применяются экземпляры объектов, т.к. синтаксис для использования свойств и полей выглядит одинаково.
Объект может четко определять и тип доступа к свойствам (для чтения и/или для записи). Некоторые свойства могут быть доступными только для чтения, т.е. они позволяют узнать их значения, но не изменять их (по крайней мере, непосредственно). Это часто бывает удобно для одновременного считывания нескольких фрагментов состояния. Например, класс CupOfCoffee может иметь доступное только для чтения свойство по имени Description (Описание), возвращающее строку с полной информацией о состоянии экземпляра этого класса. Конечно, эти сведения можно собрать и путем опроса нескольких свойств, но наличие такого свойства может сэкономить время и усилия. Аналогично ведут себя и свойства, доступные только для записи.
Кроме доступа для чтения и записи, для свойств и полей можно задавать разные виды доступности. Доступность членов класса определяет, какой код может получать доступ к этим членам, т.е. являются ли они доступными для всего кода (общедоступные), только для кода внутри класса (приватные) или следуют более сложной схеме (об этом будет рассказано позже). Как правило, поля делают приватными, а доступ к ним открывается через общедоступные свойства. При таком подходе код внутри класса имеет прямой доступ к хранящимся в поле данным, а общедоступное свойство ограждает внешних пользователей от этих данных и не позволяет им заносить туда недопустимое содержимое. Об общедоступных членах говорят, что они предоставляются классом.
Доступность немного похожа на область видимости переменных. Например, приватные поля и свойства можно считать локальными для объекта, который ими владеет, а область видимости общедоступных полей и свойств охватывает и внешний для объекта код [3].
Объектно-ориентированное программирование базируется на трех основных принципах:
−инкапсуляция;
−наследование;
−полиморфизм.
Инкапсуляция - это комбинирование данных и методов, которые манипулируют этими данными. Само по себе понятие класса подразумевает инкапсуляцию. Инкапсуляция позволяет обеспечить защиту данных от внешнего вмешательства или неправильного использования. Степень закрытости данных регулируется областями видимости (Public, Private, Protected). Обычно открытые члены класса используются для того, чтобы обеспечить контролируемый интерфейс с его закрытой частью [4].
Наследование (inheritance) - один из самых важных механизмов в ООП. Любой класс может наследоваться от другого класса, а это значит, что он будет иметь все те члены, что и класс, от которого он унаследован. В терминологии ООП класс, от которого наследуется (порождается) другой класс, называется родительским или базовым классом. Классы в C# могут непосредственно наследоваться только от одного базового класса, хотя у того базового класса может быть собственный базовый класс, и т.д.
Механизм наследования позволяет расширять или создавать конкретные классы от одного более общего базового класса. Например, возьмем класс, представляющий животное с фермы. Этот класс мог бы называться Animal (Животное) и обладать методами вроде EatFood() (Питаться) или Breed() (Плодиться). От него можно создать производный класс по имени Cow (Корова), который поддерживает все эти методы, но при этом имеет и собственные - например, Moo() (Мычать) и SupplyMilk() (Давать молоко). Другим производным классом может быть класс Chicken (Курица) с методами Cluck() (Кудахтать) и LayEgg() (Снести яйцо) (рисунок 1.1) [3].
Полиморфизм. В значительной степени мощь объектно-ориентированного программирования вытекает из применения различных форм полиморфизма. Слово полиморфизм греческого происхождения и означает приблизительно "много форм".
Полиморфизм дает возможность определения единого по имени метода (процедуры или функции) для всех объектов иерархии наследования, причем для каждого объекта, метод будет выполняться по-своему.
Рисунок 1.1 - Представление отношений наследования в UML
Реализация концепции полиморфизма означает, что можно создать общий интерфейс для группы близких по смыслу действий. Преимуществом полиморфизма является то, что он помогает снижать сложность программ, разрешая использование одного интерфейса для единого класса действий [4].
2. Использование хеширования для поиска информации
.1 Таблицы с прямой адресацией
Для многих приложений достаточны динамические множества, поддерживающие только стандартные словарные операции вставки, поиска и удаления. Например, компилятор языка программирования поддерживает таблицу символов, в которой ключами элементов являются произвольные символьные строки, соответствующие идентификаторам в языке. Хеш-таблица представляет собой эффективную структуру данных для реализации словарей. Хотя на поиск элемента в хеш-таблице может в наихудшем случае потребоваться столько же времени, что и в связанном списке, а именно в O(n), на практике хеширование исключительно эффективно. При вполне обоснованных допущениях математическое ожидание времени поиска элемента в хеш-таблице составляет O(1)[5].
Прямая адресация представляет собой простейшую технологию, которая хорошо работает для небольших множеств ключей. Предположим, что приложению требуется динамическое множество, каждый элемент которого имеет ключ из множества U = {0, 1, …, m - 1}, где m не слишком велико. Кроме того, предполагается, что никакие два элемента не имеют одинаковых ключей.
Для представления динамического множества мы используем массив, или таблицу с прямой адресацией, который обозначим как T[0..m - 1], каждая позиция, или ячейка, которого соответствует ключу из пространства ключей U. Ячейка k указывает на элемент множества с ключом k. Если множество не содержит элемента с ключом k, то T[k] = NIL.
Каждая из приведенных операций очень быстрая: время их работы равно O(1).
Недостаток прямой адресации очевиден: если пространство ключей U велико, хранение таблицы T размером |U| непрактично, а то и вовсе невозможно - в зависимости от количества доступной памяти и размера пространства ключей. Кроме того, множество K реально сохраненных ключей может быть мало по сравнению с пространством ключей U, а в этом случае память, выделенная для таблицы T, в основном расходуется напрасно.
Когда множество K хранящихся в словаре ключей гораздо меньше пространства возможных ключей U, хеш-таблица требует существенно меньше места, чем таблица с прямой адресацией. Точнее говоря, требования к памяти могут быть снижены до O(|K|), при этом время поиска элемента в хеш-таблице остается равным O(1). Надо только заметить, что это граница среднего времени поиска, в то время как в случае таблицы с прямой адресацией эта граница справедлива для наихудшего случая.
В случае прямой адресации элемент с ключом k хранится в ячейке k. При хешировании этот элемент хранится в ячейке h(k), т.е. мы используем хеш-функцию h для вычисления ячейки для данного ключа k. Функция h отображает пространство ключей U на ячейки хеш-таблицы T[0..m - 1].
Мы говорим, что элемент с ключом k хешируется в ячейку h(k); величина h(k) называется хеш-значением ключа k. Цель хеш-функции состоит в том, чтобы уменьшить рабочий диапазон индексов массива, и вместо |U| значений мы можем обойтись всего лишь m значениями. Соответственно снижаются и требования к количеству памяти.
Однако здесь есть одна проблема: два ключа могут быть хешированы в одну и ту же ячейку. Такая ситуация называется коллизией. К счастью, имеются эффективные технологии для разрешения конфликтов, вызываемых коллизиями[6].
Конечно, идеальным решением было бы полное устранение коллизий. Мы можем попытаться добиться этого путем выбора подходящей хеш-функции h. Одна из идей заключается в том, чтобы сделать h "случайной", что позволило бы избежать коллизий или хотя бы минимизировать их количество (этот характер функции хеширования отображается в самом глаголе "to hash", который означает "мелко порубить, перемешать"). Само собой разумеется, функция h должна быть детерминистической и для одного и того же значения к всегда давать одно и то же хеш-значение h(k). Однако поскольку |U| > m, должно существовать как минимум два ключа, которые имеют одинаковое хеш-значение. Таким образом, полностью избежать коллизий невозможно в принципе, и хорошая хеш-функция в состоянии только минимизировать количество коллизий. Таким образом, нам крайне необходим метод разрешения возникающих коллизий.
Разрешение коллизий при помощи цепочек. При использовании данного метода мы объединяем все элементы, хешированые в одну и ту же ячейку, в связанный список. Ячейка j содержит указатель на заголовок списка всех элементов, хеш-значение ключа которых равно j; если таких элементов нет, ячейка содержит значение NULL.
.2 Хеш-функции
Качественная хеш-функция удовлетворяет (приближенно) предположению простого равномерного хеширования: для каждого ключа равновероятно помещение в любую из m ячеек, независимо от хеширования остальных ключей. К сожалению, это условие обычно невозможно проверить, поскольку, как правило, распределение вероятностей, в соответствии с которым поступают вносимые в таблицу ключи, неизвестно; кроме того, вставляемые ключи могут не быть независимыми.
Во избежание ситуации, когда хеш-код одного ключа равен хеш-коду другого, схема хеширования должна включать алгоритм разрешения конфликтов (collision resolution policy), определяющий порядок действий, если ключ отображается на занятую другой записью позицию.
На практике при построении качественных хеш-функций зачастую используются различные эвристические методики. В процессе построения большую помощь оказывает информация о распределении ключей. Рассмотрим, например, таблицу символов компилятора, в которой ключами служат символьные строки, представляющие идентификаторы в программе. Зачастую в одной программе встречаются похожие идентификаторы, например, pt и pts. Хорошая хеш-функция должна минимизировать шансы попадания этих идентификаторов в одну ячейку хеш-таблицы.
Построение хеш-функции методом деления состоит в отображении ключа k в одну из ячеек путем получения остатка от деления k на m, т.е. хеш-функция имеет вид h(k) = k mod m.
Например, если хеш-таблица имеет размер m = 12, а значение ключа k = 100, то h(k) = 4. Поскольку для вычисления хеш-функции требуется только одна операция деления, хеширование методом деления считается достаточно быстрым.
При использовании данного метода мы обычно стараемся избегать некоторых значений m. Например, m не должно быть степенью 2, поскольку если m = 2p, то h(k) представляет собой просто p младших битов числа k. Если только заранее не известно, что все наборы младших p битов ключей равновероятны, лучше строить хеш-функцию таким образом, чтобы ее результат зависел от всех битов ключа.
Построение хеш-функции методом умножения выполняется в два этапа. Сначала мы умножаем ключ k на константу 0 < A < 1 и получаем дробную часть полученного произведения. Затем мы умножаем полученное значение на m и отбрасываем дробную часть.
Достоинство метода умножения заключается в том, что значение m перестает быть критичным. Обычно величина m из соображений удобства реализации функции выбирается равной степени 2.
Хотя описанный метод работает с любыми значениями константы A, некоторые значения дают лучшие результаты по сравнению с другими. Оптимальный выбор зависит от характеристик хешируемых данных. Кнут предложил использовать дающее неплохие результаты значение A = 0.6180339887.
.3 Открытая адресация
При использовании метода открытой адресации все элементы хранятся непосредственно в хеш-таблице, т.е. каждая запись таблицы содержит либо элемент динамического множества, либо значение NULL. При поиске элемента мы систематически проверяем ячейки таблицы до тех пор, пока не найдем искомый элемент или пока не убедимся в его отсутствии в таблице. Здесь, в отличие от метода цепочек, нет ни списков, ни элементов, хранящихся вне таблицы. Таким образом, в методе открытой адресации хеш-таблица может оказаться заполненной, делая невозможной вставку новых элементов; коэффициент заполнения a не может превышать 1.
Вместо того чтобы следовать по указателям, мы вычисляем последовательность проверяемых ячеек. Дополнительная память, освобождающаяся в результате отказа от указателей, позволяет использовать хеш-таблицы большего размера при том же общем количестве памяти, потенциально приводя к меньшему количеству коллизий и более быстрой выборке.
Пусть задана обычная хеш-функция h: U - {0, 1,..., m - 1}. Метод линейного исследования для вычисления последовательности исследований использует хеш-функцию
h(k, i) = (h(k) + i) mod m, (1.1)
где i принимает значения от 0 до m - 1 включительно. Для данного ключа k первой исследуемой ячейкой является T[h(k)], т.е. ячейка, которую дает вспомогательная хеш-функция. Далее мы исследуем ячейку T[h(k) + 1] и далее последовательно все до ячейки T[m - 1], после чего переходим в начало таблицы и последовательно исследуем ячейки T[0], Т[1], и так до ячейки T[h(k) - 1]. Поскольку начальная исследуемая ячейка однозначно определяет всю последовательность исследований целиком, всего имеется m различных последовательностей.
Линейное исследование легко реализуется, однако с ним связана проблема первичной кластеризации, связанной с созданием длинных последовательностей занятых ячеек, что, само собой разумеется, увеличивает среднее время поиска. Кластеры возникают в связи с тем, что вероятность заполнения пустой ячейки, которой предшествуют i заполненных ячеек, равна (i + 1) / m. Таким образом, это приводит к увеличению среднего времени поиска.
Квадратичное исследование использует хеш-функцию вида
h(k, i) = (h(k) + c1i + c2i2) mod m, (1.2)
где h - вспомогательная хеш-функция, c1 и c2 != 0 - вспомогательные константы, а i принимает значения от 0 до m - 1 включительно. Начальная исследуемая ячейка - T[h(k)]; остальные исследуемые позиции смещены относительно нее на величины, которые описываются квадратичной зависимостью от номера исследования i. Этот метод работает существенно лучше линейного исследования, но для того, чтобы исследование охватывало все ячейки, необходим выбор специальных значений c1 c2 и m. Кроме того, если два ключа имеют одну и то же начальную позицию исследования, то одинаковы и последовательности исследования в целом, так как из h1(k, 0) = h2(k, 0) вытекает h1(k, i) = h2(k, i). Это свойство приводит к более мягкой вторичной кластеризации. Как и в случае линейного исследования, начальная ячейка определяет всю последовательность, поэтому всего используется m различных последовательностей исследования.
Двойное хеширование представляет собой один из наилучших способов использования открытой адресации, поскольку получаемые при этом перестановки обладают многими характеристиками случайно выбираемых перестановок. Двойное хеширование использует хеш-функцию вида
h(k, i) = (h1(k) + ih2(k)) mod m, (1.3)
где h1 и h2 - вспомогательные хеш-функции. Начальное исследование выполняется в позиции T[h1(k)], а смещение каждой из последующих исследуемых ячеек относительно предыдущей равно h2(k) по модулю m. Следовательно, в отличие от линейного и квадратичного исследования, в данном случае последовательность исследования зависит от ключа k по двум параметрам - в плане выбора начальной исследуемой ячейки и расстояния между соседними исследуемыми ячейками, так как оба эти параметра зависят от значения ключа.
Для того чтобы последовательность исследования могла охватить всю таблицу, значение h2(k) должно быть взаимно простым с размером хеш-таблицы m. Удобный способ обеспечить выполнение этого условия состоит в выборе числа m, равного степени 2, и разработке хеш-функции h2 таким образом, чтобы она возвращала только нечетные значения.
.4 Алгоритмы работы с хеш-таблицей
Вычисление хеш-кода представлено на рисунке 2.1. Входными параметрами являются строка и размер хеш-таблицы. На выходе мы получаем значение хеш-функции, вычисленное как остаток от деления на размер таблицы, которое будет равно индексу нашего элемента в массиве.
Рисунок 2.1 - Схема вычисления хеш-кода
Функция поиска в хеш-таблице представлена на рисунке 2.2. Входным параметром является строка. Для вычисления индекса элемента используется описанная выше хеш-функция.
Рисунок 2.2 - Схема поиска элемента в хеш-таблице
Функция добавления в хеш-таблицу представлена на рисунке 2.3. Входным параметром является добавляемый элемент.
Рисунок 2.3 - Схема вставки элемента в хеш-таблицу
Функция удаления из хеш-таблицы представлена на рисунке 2.4. Входным параметром является удаляемый элемент.
Рисунок 2.4 - Схема удаления элемента из хеш-таблицы
2.5 Постановка задачи
программирование хеширование зондирование приложение
В ходе данной работы необходимо разработать Windows-приложение на языке С#, выполняющее следующие действия:
1)Чтение из xml-файла информации объектах класса согласно варианту. Количество записей не менее 50 (см. таблицу 2.1);
2)Вывод исходных данных в виде таблицы;
)Самостоятельный выбор визуальных компонентов для реализации операций перегрузки;
)На основе полученных данных формировать хеш-таблицу (ключ и метод разрешения коллизий указан в таблице 2.2);
)Редактирование информации (добавление, удаление, замена) с внесением соответствующих изменений в хеш-таблицу;
)Поиск информации по заданному значению;
)Вывод справочной информации о приложении и об авторе.
Создать несколько классов согласно варианту. Классы должны содержать следующие элементы:
1)Описание полей класса, а также свойств доступа к данным полям находятся в таблице 2.1(выделенное жирным поле оформлено как перечисление);
2)Конструкторы с параметрами и по умолчанию, а также необходимые свойства и методы;
)Перегрузку одного из операторов отношения (сравниваются два преподавателя по размеру нагрузки);
)Перегрузку префиксного и постфиксного инкремента (инкрементируется нагрузка на дисциплину у выбранного преподавателя);
)