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

Программа 14.7 Динамическая ваавка в хеш-таблицу (для линейного зондирования)

Эта реализация операции insert для линейного зондирования (см. программу 14.4) обрабатывает произвольное количество ключей, удваивая размер таблицы при каждом заполнении таблицы наполовину (такой же подход может использоваться для двойного хеширования или раздельного связывания). Удвоение требует распределения памяти для новой таблицы, повторного хеширования всех ключей в новую таблицу, а затем освобождения памяти, занимаемой старой таблицей. Функция-член init используется для построения или повторного построения таблицы, заполненной нулевыми элементами указанных размеров: она реализована так же, как конструктор ST в программе 14.4, поэтому ее код опущен.

private: void expand О

{ Item *t = st; init(M+M);

for (int i = 0; i < M/2; i++)

if (!t[i] .nullO) insert(t[i]) ; delete t;

piiblic: ST(int maxN)

{ init (4); } void insert(Item item)

{ int i = hash(item.]cey 0 , M) ;

while (!st[i]-nullO) i = (i+1) % M;

st[i] = item;

if (N++ >= M/2) expand 0;

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

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

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

Если требуется поддерживать операцию remove абстрактного типа данных, может иметь смысл сужать таблицу, вдвое уменьшая ее размер при уменьшении количества ее ключей (см. упражнение 14.44). Но это требует одной оговорки: порог сужения должен отличаться от порога увеличения, поскольку в противном случае небольшое количество операций insert и remove могло бы приводить к последовательности операций удвоения и уменьшения размера вдвое даже для очень больших таблиц.

Лемма 14.6 Последовательность операций search, insert и delete в таблицах символов может быть выполнена за время, которое пропорционально t, и при использовании объема памяти, не превышающего числа ключей в таблице, умноженного на постоянный коэффициент.

Линейное зондирование с увеличением путем удвоения используется во всех случаях, когда операция insert приводит к тому, что количество ключей в таблице становится равным половине размера таблицы. Сужение путем уменьшения размера таблицы вдвое используется, когда операция remove приводит к тому, что количество ключей в таблице становится равным одной восьмой размера таблицы, В обоих случаях после того, как размер таблицы изменен до значения 7V, она содержит N/A ключей. После этого должно быть выполнено 7V/4 операций insert, прежде чем размер таблицы будет снова удвоен (за счет повторной вставки 7V/2 ключей в таблицу размера 2N), и 7V/8 операций remove, прежде чем размер таблицы будет снова вдвое уменьшен (за счет повторной вставки 7V/8 ключей в таблицу размера N/2). В обоих случаях количество повторно вставляемых ключей не превышает двукратного количества операций, которые были выполнены для инициализации перестройки таблицы, поэтому обшие затраты остаются линейными. Более того, таблица всегда заполнена от одной восьмой до одной четверти (см. рис. 14.13), следовательно, в соответствие с леммой 14.4 среднее количество зондирований для каждой операции меньше 3.

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

Упражнения

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

14.41 Не было бы ли более экономичным увеличивать хеш-таблицу, утраивая (а не удваивая) ее размер при заполнении таблицы наполовину?

14.42 Не было бы ли более экономичным увеличивать хеш-таблицу, утраивая ее размер при заполнении таблицы на одну треть (вместо того, чтобы удваивать размер таблицы при ее заполнении наполовину)?

14.43 Не было бы ли более экономичным увеличивать хеш-таблицу, удваивая ее размер при заполнении таблицы на три четверти (а не наполовину)?

14.44 Добавьте в программу 14.7 функцию remove, которая удаляет элемент, как в программе 14.4, но затем сжимает таблицу, вдвое уменьшая ее размер, если после удаления таблица остается пустой на семь восьмых.

о 14.45 Реализуйте версию профаммы 14.7 для раздельного связывания, которая в 10 раз увеличивает размер таблицы каждый раз, когда средняя длина списка равна 10.

14.46 Измените программу 14.7 и реализацию, созданную в упражнении 14.44, чтобы в них использовалось двойное хеширование с ленивым удалением (см. упражнение 14.33). Обеспечьте, чтобы программа учитывала количество фиктивных объектов и пустых позиций при принятии решения о необходимости расширения или сужения таблицы.

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

14.6 Перспективы

Как было показано в ходе рассмотрения методов хеширования, выбор метода, который наиболее подходит для конкретного приложения, зависит от множества различных факторов. Все методы могут уменьшать время выполнения функций search и insert, делая его постоянным, и все методы находят применение в широком множестве приложений. Обобщая, можно охарактеризовать три основных метода (линейное зондирование, двойное хеширование и раздельное связывание) следующим образом: линейное зондирование является самым быстрым из этих трех методов (при наличии достаточного объема памяти, чтобы таблица была разреженной), двойное хеширование позволяет наиболее эффективно использовать память (но требует дополнительных затрат времени для вычисления второй хеш-функции), а раздельное связывание проще всего реализовать и применять (при условии наличия хорошего средства распределения памяти). Экспериментальные данные и комментарии, характеризующие производительность алгоритмов, приведены в табл. 14.1.