Библиотека Рефераты Курсовые Дипломы Поиск
Библиотека Рефераты Курсовые Дипломы Поиск
сделать стартовой добавить в избранное
Кефирный гриб на сайте za4eti.ru

Компьютеры, Программирование Компьютеры, Программирование     Программирование, Базы данных Программирование, Базы данных

Хеширование

Пакеты с замком "Extra зиплок" (гриппер), комплект 100 штук (150x200 мм).
Быстрозакрывающиеся пакеты с замком "зиплок" предназначены для упаковки мелких предметов, фотографий, медицинских препаратов и
148 руб
Раздел: Гермоупаковка
Ручка "Помада".
Шариковая ручка в виде тюбика помады. Расцветка корпуса в ассортименте, без возможности выбора!
25 руб
Раздел: Оригинальные ручки
Крючки с поводками Mikado SSH Fudo "SB Chinu", №4BN, поводок 0,22 мм.
Качественные Японские крючки с лопаткой. Крючки с поводками – готовы к ловле. Высшего качества, исключительно острые японские крючки,
58 руб
Раздел: Размер от №1 до №10

Министерство Образования РФ Воронежский государственный университет Факультет Компьютерных наук Кафедра программирования и информационных технологий Курсовая работа по курсу «Технологии программирования» по теме «Хеширование» Выполнил: студент 3его курса Шадчнев Евгений Проверил: доцент каф. ПиИТ Хлебостроев Виктор Григорьевич Воронеж 2003 Содержание Введение4 Хеш-функции5 Метод деления5 Метод умножения (мультипликативный)6 Динамическое хеширование6 Расширяемое хеширование (ex e dible hashi g)8 Функции, сохраняющие порядок ключей (Order preservi g hash fu c io s)9 Минимальное идеальное хеширование9 Разрешение коллизий11 Метод цепочек11 Открытая адресация11 Линейная адресация12 Квадратичная и произвольная адресация12 Адресация с двойным хешированием12 Удаление элементов хеш-таблицы13 Применение хеширования14 Хеширование паролей14 Заключение16 Приложение (демонстрационная программа)16 Список литературы:17 Введение С хешированием мы сталкиваемся едва ли не на каждом шагу: при работе с браузером (список Web-ссылок), текстовым редактором и переводчиком (словарь), языками скриптов (Perl, Py ho , PHP и др.), компилятором (таблица символов). По словам Брайана Кернигана, это «одно из величайших изобретений информатики». Заглядывая в адресную книгу, энциклопедию, алфавитный указатель, мы даже не задумываемся, что упорядочение по алфавиту является не чем иным, как хешированием. Хеширование есть разбиение множества ключей (однозначно характеризующих элементы хранения и представленных, как правило, в виде текстовых строк или чисел) на непересекающиеся подмножества (наборы элементов), обладающие определенным свойством. Это свойство описывается функцией хеширования, или хеш-функцией, и называется хеш-адресом. Решение обратной задачи возложено на хеш-структуры (хеш-таблицы): по хеш-адресу они обеспечивают быстрый доступ к нужному элементу. В идеале для задач поиска хеш-адрес должен быть уникальным, чтобы за одно обращение получить доступ к элементу, характеризуемому заданным ключом (идеальная хеш-функция). Однако, на практике идеал приходится заменять компромиссом и исходить из того, что получающиеся наборы с одинаковым хеш-адресом содержат более одного элемента. Термин «хеширование» (hashi g) в печатных работах по программированию появился сравнительно недавно (1967 г., ), хотя сам механизм был известен и ранее. Глагол «hash» в английском языке означает «рубить, крошить». Для русского языка академиком А.П. Ершовым был предложен достаточно удачный эквивалент — «расстановка», созвучный с родственными понятиями комбинаторики, такими как «подстановка» и «перестановка». Однако он не прижился. Как отмечает Дональд Кнут , идея хеширования впервые была высказана Г.П. Ланом при создании внутреннего меморандума IBM в январе 1953 г. с предложением использовать для разрешения коллизий хеш-адресов метод цепочек. Примерно в это же время другой сотрудник IBM – Жини Амдал – высказала идею использования открытую линейную адресацию. В открытой печати хеширование впервые было описано Арнольдом Думи (1956), указавшим, что в качестве хеш-адреса удобно использовать остаток от деления на простое число.

