равен I)1. Будем считать, что наша операционная система, как и большинство современных, снабжена подсистемой управления памятью, позволяющей при необходимости выделять новые блоки памяти и освобождать занятые. Имея это в виду, при попытке добавить запись к заполненной таблице мы будем предварительно расширять (expand) таблицу следующим образом: выделим память под таблицу увеличенного размера, скопируем имеющиеся записи из старой таблицы в новую, после чего добавим запись уже к новой таблице.

Как показывает опыт, разумно увеличивать таблицу вдвое в момент переполнения. Если мы только добавляем записи к таблице, то при такой стратегии коэффициент заполнения не может стать меньше 1/2 (если он не был таким в самом начале), т.е. пустые ячейки не будут занимать более половины таблицы.

Вот как выглядит алгоритм Table-Insert, основанный на этих принципах (table[T] -указатель на блок памяти, в котором размещена таблица Г, пит[Т] - количество записей в таблице, size[T] - размер таблицы, т.е. количество ячеек; первоначально size[T] = num[T] = 0):

Table-Insert (Г, ж)

1if size[T] = 0

2then выделить блок table[T] с одной ячейкой

3size[T] <- 1

4if num[T] = size[T]

5then выделить блок памяти new-table с 2 • size[T] ячейками

6скопировать все записи из table[T] в new-table

7освободить память, занятую table[T]

8table[T] <- new-table

9size[T] <- 2 • size[T]

10записать ж в table[T]

11num[T] <- num[T] + 1

Проанализируем время работы этого алгоритма. Собственно запись в таблицу происходит в нём только в строках 6 и 10. Стоимость операции «записать элемент в таблицу» примем за единицу. Будем считать, что время работы всей процедуры Table-Insert пропорционально количеству операций «записать в таблицу»; тем самым мы подразумеваем, что затраты на выделение памяти под таблицу с одной ячейкой (строка 2) - величина ограниченная, и что затраты на выделение и освобождение памяти в строках 5 и 7 - величина не большего порядка, чем затраты на переписыва-

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

ние из одной таблицы в другую (строка 6).

Пусть теперь мы применили га операций Table-Insert к таблице, не содержащей первоначально ни одной ячейки. Какова стоимость г-й операции, после которой в таблице будет г элементов? Обозначим эту стоимость через сг-. Если в таблице есть место (или если г = 1), то сг- = 1 (мы записываем новый элемент в таблицу один раз в строке 10. Если же места в таблице нет и добавление записи к таблице сопровождается расширением таблицы, то сг- = г: одна единица стоимости идет на запись нового элемента в расширенную таблицу (строка 10), и ещё г - 1 единица пойдет на копирование старой таблицы в новую (строка 6). Стало быть, сг- га при всех г, и грубая оценка стоимости га операций Table-Insert есть О (га2). Можно, однако, эту оценку улучшить, если проследить, сколь часто происходит расширение таблицы. В самом деле, расширение происходит только в том случае, когда г - 1 является степенью двойки, так что

Стало быть, стоимость га операций Table-Insert не превосходит Зга, и учётную стоимость каждой такой операции можно считать равной 3.

Понять, откуда берется коэффициент 3, можно с помощью метода предоплаты. Именно, при выполнении каждой операции Table-Insert (Г, ж) будем вносить по 3 доллара, при этом один доллар немедленно израсходуем на оплату операции «записать х в table[T]» в строке 10, ещё один доллар прикрепим к элементу ж, а оставшийся отдадим одному из элементов, уже записанных в таблицу (из тех, что ещё не получили своего доллара) Этими долларами будет оплачиваться перенос записей из старой таблицы в расширенную. При этом всякий раз, когда таблицу необходимо расширять, каждый из её элементов будет иметь по доллару. В самом деле, пусть при предыдущем расширении таблица имела размер т и была расширена до 2т. С тех пор мы добавили т элементов, при этом и добавленные элементы, и каждый из т старых элементов получили по доллару. Таким образом, следующее расширение таблицы уже оплачено.

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

п

Ф(Г) = 2 • пит[Т]

size[T].

Начальное значение потенциала равно нулю, и поскольку в любой момент не менее половины таблицы заполнено, значение Ф(Г) всегда неотрицательно. Стало быть, сумма учётных стоимостей операций Table-Insert (определённых по методу потенциалов как фактическая стоимость плюс изменение потенциала) оценивает сверху суммарную фактическую стоимость.

Найдем учётные стоимости. Для этого обозначим через size;, пицц и Фг размер, количество записей и потенциал таблицы после г-й операции Table-Insert. Если эта операция не сопровождалась расширением таблицы, то size; = sizei-i, пипц = питг 1 + 1 и сг- = 1, откуда

с,- = с,- + Фг - Ф,- 1 = 3.

Если же г-я операции Table-Insert сопровождалась расширением таблицы, то sizei/2 = sizei-i = nurrii-i и сг- = пига,-, откуда опять-таки

с,- = с,- + Ф,- - Ф,- 1 =

= пига, + (2 пипц - size/) - (2пипц \ - sizei \) =

= пицц + (2 пипц - (2 пипц - 2)) - (2(пищ - 1) - (пиггц - 1)) =

= пицц + 2 - (nurrii - 1) = 3.

На рис. 18.3 изображена зависимость величин nurrii, sizei и Фг- от г. Обратите внимание, как накапливается потенциал к моменту расширения таблицы.

18.4.2. Расширение и сокращение таблицы

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

•коэффициент заполнения ограничен снизу положительной константой,

•учётная стоимость операций Table-Insert и Table-Delete есть 0(1).

При этом мы по-прежнему будем считать, что стоимость алгоритма определяется количеством операций «записать в таблицу» (строки 6 и 10 алгоритма Table-Insert) и противоположных ей