Рис. 18.3 Размер таблицы (size,), число записей (пит,) и потенциал (Ф, = 2 • пит, - size,) как функция от числа операций Table-Insert, обозначенного буквой г. График пит - сплошная тонкая линия, график size - сплошная жирная линия, график Ф - пунктир. Непосредственно перед расширением таблицы Ф возрастает до пит,, чтобы оплатить это расширение. Сразу после расширения потенциал падает до нуля, но тут же и возрастает до 2 (за счет добавления записи после расширения).

операций «убрать из таблицы»; стоимость каждой из этих элементарных операций примем за единицу.

Первое, что приходит в голову, - удваивать размер таблицы всякий раз, когда надо добавить запись к заполненной таблице, и сокращать размер таблицы вдвое всякий раз, когда в результате удаления записи коэффициент заполнения падает ниже 1/2. При такой стратегии коэффициент заполнения никогда не опустится ниже 1/2, но, к сожалению, стоимости операций оказываются слишком велики. В самом деле, пусть га - натуральное число, являющееся степенью двойки. Предположим, что сначала мы добавили к пустой (не содержащей ячеек) таблице га/2 + 1 записей, а затем провели ещё п/2 - 1 операцию в такой последовательности: два удаления, затем два добавления, затем опять два удаления, опять два добавления, и т.д. После п/2 + 1 добавлений размер таблицы станет равным п (и заполнено будет чуть больше половины ячеек); после двух удалений его придется сократить до п/2; после следующих двух добавлений размер опять возрастет до п, после двух удалений - сократится до п/2, и т.д. Стоимость каждого сокращения и расширения есть в (га), и количество сокращений и расширений также есть О(га), так что стоимость га операций есть 0(га2), а средняя стоимость в расчёте на одну операцию оказывается равной О(га).

Причина неудачи понятна: истратив весь резерв на оплату расширения таблицы, мы тут же вынуждены ее сокращать, не успев

накопить средства на оплату будущего сокращения. Та же история и с расширением таблицы: мы вынуждены предпринимать его сразу после сокращения, не успев накопить средства за счет добавления записей в таблицу постоянного размера.

Дела пойдут лучше, если мы разрешим коэффициенту заполнения опускаться ниже 1/2 [введя гистерезис в наш алгоритм, как сказали бы физики]. Именно, мы по-прежнему удваиваем размер таблицы при попытке добавить запись к заполненной таблице, а вот сокращение таблицы вдвое мы предпринимаем только тогда, когда коэффициент заполнения падает ниже 1/4. Таким образом, коэффициент заполнения всегда будет больше или равен 1/4. Другими словами, мы считаем 50% оптимальным коэффициентом заполнения таблицы, и возвращаемся к такой ситуации, как только коэффициент заполнения отклонится от оптимального в два раза (в любую сторону).

Мы не будем выписывать псевдокод для алгоритма Table-Delete - он аналогичен коду для Table-Insert. Отметим только, что при удалении из таблицы последней записи разумно полностью освобождать память, занимаемую ячейками таблицы. Ниже мы будем считать, что в алгоритме Table-Delete это предусмотрено, иными словами, что size[T] = 0, как только пит[Т] = 0.

Для оценки стоимости последовательности из п операций Table-Insert и Table-Delete, примененных к пустой таблице, мы воспользуемся методом потенциалов. Потенциальная функция будет равна нулю, когда коэффициент заполнения оптимален (равен 1/2) - так будет сразу после сокращения или расширения. Потенциал возрастает по мере того, как коэффициент заполнения приближается к 1 или 1/4. Напомним, что коэффициент заполнения си (Г) равен num[T]/size[T], если size[T] ф 0, и равен 1, если size[T] (и тем самым питп[Т]) равно нулю. Нашим требованиям удовлетворяет такая потенциальная функция:

Заметим, что Ф(Г) = 0 при си (Г) = 1/2 (по любой из двух формул), что потенциал пустой таблицы равен нулю и что потенциал всегда неотрицателен. Если коэффициент заполнения равен 1 или 1/4, то Ф[Т] = питп[Т], так что накопленного потенциала достаточно для оплаты расширения или сокращения таблицы. На рис. 18.4 изображено, как меняется потенциал в процессе выполнения последовательности операций Table-Insert и Table-Delete.

Найдем учётные стоимости операций при таком потенциале Ф. Если операция Table-Insert или Table-Delete не сопровождается расширением или сокращением таблицы, то изменение потенциала не превосходит 2 (size не меняется, пит меняется на 1), так

если си [Г] 1/2, если си [Г] 1/2.

Рис. 18.4 Размер таблицы (size,), число записей (пит,) и потенциал

j 2 • пит, - size,, если а, 1/2,

1 size,/2 - пит,, если а, < 1/2, как функция от числа операций Table-Insert и Table-Delete, обозначенного буквой г. График пит - сплошная тонкая линия, график size - сплошная жирная линия, график Ф - пунктир. Непосредственно перед расширением или сокращением таблицы потенциал равен количеству записей.

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

В общем и целом, учётная стоимость каждой из операций есть 0(1), так что фактическая стоимость последовательности из га операций есть О(га).

Упражнения

18.4-1 Объясните, почему для случая< сиг- 1/2 учётная

стоимость операции Table-Insert равна нулю.

18.4-2 Почему динамическую хеш-таблицу с открытой адресацией разумно считать заполненной (и расширять) ещё до того, как коэффициент заполнения станет равным единице? Как запрограммировать добавление записи в такую таблицу, чтобы математическое ожидание учётной стоимости добавления была 0(1)? Почему нельзя гарантировать, что математическое ожидание реальной стоимости каждого добавления будет 0(1)?

18.4-3 Докажите, что учётная стоимость (относительно потенциала (18.5)) операции Table-Delete, примененной к динамической таблице с коэффициентом заполнения 1/2, не превосходит некоторой константы.