при использовании расширенных BST-деревьев, RB-деревьев бинарного поиска или списков пропусков. В случае необходимости, RB-деревья бинарного поиска можно сделать столь же эффективными в плане используемого объема памяти, как и расширенные BST-деревья, исключив разряд цвета (см. упражнение 13.65). В современных приложениях объем памяти - не столь критичный фактор, каким он был когда-то, однако истинный профессионал все же должен избегать напрасных затрат. Например, необходимо знать, что некоторые системы могут использовать все 32-разрядное слово для небольшого поля счетчика или 1-разрядного поля цвета в узле, в то время как другие системы могут упаковывать поля в памяти так, что их распаковка требует значительного дополнительного времени. Если объем памяти ограничен, списки пропусков с большим параметром t могут уменьшить объем памяти, требуемый для связей, почти в два раза ценой более медленного (но все же определяемого логарифмической зависимостью) поиска. В некоторых случаях основанные на деревьях методы могут быть также реализованы с использованием по одной связи на узел (см. упражнение 12.68).

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

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

Упражнения

13.85 Разработайте реализацию таблицы символов, использующую рандомизованные BST-деревья, которая содержит деструктор, конструктор копирования и перегруженную операцию присваивания и поддерживает операции construct, count, search, insert, remove, join, select и sort для АТД таблиц символов с дескрипторами клиентских элементов (см. упражнения 12.6 и 12.7).

13.86 Разработайте реализацию таблицы символов, использующую списки пропусков, которая содержит деструктор, конструктор копирования и перегруженную операцию присваивания и поддерживает операции construct, count, search, insert, remove, join, select и sort тя АТД таблиц символов с дескрипторами юшентских элементов (см. упражнения 12.6 и 12.7).

Zta 14

Хеширование

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

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