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

Однако если бы элемент можно было связать с уникальным индексом, его можно было бы найти посредством однонаправленного действия: просто извлекая элемент, расположенный в позиции MyList[ItemIndex]. Это пример поиска с использованием индексирования по ключу, когда ключ элемента преобразуется в индекс, и элемент извлекается из массива с помощью этого индекса. Такой подход кардинально отличается от бинарного поиска, при котором, по существу, ключ элемента используется для перемещения по структуре с применением метода, в основе которого лежит сравнение.

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

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

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

Время от времени, с хеш-таблицами придется выполнять следующие операции:

* вставлять элементы в хеш-таблицу;

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

* удалять элементы из хеш-таблицы.

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

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

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

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

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

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

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

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

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

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

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

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