Категория
Информатика
Тип
реферат
Страницы
5 стр.
Дата
09.10.2008
Формат файла
.rtf — Rich Text Format (Wordpad)
Архив
19050.zip — 25.13 kb
  • poisk-xesh-funkcii_19050_1.rtf — 136.76 Kb
  • Readme_docus.me.txt — 125 Bytes
Оцените работу
Хорошо  или  Плохо


Текст работы

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



Ваше мнение



CAPTCHA