ХЕШИРОВАНИЕ

До сих пор мы рассматривали методы поиска, основанные на сравнении данного аргумента 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