ХЕШИРОВАНИЕ
До сих пор мы рассматривали методы поиска, основанные на сравнении
данного аргумента 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
Мультипликативную схему хеширования также легко реализовать, но
несколько труднее описать, так как нужно представить, что мы работаем с
дробями, а не с целыми числами. Пусть w есть размер машинного слова; целое
число A можно рассматривать как дробь A/w, если мысленно поставить
десятичную (или двоичную) точку слева от машинного слова, в котором
записано A. Метод состоит в том, чтобы выбрать A взаимно простым с w и
положить h(K)=[M(((A/w)K) mod 1)]. (4)
В двоичной системе M обычно берут равным степени двойки, так что
h(K) состоит из старших битов правой значащей половины произведения AK. В
двоичном виде при M=2m мультипликативная хеш-функция вычисляется так:
rA