А. Думи описывал метод цепочек для разрешения коллизий, но не говорил об открытой адресации. Подход к хешированию, отличный от метода цепочек, был предложен А.П. Ершовым (1957, ), который разработал и описал метод линейной открытой адресации. Среди других исследований можно отметить работу Петерсона (1957, ). В ней реализовывался класс методов с открытой адресацией при работе с большими файлами. Петерсон определил открытую адресацию в общем случае, проанализировал характеристики равномерного хеширования, глубоко изучил статистику использования линейной адресации на различных задачах. В 1963 г. Вернер Букхольц опубликовал наиболее основательное исследование хеш-функций. К концу шестидесятых годов прошлого века линейная адресация была единственным типом схемы открытой адресации, описанной в литературе, хотя несколькими исследователями независимо была разработана другая схема, основанная на неоднократном случайном применении независимых хеш-функции (, стр. 585). В течение нескольких последующих лет хеширование стало широко использоваться, хотя не было опубликовано никаких новых работ. Затем Роберт Моррис обширный обзор по хешированию и ввел термин «рассеянная память» (sca er s orage). Эта работа привела к созданию открытой адресации с двойным хешированием. Далее будут рассмотрены основные виды хеш-функций и некоторые их модификации, методы разрешения коллизий, проблемы удаления элементов из хеш-таблицы, а также некоторые варианты применения хеширования. Хеш-функции Хеш-функция – это некоторая функция h(K), которая берет некий ключ K и возвращает адрес, по которому производится поиск в хеш-таблице, чтобы получить информацию, связанную с K. Например, K – это номер телефона абонента, а искомая информация – его имя. Функция в данном случае нам точно скажет, по какому адресу найти искомое. Пример с телефонным справочником иллюстрируется демонстрационной программой на прилагаемом компакт-диске. Коллизия – это ситуация, когда h(K1) = h(K2), в то время как K1 & e; K2. В этом случае, очевидно, необходимо найти новое место для хранения данных. Очевидно, что количество коллизий необходимо минимизировать. Методикам разрешения коллизий будет посвящен отдельный раздел ниже. Хорошая хеш-функция должна удовлетворять двум требованиям: ее вычисление должно выполняться очень быстро; она должна минимизировать число коллизий. Итак, первое свойство хорошей хеш-функции зависит от компьютера, а второе – от данных. Если бы все данные были случайными, то хеш-функции были бы очень простые (несколько битов ключа, например). Однако на практике случайные данные встречаются крайне редко, и приходится создавать функцию, которая зависела бы от всего ключа. Теоретически невозможно определить хеш-функцию так, чтобы она создавала случайные данные из реальных неслучайных файлов. Однако на практике реально создать достаточно хорошую имитацию с помощью простых арифметических действий. Более того, зачастую можно использовать особенности данных для создания хеш-функций с минимальным числом коллизий (меньшим, чем при истинно случайных данных) . Возможно, одним из самых очевидных и простых способов хеширования является метод середины квадрата, когда ключ возводится в квадрат и берется несколько цифр в середине.

Здесь и далее предполагается, что ключ сначала приводится к целому числу, для совершения с ним арифметических операций. Однако такой способ хорошо работает до момента, когда нет большого количества нолей слева или справа. Многочисленные тесты показали хорошую работу двух основных типов хеширования, один из которых основан на делении, а другой на умножении. Впрочем, это не единственные методы, которые существуют, более того, они не всегда являются оптимальными. Метод деления Метод деления весьма прост – используется остаток от деления на M: h(K) = K mod M Надо тщательно выбирать эту константу. Если взять ее равной 100, а ключом будет случить год рождения, то распределение будет очень неравномерным для ряда задач (идентификация игроков юношеской бейсбольной лиги, например). Более того, при четной константе значение функции будет четным при четном K и нечетным - при нечетном, что приведет к нежелательному результату. Еще хуже обстоят дела, если M – это степень счисления компьютера, поскольку при этом результат будет зависеть только от нескольких цифр ключа справа. Точно также можно показать, что M не должно быть кратно трем, поскольку при буквенных ключах два из них, отличающиеся только перестановкой букв, могут давать числовые значения с разностью, кратной трем (см. , стр. 552). Приведенные рассуждения приводят к мысли, что лучше использовать простое число. В большинстве случаев подобный выбор вполне удовлетворителен. Другой пример – ключ, являющийся символьной строкой С . Хеш-функция отображает эту строку в целое число посредством суммирования первого и последнего символов и последующего вычисления остатка от деления на 101 (размер таблицы). Эта хеш-функция приводит к коллизии при одинаковых первом и последнем символах строки. Например, строки «s ar » и «sla » будут отображаться в индекс 29. Так же ведет себя хеш-функция, суммирующая все символы строки. Строки «bad» и «dab» преобразуются в один и тот же индекс. Лучшие результаты дает хеш-функция, производящая перемешивание битов в символах. На практике, метод деления – самый распространенный . Метод умножения (мультипликативный) Для мультипликативного хеширования используется следующая формула: h(K) = Здесь производится умножение ключа на некую константу С, лежащую в интервале . После этого берется дробная часть этого выражения и умножается на некоторую константу M, выбранную таким образом, чтобы результат не вышел за границы хеш-таблицы. Оператор возвращает наибольшее целое, которое меньше аргумента. Если константа С выбрана верно, то можно добиться очень хороших результатов, однако, этот выбор сложно сделать. Дональд Кнут (см. , стр. 553) отмечает, что умножение может иногда выполняться быстрее деления. Мультипликативный метод хорошо использует то, что реальные файлы неслучайны. Например, часто множества ключей представляют собой арифметические прогрессии, когда в файле содержатся ключи {K, K d, K 2d, , K d}. Например, рассмотрим имена типа {PAR 1, PAR 2, , PAR }. Мультипликативный метод преобразует арифметическую прогрессию в приближенно арифметическую прогрессию h(K), h(K d), h(K 2d), различных хеш-значений, уменьшая число коллизий по сравнению со случайной ситуацией.

В истории криптографии много случаев, когда слабости находили и в новых схемах известных авторов, и в алгоритмах, успевших получить распространение. Например, в 1996 году одна из ранних версий протокола SSL была взломана именно из-за слабостей в генераторе случайных чисел. Совсем недавно были обнаружены криптографические слабости в PRNG операционных систем Linux и FreeBSD, открытых для анализа. По этой причине многие разработчики средств защиты благосклонно встретили инициативу NIST, американского Института стандартов и технологий, подготовившего и опубликовавшего большой, на 130 страниц документ под названием NIST Special Publication 800-90, целиком посвященный генераторам псевдослучайных чисел. В этом документе они именуются DRBG (Deterministic Random Bit Generators), и там содержатся описания четырех изученных и рекомендуемых к применению генераторов. Все четыре генератора построены на основе уже существующих криптографических примитивов, что принято считать плюсом. Один на основе хеш-функций, другой на основе HMAC (хешированного кода аутентификации сообщения), третий на основе блочных шифров, четвертый - на эллиптических кривых

1. Метод расчета скейлинговых констант Фейгенбаума для одномерных дискретных отображений по точкам сверхустойчивых циклов

2. Метод конечных элементов

3. Изучение миксомицетов среднего Урала, выращенных методом влажных камер

4. Методы исследования в цитологии

5. МЕТОДЫ ИЗУЧЕНИЯ ЭВОЛЮЦИИ ЧЕЛОВЕКА

6. Методологическое значение сравнительного метода в зоологических исследованиях
7. Метод радиоавтографии в биологии
8. Виды стихийных бедствий и методы борьбы с ними

9. Статистика населения. Методы анализа динамики и численности и структуры населения

10. Гамма – каротаж. Физические основы метода

11. Метод Бокового каротажа

12. Методы выделения мономинеральных фракций

13. Основні методи боротьби з інфляцією

14. Предмет, метод, источники Административного права

15. Методы осуществления государственной власти

16. Метод гражданско правового регулирования

Универсальное жидкое средство для стирки детского белья "Burti liquid Baby", 1.5 литра.
Разработан специально для детского белья. Исключительная эффективность стирки и бережный уход за бельем из-за содержания натурального
601 руб
Раздел: Для стирки детских вещей
Шкатулка ювелирная "Moretto", 2 яруса, со стразами, 18x13x10 см.
Оригинальная шкатулка сохранит ваши ювелирные изделия в первозданном виде. С ней вы сможете внести в интерьер частичку
1632 руб
Раздел: Шкатулки для украшений
Коляска-трость Еду-Еду (цвет: серый/фиолетовый, арт. E-103).
Коляска-трость E-103 - простая, стильная и легкая коляска. Особенности: - Стильный и яркий дизайн; - Надёжная стальная рама; - Плавающие
1637 руб
Раздел: Коляски-трость

17. Формы и методы государственного регулирования экономики в Казахстане

18. Математические методы и модели в конституционно-правовом исследовании

19. Методы комплексной оценки хозяйственно-финансовой деятельности

20. Цикл-метод обучения. (Методика преподавания эстонского языка)

21. Специфика преподавания иностранного языка и метод проектов

22. Естественная и гуманитарная культуры. Научный метод
23. Русская здрава (методы оздоровления на Руси)
24. Методы исследования литературы

25. Метод комплексного археолого-искусствоведческого анализа могильников

26. Конвертер программы с подмножества языка Си в Паскаль с использованием LL(1) метода синтаксического анализа (выражения)

27. Методы компьютерной обработки статистических данных. Проверка однородности двух выборок

28. Методичка по Internet Explore

29. Шифрование по методу UUE

30. Разработка методов определения эффективности торговых интернет систем

31. Алгоритм Кнута-Морриса-Пратта

32. Метод деформируемого многогранника

Набор цветных карандашей "Noris Club", акварельные, 36 цветов, с кистью.
Детские цветные акварельные карандаши в картонной коробке. Серия «Noris Club» предназначена для использования детьми. Специальное защитное
859 руб
Раздел: Акварельные
Мозаика.
50 фишек. Размер поля: 24 х 35 см. Размер фишки: 40 х 45 х 14 мм. Материал: полипропилен.
450 руб
Раздел: Пластмассовая
Блюдо для блинов "Спелая смородина", 24,5x28x3 см.
Блюдо для блинов. Размер: 24,5x28x3 см. Материал: фарфор.
619 руб
Раздел: Прочее

