Prolog

  • 22 марта 2012 г.
  • 1817 Слова
ХЕШИРОВАНИЕ
До сих пор мы рассматривали методы поиска, основанные на сравнении данного аргумента 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 ←K.
rAX ←AK. (5)
rAX ← AK mod w.
Сдвиг rAX на m битов влево.

Результат получается в регистре A.
Одна из привлекательных черт мультипликативной схемы состоит в том, что в (5) не происходит потери информации; мы могли бы вновь найти K, зная лишь содержимое rAX после выполнения инструкций (5). Дело в том, что A взаимно просто с w, и припомощи алгоритма Евклида можно найти Константу A': AA' mod w = 1 ; отсюда следует, что K=(A'(AK mod w)) mod w. Иными словами,
K1 ≠ K2 влечет f(K1 ) ≠ f(K2 ). (6)
Конечно, f(K)принимает значения в диапазоне от 0 до w-1 и не является сколько-нибудь подходящей хеш-функцией, но она может быть очень полезной в качестве рассеивающей функции, а именно функции,...
tracking img