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

Хеширование - хороший пример компромисса между временем и объемом памяти. Если бы на объем используемой памяти ограничения не накладывались, любой поиск можно было бы выполнить за счет всего лишь одного обращения к памяти, просто используя ключ в качестве адреса памяти, как это делается при поиске с использованием индексирования по ключу. Однако, часто этот идеальный случай оказывается недостижимым, поскольку требуемый объем памяти неприемлем, когда ключи являются длинными. С другой стороны, если бы не существовало ограничений на время выполнения, можно было бы обойтись минимальным объемом памяти, используя метод последовательного поиска. Хеширование предоставляет способ использования как приемлемого объема памяти, так и приемлемого времени с целью достижения компромисса между этими двумя крайними случаями. В частности, можно поддерживать любое выбранное соотношение, просто настраивая размер таблицы, а не переписывая код или выбирая другие алгоритмы.

Хеширование - одна из классических задач компьютерных наук: различные алгоритмы подробно исследованы и находят широкое применение. Мы увидим, что при ряде общих допущений можно надеяться на обеспечение поддержки операций search и insert в таблицах символов при постоянном времени выполнения независимо от размера таблицы.

Это ожидаемое постоянное время выполнения - теоретический оптимум производительности для любой реализации таблицы символов, но хеширование не является панацеей по двум основным причинам. Во-первых, время выполнения зависит от длины ключа, которая может быть значительной в реальных приложениях, использующих длинные ключи. Во-вторых, хеширование не обеспечивает эффективные реализации для других операций, таких как select или sort, с таблицами символов. Эти и другие вопросы подробно рассматриваются в этой главе.

14.1 Хеш-функции

Прежде всего, необходимо решить задачу вычисления хеш-функции, которая занимается преобразованием ключей в адреса в таблице. Обычно реализация этого математического вычисления не представляет сложности, но необходимо соблюдать определенную осторожность во избежание различных малозаметных ловушек. При наличии таблицы, которая может содержать М элементов, нам требуется функция, которая преобразует ключи в целые числа в диапазоне [О, Л/ - 1]. Идеальную хеш-функцию легко вычислить и аппроксимировать случайной функцией: для любого вводимого значения в определенном смысле выводимое значение должно быть равновероятным.

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

Вероятно, простейшей является ситуация, когда ключами являются числа с плавающей точкой, заведомо относящиеся к фиксированному диапазону. Например, если ключи - числа, которые больше О и меньше 1, их можно просто умножить на М, округлить до ближайшего целого числа и получить адрес в диапазоне между О и М - \ ; пример показан на рис. 14.1. Если ключи больше S и меньше t, их можно масштабировать, вычтя s и разделив на / - л, в результате чего они попадут в диапазон значений между О и 1, а затем умножить на М для получения адреса в таблице.

Если ключи - это н-разрядные целые числа, их можно преобразовать в числа с плавающей точкой и разделить на 2* для получения чисел с плавающей точкой в диапазоне между О и 1, а затем умножить на М, как в предыдущем абзаце. Если операции с плавающей точкой выполняются часто, а числа не столь велики, чтобы при-

РИСУНОК 14.1

МУЛЬТИПЛИКАТИВНАЯ ХЕШ-ФУНКЦИЯ ДЛЯ КЛЮЧЕЙ С ПЛАВАЮЩЕЙ ТОЧКОЙ

Для преобразования чисел с плавающей точкой в диапазоне между О и 1 в индексы таблицы, размер которой равен 97, выполняется умножение на 97. В этом примере имеют место три конфликта: при значениях индексов равных 17, 53 и 76. Старшие разряды ключа определяют хеш-значения; младшие разряды ключей не играют никакой роли. Одна из целей разработки хеш-функции - избежание дисбаланса, когда во время вычисления каждый разряд данных играет определенную роль.

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

Более простой и эффективный метод для и-разряд-ных целых чисел - один из, вероятно, наиболее часто используемых методов хеширования - выбор в качестве размера М таблицы простого числа и вычисление остатка от деления к на Л/, или h{k) = к mod М для любого целочисленного ключа к. Такая функция называется модульной хеш-функцией. Ее очень просто вычислить (к % М в языке С++), и она эффективна для достижения равномерного распределения значений ключей между значениями, которые меньше М. Небольшой пример показан на рис. 14,2.

Модульное хеширование можно использовать также для ключей с плавающей точкой. Если ключи относятся к небольшому диапазону, можно выполнить масштабирование с целью их преобразования в числа из диапазона между О и 1, умножить на 2** для получения w-разрядных целочисленных значений, а затем использовать модульную хеш-функцию. Другая альтернатива - просто ис-.пользовать в качестве операнда модульной хеш-функции двоичное представление ключа (если оно доступно).

Модульное хеширование применяется во всех случаях, когда имеется доступ к разрядам, образующим ключи, независимо от того, являются ли они целыми числами, представленными машинным словом, последовательностью символов, упакованных в машинное слово, или представлены одним из множества других возможных вариантов. Последовательность случайных символов, упакованная в машинное слово - не совсем то же, что случайные целочисленные ключи, поскольку некоторые разряды используются для кодирования. Но оба эти типа (и любой другой тип ключа, который кодируется так, чтобы уместиться в машинном слове) можно заставить выглядеть случайными индексами в небольшой таблице.

РИСУНОК 14.2 МОДУЛЬНАЯ ХЕШ-ФУНКЦИЯ ДЛЯ ЦЕЛОЧИСЛЕННЫХ КЛЮЧЕЙ

В трех правых столбцах показан результат хеширования 16-разрядных ключей, приведенных слева, с помощью следующих функций v% 97 (слева) V % 100 (в центре) и (int) (a*v)% 100 (справа), где а = .618033. Размеры таблицы для этих функций соответственно равны 97, 100 и 100. Значения оказываются случайными (поскольку ключи случайны). Центральная функция (v % 100) использует только две крайние справа цифры ключей и поэтому может показывать низкую производительность применительно к неслучайным ключам.