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




Скачать 191.55 Kb.
НазваниеКурсовая работа по курсу «Технологии программирования» по теме «Хеширование»
Дата публикации27.03.2014
Размер191.55 Kb.
ТипКурсовая
uchebilka.ru > Информатика > Курсовая
Реферат скачан с сайта allreferat.wow.ua


Хеширование

Министерство Образования РФ Воронежский государственный университет Факультет Компьютерных наук Кафедра программирования и информационных технологий Курсовая работа по курсу «Технологии программирования» по теме «Хеширование» Выполнил: студент 3его курса Шадчнев Евгений Проверил: доцент каф. ПиИТ Хлебостроев Виктор Григорьевич Воронеж 2003 СодержаниеВведение 3Хеш-функции 4 Метод деления 4 Метод умножения (мультипликативный) 5 Динамическое хеширование 5 Расширяемое хеширование (extendible hashing) 7 Функции, сохраняющие порядок ключей (Order preserving hash functions) 8 Минимальное идеальное хеширование 8Разрешение коллизий 10 Метод цепочек 10 Открытая адресация 10 Линейная адресация 11 Квадратичная и произвольная адресация 11 Адресация с двойным хешированием 11Удаление элементов хеш-таблицы 12Применение хеширования 13 Хеширование паролей 13Заключение 15Приложение (демонстрационная программа) 15Список литературы: 16ВведениеС хешированием мы сталкиваемся едва ли не на каждом шагу: при работе сбраузером (список 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). Эта работа привела к созданию открытой адресациис двойным хешированием.Далее будут рассмотрены основные виды хеш-функций и некоторые ихмодификации, методы разрешения коллизий, проблемы удаления элементов из хеш-таблицы, а также некоторые варианты применения хеширования.Хеш-функцииХеш-функция – это некоторая функция h(K), которая берет некий ключ K ивозвращает адрес, по которому производится поиск в хеш-таблице, чтобыполучить информацию, связанную с K. Например, K – это номер телефонаабонента, а искомая информация – его имя. Функция в данном случае нам точноскажет, по какому адресу найти искомое. Пример с телефонным справочникомиллюстрируется демонстрационной программой на прилагаемом компакт-диске.Коллизия – это ситуация, когда h(K1) = h(K2), в то время как K1 ? K2. Вэтом случае, очевидно, необходимо найти новое место для хранения данных.Очевидно, что количество коллизий необходимо минимизировать. Методикамразрешения коллизий будет посвящен отдельный раздел ниже.Хорошая хеш-функция должна удовлетворять двум требованиям: . ее вычисление должно выполняться очень быстро; . она должна минимизировать число коллизий.Итак, первое свойство хорошей хеш-функции зависит от компьютера, а второе –от данных. Если бы все данные были случайными, то хеш-функции были бы оченьпростые (несколько битов ключа, например). Однако на практике случайныеданные встречаются крайне редко, и приходится создавать функцию, котораязависела бы от всего ключа.Теоретически невозможно определить хеш-функцию так, чтобы она создаваласлучайные данные из реальных неслучайных файлов. Однако на практике реальносоздать достаточно хорошую имитацию с помощью простых арифметическихдействий. Более того, зачастую можно использовать особенности данных длясоздания хеш-функций с минимальным числом коллизий (меньшим, чем приистинно случайных данных) [3].Возможно, одним из самых очевидных и простых способов хеширования являетсяметод середины квадрата, когда ключ возводится в квадрат и беретсянесколько цифр в середине. Здесь и далее предполагается, что ключ сначалаприводится к целому числу, для совершения с ним арифметических операций.Однако такой способ хорошо работает до момента, когда нет большогоколичества нолей слева или справа. Многочисленные тесты показали хорошуюработу двух основных типов хеширования, один из которых основан на делении,а другой на умножении. Впрочем, это не единственные методы, которыесуществуют, более того, они не всегда являются оптимальными.Метод деленияМетод деления весьма прост – используется остаток от деления на M: h(K) = K mod MНадо тщательно выбирать эту константу. Если взять ее равной 100, а ключомбудет случить год рождения, то распределение будет очень неравномерным дляряда задач (идентификация игроков юношеской бейсбольной лиги, например).Более того, при четной константе значение функции будет четным при четном Kи нечетным - при нечетном, что приведет к нежелательному результату. Ещехуже обстоят дела, если M – это степень счисления компьютера, поскольку приэтом результат будет зависеть только от нескольких цифр ключа справа. Точнотакже можно показать, что M не должно быть кратно трем, поскольку прибуквенных ключах два из них, отличающиеся только перестановкой букв, могутдавать числовые значения с разностью, кратной трем (см. [3], стр. 552).Приведенные рассуждения приводят к мысли, что лучше использовать простоечисло. В большинстве случаев подобный выбор вполне удовлетворителен.Другой пример – ключ, являющийся символьной строкой С++. Хеш-функцияотображает эту строку в целое число посредством суммирования первого ипоследнего символов и последующего вычисления остатка от деления на 101(размер таблицы). Эта хеш-функция приводит к коллизии при одинаковых первоми последнем символах строки. Например, строки «start» и «slant» будутотображаться в индекс 29. Так же ведет себя хеш-функция, суммирующая всесимволы строки. Строки «bad» и «dab» преобразуются в один и тот же индекс.Лучшие результаты дает хеш-функция, производящая перемешивание битов всимволах.На практике, метод деления – самый распространенный [7].Метод умножения (мультипликативный)Для мультипликативного хеширования используется следующая формула: h(K) = [M * ((C * K) mod 1)]Здесь производится умножение ключа на некую константу С, лежащую винтервале [0..1]. После этого берется дробная часть этого выражения иумножается на некоторую константу M, выбранную таким образом, чтобырезультат не вышел за границы хеш-таблицы. Оператор [ ] возвращаетнаибольшее целое, которое меньше аргумента.Если константа С выбрана верно, то можно добиться очень хорошихрезультатов, однако, этот выбор сложно сделать. Дональд Кнут (см. [3], стр.553) отмечает, что умножение может иногда выполняться быстрее деления.Мультипликативный метод хорошо использует то, что реальные файлынеслучайны. Например, часто множества ключей представляют собойарифметические прогрессии, когда в файле содержатся ключи K, K + d, K +2d, …, K + td. Например, рассмотрим имена типа PART1, PART2, …, PARTN.Мультипликативный метод преобразует арифметическую прогрессию в приближенноарифметическую прогрессию h(K), h(K + d), h(K + 2d),… различных хеш-значений, уменьшая число коллизий по сравнению со случайной ситуацией.Впрочем, справедливости ради надо заметить, что метод деления обладает темже свойством.Частным случаем выбора константы является значение золотого сечения ? = (?5- 1)/2 ? 0,6180339887. Если взять последовательность ?, 2?, 3?,...где оператор возвращает дробную часть аргумента, то на отрезке [0..1]она будет распределена очень равномерно. Другими словами, каждое новоезначение будет попадать в наибольший интервал. Это явление было впервыезамечено Я. Одерфельдом (J. Oderfeld) и доказано С. Сверчковски (S.?wierczkowski) (см. [8]). В доказательстве играют важную роль числаФибоначчи. Применительно к хешированию это значит, что если в качествеконстанты С выбрать золотое сечение, то функция будет достаточно хорошорассеивать ключи вида PART1, PART2, …, PARTN. Такое хешированиеназывается хешированием Фибоначчи. Впрочем, существует ряд ключей (когдаизменение происходит не в последней позиции), когда хеширование Фибоначчиоказывается не самым оптимальным [3].Динамическое хешированиеОписанные выше методы хеширования являются статическими, т.е. сначалавыделяется некая хеш-таблица, под ее размер подбираются константы для хеш-функции. К сожалению, это не подходит для задач, в которых размер базыданных меняется часто и значительно [9]. По мере роста базы данных можно . пользоваться изначальной хеш-функцией, теряя производительность из-за роста коллизий; . выбрать хеш-функцию «с запасом», что повлечет неоправданные потери дискового пространства; . периодически менять функцию, пересчитывать все адреса. Это отнимает очень много ресурсов и выводит из строя базу на некоторое время.Существует техника, позволяющая динамически менять размер хеш-структуры[10]. Это – динамическое хеширование. Хеш-функция генерирует так называемыйпсевдоключ (“pseudokey”), который используется лишь частично для доступа кэлементу. Другими словами, генерируется достаточно длинная битоваяпоследовательность, которая должна быть достаточна для адресации всехпотенциально возможных элементов. В то время, как при статическомхешировании потребовалась бы очень большая таблица (которая обычно хранитсяв оперативной памяти для ускорения доступа), здесь размер занятой памятипрямо пропорционален количеству элементов в базе данных. Каждая запись втаблице хранится не отдельно, а в каком-то блоке (“bucket”). Эти блокисовпадают с физическими блоками на устройстве хранения данных. Если в блокенет больше места, чтобы вместить запись, то блок делится на два, а на егоместо ставится указатель на два новых блока.Задача состоит в том, чтобы построить бинарное дерево, на концах ветвейкоторого были бы указатели на блоки, а навигация осуществлялась бы наоснове псевдоключа. Узлы дерева могут быть двух видов: узлы, которыепоказывают на другие узлы или узлы, которые показывают на блоки. Например,пусть узел имеет такой вид, если он показывает на блок:|Zero |Null ||Bucket |Указатель ||One |Null |Если же он будет показывать на два других узла, то он будет иметь такойвид:|Zero |Адрес a ||Bucket |Null ||One |Адрес b |Вначале имеется только указатель на динамически выделенный пустой блок. Придобавлении элемента вычисляется псевдоключ, и его биты поочередноиспользуются для определения местоположения блока. Например (см. рисунок),элементы с псевдоключами 00… будут помещены в блок A, а 01… - в блок B.Когда А будет переполнен, он будет разбит таким образом, что элементы 000…и 001… будут размещены в разных блоках.[pic]Расширяемое хеширование (extendible hashing)Расширяемое хеширование близко к динамическому. Этот метод такжепредусматривает изменение размеров блоков по мере роста базы данных, но этокомпенсируется оптимальным использованием места. Т.к. за один разразбивается не более одного блока, накладные расходы достаточно малы [9].Вместо бинарного дерева расширяемое хеширование предусматривает список,элементы которого ссылаются на блоки. Сами же элементы адресуются понекоторому количеству i битов псевдоключа (см. рис). При поиске берется iбитов псевдоключа и через список (directory) находится адрес искомогоблока. Добавление элементов производится сложнее. Сначала выполняетсяпроцедура, аналогичная поиску. Если блок неполон, добавляется запись в негои в базу данных. Если блок заполнен, он разбивается на два, записиперераспределяются по описанному выше алгоритму. В этом случае возможноувеличение числа бит, необходимых для адресации. В этом случае размерсписка удваивается и каждому вновь созданному элементу присваиваетсяуказатель, который содержит его родитель. Таким образом, возможна ситуация,когда несколько элементов показывают на один и тот же блок. Следуетзаметить, что за одну операцию вставки пересчитываются значения не более,чем одного блока. Удаление производится по такому же алгоритму, тольконаоборот. Блоки, соответственно, могут быть склеены, а список – уменьшен вдва раза.[pic]Итак, основным достоинством расширяемого хеширования является высокаяэффективность, которая не падает при увеличении размера базы данных. Кромеэтого, разумно расходуется место на устройстве хранения данных, т.к. блокивыделяются только под реально существующие данные, а список указателей наблоки имеет размеры, минимально необходимые для адресации данногоколичества блоков. За эти преимущества разработчик расплачиваетсядополнительным усложнением программного кода.Функции, сохраняющие порядок ключей (Order preserving hash functions)Существует класс хеш-функций, которые сохраняют порядок ключей [11].Другими словами, выполняется K1 < K2 ( h(K1) < h(K2)Эти функции полезны для сортировки, которая не потребует никакойдополнительной работы. Другими словами, мы избежим множества сравнений,т.к. для того, чтобы отсортировать объекты по возрастанию достаточно простолинейно просканировать хеш-таблицу.В принципе, всегда можно создать такую функцию, при условии, что хеш-таблица больше, чем пространство ключей. Однако, задача поиска правильнойхеш-функции нетривиальна. Разумеется, она очень сильно зависит отконкретной задачи. Кроме того, подобное ограничение на хеш-функцию можетпагубно сказаться на ее производительности. Поэтому часто прибегают киндексированию вместо поиска подобной хеш-функции, если только заранее неизвестно, что операция последовательной выборки будет частой.Минимальное идеальное хешированиеКак уже упоминалось выше, идеальная хеш-функция должна быстро работать иминимизировать число коллизий. Назовем такую функцию идеальной (perfecthash function) [12]. С такой функцией можно было бы не пользоватьсямеханизмом разрешения коллизий, т.к. каждый запрос был бы удачным. Но можноналожить еще одно условие: хеш-функция должна заполнять хеш-таблицу безпробелов. Такая функция будет называться минимальной идеальной хеш-функцией. Это идеальный случай с точки зрения потребления памяти и скоростиработы. Очевидно, что поиск таких функций – очень нетривиальная задача.Один из алгоритмов для поиска идеальных хеш-функций был предложен Р.Чичелли [13]. Рассмотрим набор некоторых слов, для которых надо составитьминимальную идеальную хеш-функцию. Пусть это будут некоторые ключевые словаязыка С++. Пусть это будет какая-то функция, которая зависит от некоегочисленного кода каждого символа, его позиции и длины. Тогда задача созданияфункции сведется к созданию таблицы кодов символов, таких, чтобы функциябыла минимальной и идеальной. Алгоритм очень прост, но занимает очень многовремени для работы. Производится полный перебор всех значений в таблице соткатом назад в случае необходимости, с целью подобрать все значения так,чтобы не было коллизий. Если взять для простоты функцию, которая складываеткоды первого и последнего символа с длиной слова (да, среди слов умышленнонет таких, которые дают коллизию), то алгоритм дает следующий результат:|Auto |21 |Double |0 |Int |15 |Struct |23 ||Break |28 |Else |12 |Long |26 |Switch |17 ||Case |1 |Enum |4 |Register|18 |Typedef |29 ||Char |2 |Extern |9 |Return |10 |Union |30 ||Const |8 |Float |27 |Short |22 |Unsigned|24 ||Continue|5 |For |20 |Signed |3 |Void |13 ||Default |7 |Goto |19 |Sizeof |25 |Volatile|31 ||Do |14 |If |16 |Static |6 |While |11 |Подробный анализ алгоритма, а также реализацию на С++ можно найти по адресу[12]. Там же описываются методы разрешения коллизий. К сожалению, эта темавыходит за рамки этой работы.Разрешение коллизийСоставление хеш-функции – это не вся работа, которую предстоит выполнитьпрограммисту, реализующему поиск на основе хеширования. Кроме этого,необходимо реализовать механизм разрешения коллизий. Как и с хеш-функциямисуществует несколько возможных вариантов, которые имеют свои достоинства инедостатки.Метод цепочекМетод цепочек – самый очевидный путь решения проблемы. В случае, когдаэлемент таблицы с индексом, который вернула хеш-функция, уже занят, к немуприсоединяется связный список. Таким образом, если для нескольких различныхзначений ключа возвращается одинаковое значение хеш-функции, то по этомуадресу находится указатель на связанный список, который содержит всезначения. Поиск в этом списке осуществляется простым перебором, т.к. приграмотном выборе хеш-функции любой из списков оказывается достаточнокоротким. Но даже здесь возможна дополнительная оптимизация. Дональд Кнут([3], стр. 558) отмечает, что возможна сортировка списков по времениобращения к элементам. С другой стороны, для повышения быстродействияжелательны большие размеры таблицы, но это приведет к ненужной трате памятина заведомо пустые элементы. На рисунке ниже показана структура хеш-таблицыи образование цепочек при возникновении коллизий. [pic]Прекрасная наглядная иллюстрация этой схемы разрешения коллизий в виде Java-апплета вместе с исходным кодом на C++ представлена по адресу [14].Открытая адресацияДругой путь решения проблемы, связанной с коллизиями, состоит в том, чтобыполностью отказаться от ссылок, просто просматривая различные записитаблицы по порядку до тех пор, пока не будет найден ключ K или пустаяпозиция [3]. Идея заключается в формулировании правила, согласно которомупо данному ключу определяется «пробная последовательность», т.е.последовательность позиций таблицы, которые должны быть просмотрены привставке или поиске ключа K. Если при поиске встречается пустая ячейка, томожно сделать вывод, что K в таблице отсутствует, т.к. эта ячейка была бызанята при вставке, т.к. алгоритм проходил ту же самую цепочку. Этот общийкласс методов назван открытой адресацией [4].Линейная адресацияПростейшая схема открытой адресации, известная как линейная адресация(линейное исследование, linear probing) использует циклическуюпоследовательность проверок h(K), h(K - 1), …, 0, M – 1, M – 2, …, h(K) + 1и описывается следующим алгоритмом ([3], стр. 562). Он выполняет поискключа K в таблице из M элементов. Если таблица не полна, а ключотсутствует, он добавляется.Ячейки таблицы обозначаются как TABLE[i], где 0 ? i < M и могут быть илипустыми, или занятыми. Вспомогательная переменная N используется дляотслеживания количества занятых узлов. Она увеличивается на 1 при каждойвставке. 1. Установить i = h(K) 2. Если TABLE[i] пуст, то перейти к шагу 4, иначе, если по этому адресу искомый, алгоритм завершается. 3. Установить i = i – 1, если i < 0, то i = i +M. Вернуться к шагу 2. 4. Вставка, т.к. поиск оказался неудачным. Если N = M – 1, то алгоритм завершается по переполнению. Иначе увеличить N, пометить ячейку TABLE[i] как занятую и установить в нее значение ключа K.Опыты показывают ([3], стр. 564), что алгоритм хорошо работает в началезаполнения таблицы, однако по мере заполнения процесс замедляется, адлинные серии проб становятся все более частыми.Квадратичная и произвольная адресацияВместо постоянного изменения на единицу, как в случае с линейнойадресацией, можно воспользоваться следующей формулой [15] h = h + a2,где a – это номер попытки. Этот вид адресации достаточно быстр ипредсказуем (он проходит всегда один и тот же путь по смещениям 1, 4, 9,16, 25, 36 и т.д.). Чем больше коллизий в таблице, тем дольше этот путь. Содной стороны, этот метод дает хорошее распределение по таблице, а с другойзанимает больше времени для просчета.Произвольная адресация использует заранее сгенерированный список случайныхчисел для получения последовательности [15]. Это дает выигрыш в скорости,но несколько усложняет задачу программиста.Адресация с двойным хешированиемЭтот алгоритм выбора цепочки очень похож на алгоритм для линейнойадресации, но он проверяет таблицу несколько иначе, используя две хеш-функции h1(K) и h2(K). Последняя должна порождать значения в интервале от 1до M – 1, взаимно простые с М. 1. Установить i = h1(K) 2. Если TABLE[i] пуст, то перейти к шагу 6, иначе, если по этому адресу искомый, алгоритм завершается. 3. Установить c = h2(K) 4. Установить i = i – c, если i < 0, то i = i +M. 5. Если TABLE[i] пуст, то переход на шаг 6. Если искомое расположено по этому адресу, то алгоритм завершается, иначе возвращается на шаг 4. 6. Вставка. Если N = M – 1, то алгоритм завершается по переполнению. Иначе увеличить N, пометить ячейку TABLE[i] как занятую и установить в нее значение ключа K.Очевидно, что этот вариант будет давать значительно более хорошеераспределение и независимые друг от друга цепочки. Однако, он несколькомедленнее из-за введения дополнительной функции.Дональд Кнут ([3], стр. 566) предлагает несколько различных вариантоввыбора дополнительной функции. Если M – простое число и h1(K) = K mod M,можно положить h2(K) = 1 + (K mod (M – 1)); однако, если M – 1 четно(другими словами, M нечетно, что всегда выполняется для простых чисел),было бы лучше положить h2(K) = 1 + (K mod (M – 2)).Здесь обе функции достаточно независимы. Гари Кнотт (Gary Knott) в 1968предложил при простом M использовать следующую функцию: h2(K) = 1, если h1(K) = 0 и h2(K) = M – h1(K) в противном случае (т.е. h1(K) > 0).Этот метод выполняется быстрее повторного деления, но приводит к увеличениючисла проб из-за повышения вероятности того, что два или несколько ключейпойдут по одному и тому же пути.Удаление элементов хеш-таблицыМногие программисты настолько слепо верят в алгоритмы, что даже не пытаютсязадумываться над тем, как они работают. Для них неприятным сюрпризомстановится то, что очевидный способ удаления записей из хеш-таблицы неработает. Например, если удалить ключ, который находится в цепочке, покоторой идет алгоритм поиска, использующий открытую адресацию, то всепоследующие элементы будут потеряны, т.к. алгоритм производит поиск допервого незанятого элемента.Вообще говоря, обрабатывать удаление можно, помечая элемент как удаленный,а не как пустой. Таким образом, каждая ячейка в таблице будет содержать ужеодно из трех значений: пустая, занятая, удаленная. При поиске удаленныеэлементы будут трактоваться как занятые, а при вставке – как пустые,соответственно.Однако, очевидно, что такой метод работает только при редких удалениях,поскольку однажды занятая позиция больше никогда не сможет стать свободной,а, значит, после длинной последовательности вставок и удалений всесвободные позиции исчезнут, а при неудачном поиске будет требоваться Мпроверок (где М, напомним, размер хеш-таблицы). Это будет достаточно долгийпроцесс, так как на каждом шаге №4 алгоритма поиска (см. раздел Адресация сдвойным хешированием) будет проверяться значение переменной i.Рассмотрим алгоритм удаления элемента i при линейной адресации. 1. Пометить TABLE[i] как пустую ячейку и установить j = i 2. i = i – 1 или i = i + M, если i стало отрицательным 3. Если TABLE[i] пуст, алгоритм завершается, т.к. нет больше элементов, о доступе к которым следует заботиться. В противном случае мы устанавливаем r = h(KEY[i]), где KEY[i] – ключ, который хранится в TABLE[i]. Это нам даст его первоначальный хеш-адрес. Если i ? r < j или если r < j < i либо j < i ? r (другими словами, если r циклически лежит между этими двумя переменным, что говорит о том, что этот элемент находится в цепочке, звено которой мы удалили выше), вернуться на шаг 1. 4. Надо переместить запись TABLE[j] = TABLE[i] и вернуться на первый шаг.Можно показать ([3], стр. 570), что этот алгоритм не вызывает сниженияпроизводительности. Однако, корректность алгоритма сильно зависит от тогофакта, что используется линейное исследование хеш-таблицы, поэтомуаналогичный алгоритм для двойного хеширования отсутствует.Данный алгоритм позволяет перемещать некоторые элементы таблицы, что можетоказаться нежелательно (например, если имеются ссылки извне на элементы хеш-таблицы). Другой подход к проблеме удаления основывается на адаптированиинекоторых идей, использующихся при сборке мусора: можно хранить количествоссылок с каждым ключом, говорящим о том, как много других ключейсталкивается с ним. Тогда при обнулении счетчика можно преобразовыватьтакие ячейки в пустые. Некоторые другие методы удаления, позволяющиеизбежать перемещения в таблице и работающие с любой хеш-технологией, былипредложены в [16].Применение хешированияОдно из побочных применений хеширования состоит в том, что оно создаетсвоего рода слепок, «отпечаток пальца» для сообщения, текстовой строки,области памяти и т. п. Такой «отпечаток пальца» может стремиться как к«уникальности», так и к «похожести» (яркий пример слепка — контрольнаясумма CRC). В этом качестве одной из важнейших областей применения являетсякриптография. Здесь требования к хеш-функциям имеют свои особенности.Помимо скорости вычисления хеш-функции требуется значительно осложнитьвосстановление сообщения (ключа) по хеш-адресу. Соответственно необходимозатруднить нахождение другого сообщения с тем же хеш-адресом. Припостроении хеш-функции однонаправленного характера обычно используютфункцию сжатия (выдает значение длины n при входных данных больше длины m иработает с несколькими входными блоками). При хешировании учитывается длинасообщения, чтобы исключить проблему появления одинаковых хеш-адресов длясообщений разной длины. Наибольшую известность имеют следующие хеш-функции[17]: MD4, MD5, RIPEMD-128 (128 бит), RIPEMD-160, SHа (160 бит). Вроссийском стандарте цифровой подписи используется разработаннаяотечественными криптографами хеш-функция (256 бит) стандарта ГОСТ Р34.11—94.Хеширование паролейНиже предполагается, что для шифрования используется 128-битный ключ.Разумеется, это не более, чем конкретный пример. Хеширование паролей –метод, позволяющей пользователям запоминать не 128 байт, то есть 256шестнадцатиричных цифр ключа, а некоторое осмысленное выражение, слово илипоследовательность символов, называющуюся паролем. Действительно, приразработке любого криптоалгоритма следует учитывать, что в половине случаевконечным пользователем системы является человек, а не автоматическаясистема. Это ставит вопрос о том, удобно, и вообще реально ли человекузапомнить 128-битный ключ (32 шестнадцатиричные цифры). На самом делепредел запоминаемости лежит на границе 8-12 подобных символов, а,следовательно, если мы будем заставлять пользователя оперировать именноключом, тем самым мы практически вынудим его к записи ключа на каком-либолистке бумаги или электронном носителе, например, в текстовом файле. Это,естественно, резко снижает защищенность системы.Для решения этой проблемы были разработаны методы, преобразующиепроизносимую, осмысленную строку произвольной длины – пароль, в указанныйключ заранее заданной длины. В подавляющем большинстве случаев для этойоперации используются так называемые хеш-функции. Хеш-функцией в данномслучае называется такое математическое или алгоритмическое преобразованиезаданного блока данных, которое обладает следующими свойствами: 1. хеш-функция имеет бесконечную область определения, 2. хеш-функция имеет конечную область значений, 3. она необратима, 4. изменение входного потока информации на один бит меняет около половины всех бит выходного потока, то есть результата хеш-функции.Эти свойства позволяют подавать на вход хеш-функции пароли, то естьтекстовые строки произвольной длины на любом национальном языке и,ограничив область значений функции диапазоном 0..2N-1, где N – длина ключав битах, получать на выходе достаточно равномерно распределенные по областизначения блоки информации – ключи.ЗаключениеХеширование, которое родилось еще в середине прошлого века, активноиспользуется в наши дни везде, где требуется произвести быструю выборкуданных. Появились новые методы хеширования, новые модификации алгоритмов,написанных ранее. По мнению Дональда Кнута ([3], стр. 586), наиболее важнымоткрытием в области хеширования со времен 70 годов, вероятно, являетсялинейное хеширование Витольда Литвина [18]. Линейное хеширование, котороене имеет ничего общего с классической технологией линейной адресации,позволяет многим хеш-адресам расти и/или выступать в поли вставляемых иудаляемых элементов. Линейное хеширование может также использоваться дляогромных баз данных, распределенных между разными узлами в сети.Разумеется, методы и сферы применения хеширования не ограничиваются тем,что представлено в этой работе. Не вдаваясь в строгий анализ эффективности,были рассмотрены только базовые, наиболее известные методы. Помимо нихможно отметить полиномиальное хеширование (М. Ханан и др., 1963),упорядоченное хеширование (О. Амбль, 1973), линейное хеширование (В.Литвин, 1980). Подробнее о методах хеширования см. [3, 6, 7, 19—22].Приложение (демонстрационная программа)В рамках выполнения данной работы была написана демонстрационная программа,которая, используя методы деления, умножения и хеширования Фибоначчи,создает хеш-таблицу и производит поиск по ней. Программа подсчитывает ипоказывает время, затраченное на каждую операцию, ведет протокол всехдействий, что позволяет сравнить разные алгоритмы по быстродействию. Вкачестве исходной базы данных используется файл data.ans, содержащий 11495записей телефонной книги одного из районов г. Воронежа с измененныминомерами телефонов.Программа предназначена исключительно для демонстрации применения некоторыхалгоритмов хеширования. Язык реализации – С++, среда разработки – VisualC++ 6.0. Программа расположена на прилагаемом компакт-диске в директорииHashing Demo. Исходный код расположен в каталоге Hashing Source. Исходнаябаза данных хранится в текстовом формате, что дает возможностьвоспользоваться ею для получения номеров, которым соответствуют некоторыезаписи в базе данных, что понадобится при тестировании программы.Список литературы: 1. Hellerman H., Digital Computer System Principles. McGraw-Hill, 1967. 2. Ершов А.П., Избранные труды., Новосибирск: «Наука», 1994. 3. Кнут Д., Искусство программирования, т.3. М.: Вильямс, 2000. 4. Peterson W.W., Addressing for Random-Access Storage // IBM Journal of Research and Development, 1957. V.1, N2. Р.130—146. 5. Morris R., Scatter Storage Techniques // Communications of the ACM, 1968. V.11, N1. Р.38—44. 6. Buchholz W., IBM Systems J., 2 (1963), 86–111 7. http://www.optim.ru/cs/2000/4/bintree_htm/hash.asp 8. Fundamenta Math. 46 (1958), 187-189 9. http://www.cs.sfu.ca/CC/354/zaiane/material/notes/Chapter11/node20.html10. http://www.ecst.csuchico.edu/~melody/courses/csci151_live/Dynamic_hash_no tes.htm11. http://planetmath.org/encyclopedia/Hashing.html12. http://www.eptacom.net/pubblicazioni/pub_eng/mphash.html13. R. Cichelli, Minimal Perfect Hashing Made Simple, Comm. ACM Vol. 23 No. 1, Jan. 1980.14. http://www2.ics.hawaii.edu/~richardy/project/hash/applet.html15. http://www.cs.uic.edu/~i201/HashingAns.pdf16. T. Gunji, E. Goto, J. Information Proc., 3 (1980), 1-1217. Чмора А., Современная прикладная криптография., М.: Гелиос АРВ, 2001.18. Litwin W., Proc. 6th International Conf. on Very Large Databases (1980), 212-22319. Кормен Т., Лейзерсон Ч., Ривест Р., Алгоритмы: построение и анализ, М.: МЦНМО, 200120. Вирт Н., Алгоритмы + структуры данных = программы, М.: Мир, 1985.21. Керниган Б., Пайк Р., Практика программирования, СПб.: Невский диалект, 2001.22. Шень А, Программирование: теоремы и задачи. М.: МЦНМО, 1995.

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

Похожие:

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

Курсовая работа по курсу «Технологии программирования» по теме «Хеширование» iconКурсовая работа (реферат) по теме: «Экозащитные техника и технологии»

Курсовая работа по курсу «Технологии программирования» по теме «Хеширование» iconКурсовая работа по курсу "статистика" по теме "Статистическая сводка. Группировка таблицы."

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

Курсовая работа по курсу «Технологии программирования» по теме «Хеширование» iconКурсовая работа по теме: Избирательные технологии в современной России....

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

Курсовая работа по курсу «Технологии программирования» по теме «Хеширование» iconРеферат скачан с сайта allreferat wow ua Оценка рекреационных ресурсов...

Курсовая работа по курсу «Технологии программирования» по теме «Хеширование» iconТема Задачи курса «Основы алгоритмических языков и программирования»
Он изучается в 1 и 2 семестрах. Включает в себя лекции, лабораторные работы и самостоятельную работу вне аудитории. В процессе изучения...

Курсовая работа по курсу «Технологии программирования» по теме «Хеширование» iconКурсовая работа По предмету: «Технология социальной работы» По теме:...

Курсовая работа по курсу «Технологии программирования» по теме «Хеширование» iconКурсовая работа по дисциплине «Объектно-ориентированное программирование»
Объектно-ориентированное программирование это метод программирования, развивающий принципы структурного программирования и основанный...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
uchebilka.ru
Главная страница


<