Реферат: Хеширование

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

Составление хеш-функции – это не вся работа, которую предстоит выполнить программисту, реализующему поиск на основе хеширования. Кроме этого, необходимо реализовать механизм разрешения коллизий. Как и с хеш-функциями существует несколько возможных вариантов, которые имеют свои достоинства и недостатки.

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

Метод цепочек – самый очевидный путь решения проблемы. В случае, когда элемент таблицы с индексом, который вернула хеш-функция, уже занят, к нему присоединяется связный список. Таким образом, если для нескольких различных значений ключа возвращается одинаковое значение хеш-функции, то по этому адресу находится указатель на связанный список, который содержит все значения. Поиск в этом списке осуществляется простым перебором, т.к. при грамотном выборе хеш-функции любой из списков оказывается достаточно коротким. Но даже здесь возможна дополнительная оптимизация. Дональд Кнут ([3], стр. 558) отмечает, что возможна сортировка списков по времени обращения к элементам. С другой стороны, для повышения быстродействия желательны большие размеры таблицы, но это приведет к ненужной трате памяти на заведомо пустые элементы. На рисунке ниже показана структура хеш-таблицы и образование цепочек при возникновении коллизий.

Прекрасная наглядная иллюстрация этой схемы разрешения коллизий в виде 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, 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.
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.html

10.  http://www.ecst.csuchico.edu/~melody/courses/csci151_live/Dynamic_hash_notes.htm

11.  http://planetmath.org/encyclopedia/Hashing.html

12.  http://www.eptacom.net/pubblicazioni/pub_eng/mphash.html

13.  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.html

15.  http://www.cs.uic.edu/~i201/HashingAns.pdf

16.  T. Gunji, E. Goto, J. Information Proc., 3 (1980), 1-12

17.  Чмора А., Современная прикладная криптография., М.: Гелиос АРВ, 2001.

18.  Litwin W., Proc. 6th International Conf. on Very Large Databases (1980), 212-223

19.  Кормен Т., Лейзерсон Ч., Ривест Р., Алгоритмы: построение и анализ, М.: МЦНМО, 2001

20.  Вирт Н., Алгоритмы + структуры данных = программы, М.: Мир, 1985.

21.  Керниган Б., Пайк Р., Практика программирования, СПб.: Невский диалект, 2001.

22.  Шень А, Программирование: теоремы и задачи. М.: МЦНМО, 1995.