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


Текст работы

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



Ваше мнение



CAPTCHA