Категория
Информатика
Тип
реферат
Страницы
7 стр.
Дата
15.03.2009
Формат файла
.doc — Microsoft Word
Архив
20416.zip — 181.55 kb
  • xesh-funkcii_20416_1.DOC — 760.5 Kb
  • Readme_docus.me.txt — 125 Bytes
Рейтинг
10  из 10
Оценок
1
Оцените работу
Хорошо  или  Плохо


Текст работы

ХЕШИРОВАНИЕ
До сих пор мы рассматривали методы поиска, основанные на сравнении данного аргумента K с имеющимися в таблице ключами или на использовании его цифр для управления процессом разветвления. Но есть и третий путь: не рыскать вокруг да около, а произвести над K некоторое арифметическое вычисление и получить функцию f(K), указывающую адрес в таблице, где хранится K и ассоциированная с ним информация.
К сожалению, находить подобные функции f(K) довольно сложно.
Функции, дающие неповторяющиеся значения, неожиданно редки даже в случае довольно большой таблицы. Например, знаменитый парадокс дней рождения утверждает, что, если в комнате присутствует не менее 23 человек, имеется хороший шанс на то, что у двух из них совпадет день рождения! Иными словами, если мы выбираем случайную функцию, отображающую 23 ключа в 365-элементную таблицу, то с вероятностью 0.4927 (менее половины) все ключи попадут в разные места.
Разумеется, такой метод имеет существенный недостаток, ибо содержимое таблицы должно быть известно заранее; добавление хотя бы одного ключа может все испортить, и нам придется начинать фактически на пустом месте.
Можно получить гораздо более гибкий метод, если отбросить идеюоднозначности, допуская совпадения значений f(K) для различныхаргументов, и использовать особый метод разрешения неопределенности после вычисления f(K).
Наши рассмотрения приводят к широко известному классу методов, обычно называемых хешированием или рассеянной памятью. Английскийглагол "to hash" имеет смысл нарезать, раскрошить что-либо или сделать из этого месиво; идея хеширования состоит в том, чтобы взять некоторые характеристики ключа и использовать полученную частичную информацию в качестве основы поиска. Мы вычисляем хеш-функцию h(K) и берем это значение



Ваше мнение



CAPTCHA