До сих ПОР мы РАССМАТРИВАЛИ методы поиска, основанные на сравнении данного аргумента К с ключами в таблице или на использовании его цифр для управления процессом разветвления. Третий путь заключается в том, чтобы отказаться от поиска по данным и выполнить арифметические действия над К, позволяющие вычислить некоторую функцию f{K). Последняя укажет адрес в таблице, где хранится К и связанная с ним информация.

Например, рассмотрим хорошо известное нам множество из 31 английского слова, которое приводилось в разделах 6.2.2 и 6.3. В табл. 1 показана небольшая MIX-программа, взаимно однозначно преобразующая 31 ключ в числа f{K) между -10 и 30. Если сравнить этот метод с MIX-программами для других рассматривавшихся методов (например, для бинарного поиска, оптимального поиска по дереву, "лучевого" поиска, цифрового поиска по дереву), то можно обнаружить, что новый способ превосходит старые как с точки зрения быстродействия, так и с точки зрения количества используемой памяти (за исключением бинарного поиска, для которого необходим несколько меньший объем памяти). В самом деле, среднее время успешного поиска с помощью программы из табл. 1 составляет около 17.8и и требует для хранения 31 ключа таблицу из 41 элемента.

К сожалению, поиск таких функций f{K) - довольно сложная задача. Имеется 41 и 10° возможных функций, отображающих 31-элементное множество в 41-элементное; однако только 41 • 40 • ... 11 = 411/10! и 10* из них дают различные значения для различных аргументов; следовательно, только одна из десяти миллионов функций подходит для достижения нашей цели.

Функции, дающие неповторяющиеся значения, встречаются на удивление редко (даже для больших таблиц). Например, в соответствии со знаменитым "парадоксом дней рождения" получается, что в компании из 23 человек более вероятно совпадение дней рождения у двух из них, чем то, что у всех дни рождения окажутся различными. Иными словами, если выбрать случайную функцию, отображающую 23 ключа в таблицу размером 365, вероятность того, что никакие два ключа не будут отображены в одно и то же место таблицы, составляет 0.4927, т. е. менее половины. Скептики могут проверить парадокс на ближайшей многолюдной вечеринке*. [Парадокс дней рождения неформально обсуждался математиками в 30-е годы; происхождение этого парадокса неизвестно. См. I. J. Good, Probability and the Weighing of Evidence (Griffin, 1950), 38, a также R. vonMises, Istanbul Universitesi Fen Fakiiltesi Mecnauasi 4 (1939), 145-163; W. Feller, An Introduction to Probability Theory (New York: Wiley, 1950), Section 2.3.]

С другой стороны, использованный в табл. 1 подход весьма гибок [см. М. Gre-niewski and W. Turski, CACM 6 (1963), 322-323], и для таблиц небольшого размера подходящая функция может быть найдена за день-другой. Решать такого рода головоломки весьма занятно! Вопросы поиска подходящих функций рассматривались многими исследователями, включая, например, R. Sprugnoli, САСМ 20 (1977), 841-850, 22 (1979), 104, 553; R. J. Cichelli, САСМ 23 (1980), 17-19; Т. J. Sager, САСМ 28 (1985), 523-532, 29 (1986), 557; В. S. Majewski, N. С. Wormald, G. Havas

* Любители математики могут обратиться за подробностями, например, к книге У. Болла и Г. Коксетера Математические эссе и развлечения (М.: Мир, 1986. - 474 с). Скептикам-нелюдимам рекомендуется вспомнить свой класс в школе или группу в институте. - Прим. перев.

Таблица 1

ВЗАИМНО ОДНОЗНАЧНОЕ ПРЕОБРАЗОВАНИЕ МНОЖЕСТВА КЛЮЧЕЙ В АДРЕСА

and Z. J. Czech, Сотр. J. 39 (1996), 547-554; Czech, Havas, and Majewski, Theoretical Сотр. Sci. 182 (1997), 1-143. См. также статью J. Korner and K. Marton, Europ. J. Combinatorics 9 (1988), 523-530, о теоретических ограничениях идеальных хеш-функций.

Конечно, этот метод имеет очень существенный недостаток, заключающийся в том, что содержимое таблицы должно быть заранее известно. Добавив всего один ключ, можно все испортить, и придется начинать всю работу с нуля. Впрочем, можно получить гораздо более гибкий метод, отбрасывая требование однозначности и используя специальные методы разрешения возникающих неоднозначных ситуаций после вычисления f{K).

Итак, мы вплотную приблизились к популярному классу методов поиска с общим названием хеширование (hashing) или рассеянная память (scatter storage). Глагол "to hash" означает "крошить, рубить и делать из этого месиво"*. Идея хеширования состоит в использовании некоторой частичной информации, полученной из ключа, в качестве основы поиска. Мы вычисляем хеш-адрес h(K) и используем его для проведения поиска.

Парадокс дней рождения предостерегает нас, что, вероятно, найдутся различные ключи Ki ф Kj, имеющие одинаковое значение хеш-функции h(Ki) = h(Kj). Такое событие именуется коллизией (collision); для разрешения коллизий разработаны некоторые интересные подходы. Для использования хеширования программист должен решить две практически независимые задачи - выбрать хеш-функцию

* В связи с этим был очень велик соблазн использовать для термина хеширование русское слово окрошка. - Прим. перев.

h{K) и способ разрешения коллизий. В этом разделе будут рассмотрены обе эти задачи.

Хеш-функции. Для определенности в данном разделе предполагается, что хеш-функция имеет не более М различных значений, причем для всех ключей К

О < h{K) < М. (1)

На практике ключи в реальном файле зачастую избыточны, а потому мы должны быть очень внимательны при поиске хеш-функции, чтобы не допустить создания кластеров из близких ключей с целью уменьшения количества коллизий.

Теоретически невозможно определить хеш-функцию так, чтобы она создавала случайные данные из реальных неслучайных файлов. Однако на практике не так уж сложно создать неплохую имитацию случайных данных с помощью простых арифметических действий, как обсуждалось в главе 3. В действительности зачастую можно достичь даже лучших результатов, находя и используя неслучайные свойства данных для построения хеш-функций с минимальным количеством коллизий (меньшим, чем при истинно случайных данных).

Рассмотрим, например, десятизначные ключи на десятичном компьютере. Напрашивается следующий способ выбора хеш-функции: положить, скажем, М = 1000 и в качестве h{K) использовать три цифры, выбранные около средины двадцатизначного произведения К х К. Казалось бы, этот метод должен давать довольно равномерное распределение значений между ООО и 999 с низкой вероятностью коллизий, однако эксперименты с реальными данными показывают, что такой метод "середины квадрата" неплох при условии, что ключи не имеют большого количества