Хеширование

Дисциплина: Программирование
Тип работы: Курсовая
Тема: Хеширование

Министерство Образования РФ
Воронежский государственный университет
Факультет Компьютерных наук
Кафедра программирования и информационных технологий
Курсовая работа
по курсу «Технологии программирования» по теме
«Хеширование»
Выполнил: студент 3
его курса
Шадчнев Евгений
Проверил: доцент каф.
ПиИТ
Хлебостроев Виктор Григорьевич
Воронеж 200
Содержание
TOC o \"1-3\" h z u
Введение
PAGEREF _Toc29536964 h
Хеш-функции
PAGEREF _Toc29536965 h
Метод деления
PAGEREF _Toc29536966 h
Метод умножения (мультипликативный)
PAGEREF _Toc29536967 h
Динамическое хеширование
PAGEREF _Toc29536968 h
Расширяемое хеширование (
extendible hashing)
PAGEREF _Toc29536969 h
Функции, сохраняющие порядок ключей (
Order
preserving
hash
functions)
PAGEREF _Toc29536970 h
Минимальное идеальное хеширование
PAGEREF _Toc29536971 h
Разрешение коллизий
PAGEREF _Toc29536972 h
Метод цепочек
PAGEREF _Toc29536973 h
Открытая адресация
PAGEREF _Toc29536974 h
Линейная адресация
PAGEREF _Toc29536975 h
Квадратичная и произвольная адресация
PAGEREF _Toc29536976 h
Адресация с двойным хешированием
PAGEREF _Toc29536977 h
Удаление элементов хеш-таблицы
PAGEREF _Toc29536978 h
Применение хеширования
PAGEREF _Toc29536979 h
Хеширование паролей
PAGEREF _Toc29536980 h
Заключение
PAGEREF _Toc29536981 h
Приложение (демонстрационная программа)
PAGEREF _Toc29536982 h
Список литературы:
PAGEREF _Toc29536983 h
Введение
С хешированием мы сталкиваемся едва ли не на каждом шагу: при работе с браузером (список 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). Эта работа привела к созданию открытой адресации с двойным хешированием.
Далее будут рассмотрены основные виды хеш-функций и некоторые их модификации, методы разрешения коллизий, проблемы удаления элементов из хеш-таблицы, а также
некоторые варианты применения хеширования.
Хеш-функции
Хеш-функция – это некоторая функция
K), которая берет некий ключ
K и возвращает адрес, по которому производится поиск в хеш-таблице, чтобы получить информацию, связанную с
K. Например,
K – это номер телефона абонента, а искомая информация – его имя. Функция в данном случае нам точно скажет, по какому адресу найти искомое. Пример с телефонным справочником
иллюстрируется демонстрационной программой на прилагаемом компакт-диске.
Коллизия – это ситуация, когда
K1) =
K2), в то время как
K1 /=
K2. В этом случае, очевидно, необходимо найти новое место для хранения данных. Очевидно, что количество коллизий необходимо минимизировать. Методикам разрешения коллизий
будет посвящен отдельный раздел ниже.
Хорошая хеш-функция должна удовлетворять двум требованиям:
ее вычисление должно выполняться очень быстро;
она должна минимизировать число коллизий.
Итак, первое свойство хорошей хеш-функции зависит от компьютера, а второе – от данных. Если бы все данные были случайными, то хеш-функции были бы очень простые (несколько битов
ключа, например). Однако на практике случайные данные встречаются крайне редко, и приходится создавать функцию, которая зависела бы от всего ключа.
Теоретически невозможно определить хеш-функцию так, чтобы она создавала случайные данные из реальных неслучайных файлов. Однако на практике реально создать достаточно хорошую
имитацию с помощью простых арифметических действий. Более того, зачастую можно использовать особенности данных для создания хеш-функций с минимальным числом коллизий (меньшим, чем при
истинно случайных данных) [3].
Возможно, одним из самых очевидных и простых способов хеширования является метод середины квадрата, когда ключ возводится в квадрат и берется несколько цифр в середине. Здесь и далее
предполагается, что ключ сначала приводится к це...

Забрать файл

Похожие материалы: