Бесплатные рефераты


В мире
Календарь новостей
« Дек.2017»
Пн.Вт.Ср.Чт.Пт.Сб.Вс.
    123
45678910
11121314151617
18192021222324
25262728293031
ВНИМАНИЕ!!!
УВАЖАЕМЫЕ ПОЛЬЗОВАТЕЛИ!!!
Сайт поменял владельца и на нём грядут большие перемены.
Убедительная просьба не пользоваться покупкой рефератов через смс.
ДАННЫЙ СЕРВИС БОЛЬШЕ НЕ РАБОТАЕТ
Стоит вопрос об его удалении, дабы сделать рефераты бесплатными. Извините за неудобство и спасибо за понимание
Поиск реферата

Реферат, курсовая, контрольная, доклад на тему: Хеш-функции

ВНИМАНИЕ! Работа на этой странице представлена для Вашего ознакомления в текстовом (сокращенном) виде. Для того, чтобы получить полностью оформленную работу в формате Word, со всеми сносками, таблицами, рисунками (вместо pic), графиками, приложениями, списком литературы и т.д., необходимо скачать работу.

ХЕШИРОВАНИЕ

До сих пор мы рассматривали методы поиска, основанные на сравнении данного аргумента K с имеющимися в таблице ключами или на использовании его цифр для управления процессом разветвления. Но есть и третий путь: не рыскать вокруг да около, а произвести над K некоторое арифметическое вычисление и получить функцию f(K), указывающую адрес в таблице, где хранится K и ассоциированная с ним информация.

К сожалению, находить подобные функции f(K) довольно сложно.
Функции, дающие неповторяющиеся значения, неожиданно редки даже в случае довольно большой таблицы. Например, знаменитый парадокс дней рождения утверждает, что, если в комнате присутствует не менее 23 человек, имеется хороший шанс на то, что у двух из них совпадет день рождения! Иными словами, если мы выбираем случайную функцию, отображающую 23 ключа в 365- элементную таблицу, то с вероятностью 0.4927 (менее половины) все ключи попадут в разные места.

Разумеется, такой метод имеет существенный недостаток, ибо содержимое таблицы должно быть известно заранее; добавление хотя бы одного ключа может все испортить, и нам придется начинать фактически на пустом месте.

Можно получить гораздо более гибкий метод, если отбросить идею однозначности, допуская совпадения значений f(K) для различных аргументов, и использовать особый метод разрешения неопределенности после вычисления f(K).

Наши рассмотрения приводят к широко известному классу методов, обычно называемых хешированием или рассеянной памятью. Английский глагол "to hash" имеет смысл нарезать, раскрошить что-либо или сделать из этого месиво; идея хеширования состоит в том, чтобы взять некоторые характеристики ключа и использовать полученную частичную информацию в качестве основы поиска. Мы вычисляем хеш-функцию h(K) и берем это значение в качестве адреса начала поиска.

Парадокс дней рождения служит для нас предостережением, что, вероятно, найдутся различные ключи Ki ( Kj , для которых h(Ki)=h(Kj). Подобное событие называется коллизией; для разрешения коллизий были разработаны интересные подходы. Чтобы использовать рассеянную таблицу, программист должен принять два почти независимых решения: он должен выбрать хеш- функцию h(K) и метод разрешения коллизий. Эти два аспекта задачи поиска мы и рассмотрим по очереди.

Хеш-функции. Для определенности будем полагать, что хеш-функция h(K) имеет не более M различных значений и, что эти значения удовлетворяют условию

0( h(K) h(K) вычисляется следующим образом rX < K rA < 0 (3) rA < K mod 1009

Мультипликативную схему хеширования также легко реализовать, но несколько труднее описать, так как нужно представить, что мы работаем с дробями, а не с целыми числами. Пусть w есть размер машинного слова; целое число A можно рассматривать как дробь A/w, если мысленно поставить десятичную (или двоичную) точку слева от машинного слова, в котором записано A. Метод состоит в том, чтобы выбрать A взаимно простым с w и положить h(K)=[M(((A/w)K) mod 1)]. (4)

В двоичной системе M обычно берут равным степени двойки, так что h(K) состоит из старших битов правой значащей половины произведения AK. В двоичном виде при M=2m мультипликативная хеш-функция вычисляется так:

rA

ВНИМАНИЕ! Работа на этой странице представлена для Вашего ознакомления в текстовом (сокращенном) виде. Для того, чтобы получить полностью оформленную работу в формате Word, со всеми сносками, таблицами, рисунками (вместо pic), графиками, приложениями, списком литературы и т.д., необходимо А можно заказать оригинальный реферат
Опубликовано: 20.08.10 | [ + ]   [ - ]  
Просмотров: 95
Загрузок: 0
Рекомендуем
{dnmbottom}
БАНК РЕФЕРАТОВ содержит более 70 000 рефератов, курсовых, контрольных работ, сочинений и шпаргалок.