Хеширование

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

    Министерство Образования РФ
    Воронежский государственный университет
    Факультет Компьютерных наук
    Кафедра программирования и информационных технологий
    Курсовая работа
    по курсу «Технологии программирования» по теме
    «Хеширование»
    Выполнил: студент 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].
    Возможно, одним из самых очевидных и простых способов хеширования является метод середины квадрата, когда ключ возводится в квадрат и берется несколько цифр в середине. Здесь и далее
    предполагается, что ключ сначала приводится к це...

    Забрать файл

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


    Добавить комментарий
    Старайтесь излагать свои мысли грамотно и лаконично

    Введите код:
    Включите эту картинку для отображения кода безопасности
    обновить, если не виден код



ПИШЕМ УНИКАЛЬНЫЕ РАБОТЫ
Заказывайте напрямую у исполнителя!


© 2006-2016 Все права защищены