вычислений функции /i2 для одной вставки составляет согласно анализу Брента

++а®Н----и достигает в конечном счете 0(%/М); количество дополнительных

проб позиций таблицы после решения о том, каким образом будет производиться вставка, составляет около а + а* + + а® + • • •.

С усовершенствованными модификациями Бренда работав Е. Г. Маллах (Е. G, Mallach) [Сотр. J. 20 (1977), 137-140]; с другими результатами в этом направлении можно ознакомиться в работе Gaston Н. Gonnet and J. Ian Munro, SICOMP 8 (1979), 463-478.

Удаления. Многие программисты настолько слепо верят в алгоритмы, что даже не пытаются задуматься о том, как они работают. Для них неприятным сюрпризом становится то, что очевидный способ удаления записей из хеш-таблицы не работает. Например, чтобы удалить ключ EN на рис. 41, нельзя просто пометить этот узел в таблице как пустой, поскольку окажется потерянным другой ключ, РЕМ. (Вспомним, что и EN, и РЕМ хешируются в одно и то же положение. При поиске РЕМ мы натолкнемся на пустое .место, что свидетельствует о неудачном завершегши поиска.) Подобная проблема возникает в случае использования алгоритма С из-за срастания списков; рассмотрите удаление двух ключей - ТО и FIRE - на рис. 40.

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

Однако такой метод работает только при редких удалениях, поскольку однажды занятая позиция больше никогда не сможет стать свободной, а значит, после длинной последовательности вставок и удалений все свободные позиции исчезнут, а при неудачном поиске будет требоваться М проверок! Более того, время пробы при этом увеличится, так как на шаге D4 придется проверять, не приняло ли г свое первоначальное значение, а число проб в случае успешного поиска возрастет с Сд до Cjy.

При использовании линейного исследования (алгоритм L) можно поступить более разумно, если, конечно, затратить дополнительные усилия на удаление.

Алгоритм R (Удаление при линейном исследовании). Пусть хеш-таблица построена по алгоритму L. Алгоритм удаляет запись из данной позиции TABLE [г].

R1. [Освобождение ячейки.] Пометить TABLE [г] как пустую и установить j <- г. R2. [Уменьшение г.] Установить г <- г - 1 и, если i стало отрицательным, установить г <- г -f М.

R3. [Проверить TABLE [г].] Если TABLE [г] пуст, алгоритм завершается. В противном случае установить г <- /г(КЕУ[г]) - первоначальный хеш-адрес ключа, который хранится в позиции г. Если i < г < j или если г < j < г либо j < i < г (другими словами, если г лежит циклически между г и j), вернуться к шагу R1.

R4. [Переместить запись.] Установить TABLE [j] <- TABLE [г] и вернуться к шагу R1. I

В упр. 22 показано, что этот алгоритм не вызывает снижения производительности; другими словами, среднее количество проб, предсказанное в формулах (22) и (23), останется тем же (более слабый результат для вставки в дерево был доказан

в теореме 6.2.2Н). Однако корректность алгоритма R сильно зависит от того факта, что используется линейное исследование хеш-таблицы, а потому аналогичный алгоритм удаления при применении алгоритма D отсутствует. Среднее время работы алгоритма R анализируется в упр. 64.

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

Алгоритм R позволяет перемещать некоторые элементы таблицы, что может оказаться нежелательно (например, если на элементы имеются ссылки извне). Другой подход к проблеме удаления основывается на адаптировании некоторых идей, использующихся при сборке мусора (см. раздел 2.3.5): можно хранить количество ссылок с каждым ключом, говорящим о том, как много других ключей сталкивается с ним; тогда при обнулении счетчика можно преобразовать такие ячейки в пустые. Другой метод состоит в проходе по всей таблице, как только наберется слишком много удаченных элементов, замене всех незанятых позиций пустыми и просмотре всех оставшихся ключей, чтобы выяснить, какие незанятые позиции все еще имеют статус "удаленных" Эти методы, позволяющие избежать перемещения элементов в таблице и работающие с любой хеш-технологией, были впервые предложены в работе Т. Gunji and Е. Goto, J. Information Ргос. 3 (1980), 1-12.

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

Прежде чем приступить к анализу линейного исследования и других методов хеширования, рассмотрим приближенную модель ситуации, называемой равномерным исследованием. В этой модели, предложенной В. В. Петерсоном (W. W. Peterson) [IBM J. Research & Development 1 (1957), 135-136], предполагается, что каждый ключ размещается в совершенно случайном месте таблицы, так что все () возможных конфигураций из N занятых и М - N пустых ячеек равновероятны. В данной модели игнорируются эффекты первичного или вторичного скучивания; предполагается, что занятость каждой конкретной ячейки не зависит от занятости остальных. Тогда вероятность того, что для вставки (Л-f 1)-го элемента необходимо в точности г проб, равна количеству конфигураций, в которых г - 1 данная ячейка занята, а еще одна пуста, деленному на (), т. е.

Рг =

(М N

( М-г ,7V-r + l,

Таким образом, среднее количество проб в случае равномерного исследования составляет

См = гРг = М + 1- Y{M + 1 - r)Pr

{М + 1-Л 1(м

M-N

(Мы уже решали, по существу, ту же задачу в связи со случайной выборкой в упр. 3.4.2-5.) Полагая а = N/M, точную формулу для Cjy можно заменить приближенной:

= 1 -f а -f -f -f • •. (33)

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

1 М +1 / 1 1

-N -~1Г[МТ1М"" M-N + 2J

= (Ялт-Ям-+1)«-1п-. (34)

N а 1 - а

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

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

aia2...aN, О < а-< М, (35)

равновероятны. Здесь Oj обозначает начальный хеш-адрес j-ro ключа, вставленного в таблицу. Среднее количество проб в случае успешного поиска при работе по данному алгоритму поиска, как и выше, обозначим через С; это значение представляет собой среднее количество проб, которые необходимы для поиска fc-ro ключа, усредненное по всем 1 < к < N при равновероятных ключах и по всем хеш-последовательностям (35) (все последовательности считаются равновероятными). Аналогично среднее количество проб, необходимых при вставке Л-го ключа, считая все последовательности (35) равновероятными, обозначим как Сдг 1; эта величина представляет собой среднее количество проб в случае неудачного поиска, начинающегося при наличии в таблице Л-l элемента. При использовании открытой адресации