33. Создание клиентских частей SQL БД под ОС Windows`95 и WindowsNT

34. Обучение начальных курсов методам программирования на языке Turbo Pascal

35. Принципы реализации машин БД

36. Модифицированный симплекс-метод с мультипликативным представлением матриц

37. Методы приобретения знаний в интеллектуальных системах

38. Билеты, решения и методичка по Информатике (2.0)
39. Вычисление определённого интеграла с помощью метода трапеций на компьютере
40. Интегрирование методом Симпсона

41. Лекции по теории проектирования баз данных (БД)

42. Пример создания БД "Материалы" с помощью Access

43. Компьютерные вирусы, типы вирусов, методы борьбы с вирусами

44. Анализ криптостойкости методов защиты информации в операционных системах Microsoft Window 9x

45. Парольные методы защиты информации в компьютерных системах от несанкционированного доступа

46. Лабораторная работа №7 по "Основам теории систем" (Решение задачи коммивояжера методом ветвей и границ)

47. Лабораторная работа №6 по "Основам теории систем" (Решение задачи о ранце методом ветвей и границ)

48. Решение задач - методы спуска

Копилка "Свинка с мелом", 20x15x16 см, арт. 223018.
Копилка поможет Вам наконец-то собрать требуемую сумму для покупки долгожданной вещицы. Регулярно удалять пыль сухой, мягкой
695 руб
Раздел: Копилки
Шкатулка для ювелирных украшений, 20x13x11 см, арт. 88253.
Шкатулка сохранит ваши ювелирные изделия в первозданном виде. С ней вы сможете внести в интерьер частичку элегантности. Беречь от
363 руб
Раздел: Шкатулки для украшений
Чековая книжка желаний "Для Неё".
Этим подарком женщина обещает исполнить несколько заветных желаний мужчины по его выбору. В каждой книжке содержится 12 листов с
390 руб
Раздел: Прочее

49. Решение смешанной задачи для уравнения гиперболического типа методом сеток

50. Решение систем дифференциальных уравнений методом Рунге-Куты 4 порядка

51. Решение систем линейных алгебраических уравнений методом Гаусса и Зейделя

52. Использование численных методов для решения дифуpов (2-го порядка) (, демонстрация применения интерполяции в среде MATHCAD-а)

53. Вычисление определенного интеграла методами трапеций и средних прямоугольников

54. Решение нелинейного уравнения методом касательных
55. Методы корреляционного и регрессионного анализа в экономических исследованиях
56. Современные криптографические методы

57. Математические методы в организации транспортного процесса

58. Метод последовательных уступок (Теория принятия решений)

59. Построение графика функции различными методами (самостоятельная работа учащихся)

60. Краткая методичка по логике

61. Методы решения систем линейных неравенств

62. Вычисление двойных интегралов методом ячеек

63. Методы обучения математике в 10 -11 класах

64. Решение задач линейной оптимизации симплекс – методом

Чайник эмалированный ЕМ-25001/41 "Сицилия", 2,5 л (со свистком).
Объем: 2,5 л. Внешнее высокопрочное японское трехслойное эмалевое покрытие. Внутреннее эмалевое покрытие, устойчивое к воздействию пищевых
979 руб
Раздел: Чайники эмалированные
Подставка для ручек с часами, 11,8х10,2х5,2 см.
Подставка для ручек с часами. Материал корпуса: пластик. Механизм: электронный. ЖК дисплей. Дополнительные функции: часы, будильник,
540 руб
Раздел: Подставки, лотки для бумаг, футляры
Туалетная бумага "Zewa Deluxe" (без запаха), трехслойная, 12 рулонов.
Подарите себе удовольствие от ежедневного ухода за собой. "Zewa Deluxe" с новыми впитывающими «подушечками» деликатно
343 руб
Раздел: Бумага туалетная

65. Приближённые методы решения алгебраического уравнения

66. Решение дифференциальных уравнений 1 порядка методом Эйлера

67. Методы расчета электрических полей

68. Метод Алексея Юрьевича Виноградова для решения краевых задач

69. Решение задач на построение сечений в многогранниках методом следов

70. Новый метод «дополнительных краевых условий» Алексея Юрьевича Виноградова для краевых задач
71. Лазерные методы диагностики. Термография
72. Объективные и субъективные признаки усталости, утомления и переутомления, их причины, методы устранения и профилактика

73. Дополнительные методы обследования легочных больных. Основные синдромы при заболеваниях легких

74. Хламидиоз. Методы определения/диагностики

75. Предмет, метод, содержание cудебной медицины

76. Методы оценки кровопотери в акушерстве

77. Метод Фолля

78. Некоторые методы лечения переломов длинных трубчатых костей

79. Ретроспективный cанитарно – эпидемиологический анализ по определению связи между заболеваемостью населения ОКИ и факторами внешней среды по эпидемиологически значимым объектам (с использованием статистического метода ранговой корреляции ) за 2000 –2002 г

80. Сравнительная характеристика методов лабораторной диагностики трихомоноза

Статуэтка "Римская богиня счастья и удачи - Фортуна", 20 см, арт. 127548.
Статуэтка "Римская богиня счастья и удачи - Фортуна" - это отличный вариант подарка. Красивый продуманный дизайн и высокое
696 руб
Раздел: Статуэтки интерьерные
Ранец жесткокаркасный для начальной школы "Динозавр", 18 литров, 36x26x14 см.
Ранец жесткокаркасный для начальной школы, вместительное основное отделение и дополнительные карманы, светоотражающие полосы. Форма ранца:
1247 руб
Раздел: Без наполнения
Салатники "Хлеб", 2 штуки.
Салатники, 2 штуки. Диаметр: 13,5/16,5 см. Высота: 6/7 см. Объем: 350/650 мл. Материал: керамика.
362 руб
Раздел: Наборы

81. Продвинутые методы Ганемана. LМ-потенции: теория и практика

82. Воспалительные заболевания женских половых органов неспецифической этиологии, клиника, диагностика, методы лечения

83. Предмет, понятие, метод и система криминологии

84. Характеристики методов расследования преступлений, связанных с квалифицированным вымогательством

85. Понятие и основные методы исследовательской фотографии

86. Загрязнение водных ресурсов и методы очистки
87. Методы очистки промышленных газовых выбросов
88. Мониторинг загрязнения водной среды реки Херота с помощью методов биоиндикации

89. Экология. Предмет и методы

90. Визуальные методы оценки цикличности в ходе метеоэлементов

91. Изучение экологического состояния территории Большеземельской тундры с использованием методов дистанционного мониторинга

92. Игровые методы в логопедической практике

93. Компьютерные технологии как фактор эволюции форм и методов обучения

94. Методы изучения музыкальных произведений крупной формы в старших классах общеобразовательной школы

95. Наркомания школьников, методы профилактики

96. Средства и методы педагогического воздействия на личность

Этажерка "Люкс-5" с сидением, 3-х ярусная.
Удобная, компактная и функциональная этажерка для обуви с ящиком «Люкс 5» выполнена из металлических трубок с антикоррозионным
1624 руб
Раздел: Полки напольные, стеллажи
Ракета "Мир".
Модель 2018 года. Боковые разгонные блоки отделяются одновременно при перемещении оранжевого кольца вверх, следующая ступень также
412 руб
Раздел: Космический транспорт
Пакеты фасовочные, 10(+8)x27 см (1000 штук).
Область применения: расфасовка, упаковка продуктов питания и товаров народного потребления как на производстве, так и в быту. Размер:
306 руб
Раздел: Пакеты для продуктов

97. Эффективные методы изучения иностранных языков

98. Использование различных методов обучения с целью активизации познавательной деятельности на уроках технологии

99. Игровые методы обучения


Поиск Рефератов на сайте za4eti.ru Вы студент, и у Вас нет времени на выполнение письменных работ (рефератов, курсовых и дипломов)? Мы сможем Вам в этом помочь. Возможно, Вам подойдет что-то из ПЕРЕЧНЯ ПРЕДМЕТОВ И ДИСЦИПЛИН, ПО КОТОРЫМ ВЫПОЛНЯЮТСЯ РЕФЕРАТЫ, КУРСОВЫЕ И ДИПЛОМНЫЕ РАБОТЫ. 
Вы можете поискать нужную Вам работу в КОЛЛЕКЦИИ ГОТОВЫХ РЕФЕРАТОВ, КУРСОВЫХ И ДИПЛОМНЫХ РАБОТ, выполненных преподавателями московских ВУЗов за период более чем 10-летней работы. Эти работы Вы можете бесплатно СКАЧАТЬ.