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

Вообще говоря, обрабатывать удаление можно, помечая элемент как удаленный, а не как пустой. Таким образом, каждая ячейка в таблице будет содержать уже одно из трех значений: пустая, занятая, удаленная. При поиске удаленные элементы будут трактоваться как занятые, а при вставке – как пустые, соответственно.

Однако, очевидно, что такой метод работает только при редких удалениях, поскольку однажды занятая позиция больше никогда не сможет стать свободной, а, значит, после длинной последовательности вставок и удалений все свободные позиции исчезнут, а при неудачном поиске будет требоваться М проверок (где М, напомним, размер хеш-таблицы). Это будет достаточно долгий процесс, так как на каждом шаге №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..2^N-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. 6^th International Conf. on Very Large Databases (1980), 212-223

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

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

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

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