Хеширование
Категория реферата: Рефераты по информатике, программированию
Теги реферата: борьба реферат, курсовые
Добавил(а) на сайт: Ермил.
Предыдущая страница реферата | 1 2 3 4 5 6 | Следующая страница реферата
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, SHA (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
записей телефонной книги одного из районов г. Воронежа с измененными
номерами телефонов.
Программа предназначена исключительно для демонстрации применения некоторых
алгоритмов хеширования. Язык реализации – С++, среда разработки – Visual
C++ 6.0. Программа расположена на прилагаемом компакт-диске в директории
Hashing Demo. Исходный код расположен в каталоге Hashing Source. Исходная
база данных хранится в текстовом формате, что дает возможность
воспользоваться ею для получения номеров, которым соответствуют некоторые
записи в базе данных, что понадобится при тестировании программы.
Список литературы:
1. Hellerman H., Digital Computer System Principles. McGraw-Hill, 1967.
Рекомендуем скачать другие рефераты по теме: изложение 8 класс по русскому, оформление доклада.
Предыдущая страница реферата | 1 2 3 4 5 6 | Следующая страница реферата