Фундаментальные алгоритмы и структуры данных в Delphi

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

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

-------------

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

-------------

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

Функции хеширования

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

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

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

Простейший случай - использование целочисленный ключей, когда элемент уникально идентифицируется целочисленным значением. Простейшей функцией хеширования, которую можно было бы использовать в этом случае, является операция деления по модулю. Если хеш-таблица содержит n элементов, хеш-значение ключа k вычисляется путем вычисления k по модулю n (если результат этой операции оказывается отрицательным, нужно просто добавить к нему n). Например, если n равно 16, то ключу 6 будет соответствовать индекс 6, ключу 44 - индекс 12 и т.д. В случае равномерного распределения значений ключей эта функция вполне подходила бы для работы, но в общем случае множество значений ключей не столь равномерно распределенное, и поэтому в качестве размера хеш-таблицы необходимо использовать простое число.

На практике можно сформулировать следующее правило создания хеш-таблиц: количество записей в хеш-таблице всегда должно быть равно простому числу. Для ознакомления с полным математическим обоснованием этого утверждения обратитесь к [13].

Для строковых ключей следует использовать метод, заключающийся в преобразовании строки в целочисленное значение с последующим применением операции деления по модулю для получения значения индекса, лежащего в диапазоне от 0 до n - 1.

Так как же преобразовать строку в целочисленное значение? Один из возможных способов предполагает использование длины строкового ключа. Преимущество применения этого метода состоит в простоте и высокой скорости выполнения. Однако его недостатком является генерирование множества конфликтов. На практике таких конфликтов возникает слишком много. Например, предположим, что нужно создать хеш-таблицу, которая должна содержать названия альбомов коллекции компакт-дисков. В частности, в принадлежащей автору коллекции компакт-дисков, насчитывающей несколько сот наименований, названия подавляющего большинства альбомов содержат от 2 до 20 символов. Использование длины названия альбома привело бы к возникновению множества конфликтов: альбом Bilingual в исполнении Pet Shop Boys конфликтовал бы с Technique в исполнении New Order и с Mind Bomb в исполнении The The. Таким образом, подобная функция хеширования совершенно неприемлема.