Курсовая работа по курсу «Технологии программирования» по теме «Хеширование»

Скачать 245.44 Kb.

Название	Курсовая работа по курсу «Технологии программирования» по теме «Хеширование»
страница	1/6
Дата публикации	14.01.2015
Размер	245.44 Kb.
Тип	Курсовая

100-bal.ru > Информатика > Курсовая

1 2 3 4 5 6

Министерство Образования РФ

Воронежский государственный университет

Факультет Компьютерных наук

Кафедра программирования и информационных технологий

Курсовая работа

по курсу «Технологии программирования» по теме

«Хеширование»

Выполнил: студент 3^егокурса

Шадчнев Евгений

Проверил: доцент каф. ПиИТ

Хлебостроев Виктор Григорьевич

Воронеж 2003

Содержание

Введение 4

Хеш-функции 5

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

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

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

Расширяемое хеширование (extendible hashing) 8

Функции, сохраняющие порядок ключей (Order preserving hash functions) 9

Минимальное идеальное хеширование 9

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

Метод цепочек 11

Открытая адресация 11

Линейная адресация 12

Квадратичная и произвольная адресация 12

Адресация с двойным хешированием 12

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

Применение хеширования 14

Хеширование паролей 14

Заключение 16

Приложение (демонстрационная программа) 16

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

Введение

С хешированием мы сталкиваемся едва ли не на каждом шагу: при работе с браузером (список Web-ссылок), текстовым редактором и переводчиком (словарь), языками скриптов (Perl, Python, PHP и др.), компилятором (таблица символов). По словам Брайана Кернигана, это «одно из величайших изобретений информатики». Заглядывая в адресную книгу, энциклопедию, алфавитный указатель, мы даже не задумываемся, что упорядочение по алфавиту является не чем иным, как хешированием.

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

Термин «хеширование» (hashing) в печатных работах по программированию появился сравнительно недавно (1967 г., [1]), хотя сам механизм был известен и ранее. Глагол «hash» в английском языке означает «рубить, крошить». Для русского языка академиком А.П. Ершовым [2] был предложен достаточно удачный эквивалент — «расстановка», созвучный с родственными понятиями комбинаторики, такими как «подстановка» и «перестановка». Однако он не прижился.

Как отмечает Дональд Кнут [3], идея хеширования впервые была высказана Г.П. Ланом при создании внутреннего меморандума IBM в январе 1953 г. с предложением использовать для разрешения коллизий хеш-адресов метод цепочек. Примерно в это же время другой сотрудник IBM – Жини Амдал – высказала идею использования открытую линейную адресацию. В открытой печати хеширование впервые было описано Арнольдом Думи (1956), указавшим, что в качестве хеш-адреса удобно использовать остаток от деления на простое число. А. Думи описывал метод цепочек для разрешения коллизий, но не говорил об открытой адресации. Подход к хешированию, отличный от метода цепочек, был предложен А.П. Ершовым (1957, [2]), который разработал и описал метод линейной открытой адресации. Среди других исследований можно отметить работу Петерсона (1957, [4]). В ней реализовывался класс методов с открытой адресацией при работе с большими файлами. Петерсон определил открытую адресацию в общем случае, проанализировал характеристики равномерного хеширования, глубоко изучил статистику использования линейной адресации на различных задачах. В 1963 г. Вернер Букхольц [6] опубликовал наиболее основательное исследование хеш-функций.

К концу шестидесятых годов прошлого века линейная адресация была единственным типом схемы открытой адресации, описанной в литературе, хотя несколькими исследователями независимо была разработана другая схема, основанная на неоднократном случайном применении независимых хеш-функции ([3], стр. 585). В течение нескольких последующих лет хеширование стало широко использоваться, хотя не было опубликовано никаких новых работ. Затем Роберт Моррис [5] обширный обзор по хешированию и ввел термин «рассеянная память» (scatter storage). Эта работа привела к созданию открытой адресации с двойным хешированием.

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

1 2 3 4 5 6

Добавить документ в свой блог или на сайт

Похожие:

	Курсовая работа является обязательным видом итогового контроля по... Курсовая работа – это первый этап в самостоятельном теоретическом осмыслении материала, накопленного в ходе обучения в университете,...		Рабочая программа по дисциплине с 3 «Технологии и методы программирования» Цель преподавания дисциплины: Целью изучения дисциплины «Технологии и методы программирования» является изучение современных технологий...
	Курсовая работа " Использование технологии Macromedia Flash для создания... Информатизация образования это процесс интеллектуализации деятельности обучающегося. Она развивается на основе реализации возможностей...		Курсовая работа по дисциплине «Технологии программирования» на тему:... Протокол, предназначенный для работы в данной сети, был разработан таким образом, чтобы быть устойчивым к нарушениям целостности...
	Курсовая работа на тему : Формирование рынка ценных бумаг в Украине Курсовая работа содержит 38 листов, 2 рисунка, 2 таблицы и было использовано 11 источников		Курсовая работа На тему: «Современные технологии обучения» Ii. Современные технологии организации образовательного процесса
	Курсовая работа Курсовая работа оформляется в виде электронного файла и прикрепляется к своей странице в системе мониторинга нир. Распечатывать работу...		Курсовая работа по курсу тэс на тему “Расчет технических характеристик Канала связи
	Курсовая работа по дисциплине Электромагнитная совместимость систем... Курсовая работа состоит из 20 с, в которых содержаться: 3 рисунка, 3 таблицы, 6 формул и 4 ссылки на литературу		Курсовая работа по дисциплине «Предпринимательское право» Курсовая работа имеет целью систематизацию, закрепление и расширение теоретических знаний, углубленное изучение и решение студентом...
	11-м классам! Альтернативная форма зачета по курсу геометрии – курсовая...		Курсовой работы. Составитель: доцент Корляков А. С. Екатеринбург... Курсовая работа самостоятельная работа студента, выполняемая в соответствии с типовой программой учебного процесса по подготовке...
	Рекомендации к оформлению курсовой и дипломной работы по истории искусства. Курсовая работа Курсовая работа задание, которое выполняется студентами в определённый срок и по определённым требованиям. Защита курсовых работ...		Пояснительная записка: Цели и задачи дисциплины. Дисциплина «Языки программирования» Ступников А. А. Языки программирования. Учебно-методический комплекс. Рабочая программа для студентов очной формы обучения, направления...
	Курсовая работа на тему «Открытый урок» Данная курсовая работа выполнена для того, чтобы учителя русского языка и литературы могли использовать разработанные мною уроки...		Курсовая работа по курсу «Макроэкономика» Рынок труда: основные понятия. Опыт зарубежных стран в регулировании рынка труда стр

Школьные материалы