Хеширование

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

  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/cs/2000/4/bintree_htm/hash.asp

  8. Fundamenta Math. 46 (1958), 187-189

  9. cs.sfu.ca/CC/354/zaiane/material/notes/Chapter11/node20.html

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

  11. planetmath/encyclopedia/Hashing.html

  12. eptacom/pubblicazioni/pub_eng/mphash.html

  13. R. Cichelli, Minimal Perfect Hashing Made Simple, Comm. ACM Vol. 23 No. 1, Jan. 1980.

  14. www2.ics.hawaii.edu/~richardy/project/hash/applet.html

  15. 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.

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: