AOP_Tom3 (1021738), страница 154
Текст из файла (страница 154)
д. Вообще, пусть сх = Ьз(КЕУ[ру]) и р, ь — — (р„— Ьс]) пюб ЛХ; если для всех] и Ь, таких, что Х+Ь < г, узлы ТАВьЕ[р, ь] заняты несли 1 > г+ 1, просматриваем узлы тАВее[ро „], тАВ1.е[рк, г Ц ..., тАВ1.е[р„к1]. если первое пустое место оказывается в позиции р, „,, устанавливаем ТАВ|Е[р, „,] еТАВЬЕ [р ] и вставляем К в позицию р., Лнализ Брента показывает, что среднее количество проб на один успешный поиск уменьшается до уровней, показанных на рис. 44 на с.
583, с максимальным значением, равным приблизителыю 2.49. Количество проб Х+ 1 при неудачном поиске в результате внесенных в алгоритм изменений осталось прежним; оно осталось на уровне, который определен формулой (26) и достигает -'(ЛХ+ 1) при заполненности таблицы. Среднее количество вычислений функции Аэ для одной вставки составляет согласно анализу Брента а'+а~+-'а~+. и достигает в конечном счете 0(з/М): количество дополнительных проб позиций таблицы после решения о том, каким образом будет производиться вставка, составляет около а~ + а~ + —,а + а + С усовершенствованными модификациями Брента работал Е. Г.
Маллах (Е. БЬ Ма11ас1з) [Сошр. Х 20 (1977), 137-140); с другими результатами н этом направлении можно ознакомиться в рабате Оаэсоп Н. Ооппес апд Л. 1ап Мипго, 91СОМР 8 (1979)., 463-478. Удаления. Многие праграммистгя настолько слепо верят в алгоритмы, чта даже не пытаются заду'маться о том, как они работают. Для них неприятным ск)рпризом становится то, что очевидный способ удаления записей из теш-таблицы не работает. Например, чтобы удалить ключ ЕИ на рис. 41, нельзя просто пометить этот узел в таблице как пустой, поскольку окажется потерянным другой ключ, ЕЕИ.
(Вспомним, что и ЕИ, и ЕЕИ хешируются в одно н то же положение. При поиске ЕЕИ мы натолкнемся на пустое место, что свидетельствует о неудачном завершении поиска.) Подобная проблема возникает в случае использования алгоритма С из-за срастания списков; рассмотрите удаление двух ключей — Т0 и Е1ЕŠ— на рис. 40. Вообще говоря, обрабатывать удаление можно, поместив в соответствуницую ячейку специальный код. Таким образом, будет иметься три вида позиций в таблице: пустые, занятые и удаленные.
При поиске ключа следует пропускать удаленные ячейки, как если бы они были запяты. В случае неудачного поиска ключ может быть помещен в первую встреченную удаленву.ю или пустую позицию. Однако такой метод работает только при редких удалениях, поскольку однажды занятая позиция больше никогда не сможет стать свободной, а значит, посте длинной последовательности вставок и удалений все свабочные позиции исчезнут, а при неудачном поиске будет требоваться М проверок! Более того, время пробы при этом увеличится, так как на шаге 04 придется проверять, не приняло ли 1 свое первоначальное значение, а число проб в случае успешного поиска возрастет с Сн до Сч~.
При использовании линейнога исследования (алгоритм Ь) мовена поступить более разумно, если, конечно, затратить дополнительные усилия на удаление. Алгоритм В. (Удаление при линейном исследовании). Пусть хеш-таблица построена по алгоритму Ь. Алгоритм удаляет запись из данной позиции ТАВЬЕ[с Ь В.1. [Освобождение ячейки.) Пометить ТАВЬЕ [О как пустую и установить у е- Ь К2.
[Уменьшение 1.] Установиты е- 1 — 1 и, если 1 стало отрицательным, установить 1з — г ЬЛХ. НЗ. [Проверить ТАВЬЕ [П,) Если ТАВЬЕ [П пуст., алгоритм завершается. В противном случае установить г +- 6(КЕТ [П) — первоначальный хеш-адрес ключа, который хранится в позиции Ь Если 1 < г < 1 илн если г < 1 < 1 либо 1' < 1 < г (другими главами, если г лежит циклически между 1 и у), вернуться к шагу Й1.
Ы4. [Переместить запись.] Установить ТАВ1.Е [1) +- ТАВЬЕ [П и вернуться к шагу Н1. 1 В упр. 22 показана, что этот алгоритм не вызывает снижения производительности; друтими славами, среднее количество проб, предсказанное в формулах (22) и (23), останется тем же (более слабый результат для вставки в дерево был доказан в теореме 6.2,2Н).
Однако корректность алгоритма В сильно зависит ат того факта, что используется линейное исследование хеш-таблицы, а потому аналогичный алгоритм удаления при применении алгоритма П отсутствует, Среднее время работы алгоритма Н анализируется в упр. 64. Конечно, при использовании метода цепочек с различными списками для всех возможных хеш-значений удаление не вьгзывает проблем, поскольку сводится к простому удалению из связанного линейного списка. Удаление для алгоритма С обсуждается в упр. 23. Алгоритм К позволяет перемещать некоторые элементы таблицы, что может оказаться нежелательно (например, если на элементы имеются ссылки извне). Другой подход к проблеме удаления основывается на адаптировании некоторых идей, использующихся при сборке мусора (см.
раздел 2.3.5): можно хранить количество ссылок с каждым ключом, говорящим о том, как много других ключей сталкивается с ним; тогда при обнулении счетчика можно преобразовать эакве ячейки в пустые. Другой метод состоит в проходе по всей таблице, как только наберется слишком много удаленных элементов, замене всех незанятых позиций пустыми и просмотре всех оставшихся ключей, чтобы выяснить, какие незанятые позиции все еще имеют статус "удаленных".
Эти методы, позволяющие избежать перемещения элементов в таблице и работающие с любой хеш-технологией, были впервые предложены в работе Т. Опп)! апб Е. Со!о, 1. 1пуогта!!оп Ргос. 3 (1980), 1-12. *Анализ алгоритмов. Поскольку при хешировании необходимо опираться на теорию вероятностей, очень важно знать поведение метода хеширования в среднем. Наихудший случай использования этих алгоритмов невообразимо плох, поэтому следует убедиться в том,что поведение в среднем очень хорошее. Прежде чем приступить к анализу линейного исследования и других методов хеширования, рассмотрим приближенную модель ситуации, называемой равномерным исследованием.
В этой модели, предложенной В. В. Петерсоном (%. Ж. Регегэоп) [1ВМ Х Незеагсл й Рече!ортеп1 1 (1957), 135-136], предполагается, !то каждый ключ размещается в совершенно случайном месте таблицы, так что все (л) воз- М можных конфигураций из !У занятых и М вЂ” Х пусгых ячеек равновероятны.
В данной модели игнорируются эффекты первичного или вторичного скучивания; предполагается, что занятость каждой конкретной ячейки не зависит от занятости остальных. Тогда вероятность того, что для вставки (!У+ 1)-го элемента необходимо н точности г проб, равна количеству конфигураций, и которых г — 1 данная ячейка занята, а еще одна пуста, деленному на (,), т. е. м Таким образом, среднее количество проб в случае равномерного исследования со- ставляет м м С!ч = ~' гР~ = М + 1 ~(М + 1 !')Р~ г=! г=! =И~~ — Еэ[!1 ! —,|( ~ ' )!!(~~) = и,- ~ — Е<ы — к)(~~+ ') ~ (~) = лб 1 — [и — лс ( к+,',),~('~~) =М+1 — 1М вЂ” Л) = ', 1<~Ч< М. (Зг) М+1 М+1 М-Н+1 М-я+1' (Мы уже решали, по существу, ту же задачу в связи со случайной выборкой в упр.
3.4,2-5.) Полагая а = Ю/М, точную формулу для С~ можно заменить приблихсенной: =1+а+а +а + (ЗЗ) 1 — а Ее можно интерпретировать примерно так: с вероятностью а требуется более одной пробы, с вероятностью ат — более двух и т. д. Соответствующее среднее число проб при успешном поиске равно (34) Как отмечалось выше, многочисленные тесты показали, что алгоритм Р с двумя независимыми хеш-функциями ведет себя, по сути, так же, как при равномерном исследовании для всех практических целей. В действительности двойное хеширование асимптотически эквивалентно равномерному исследованию в пределе при М вЂ” ~ со (см. упр. 70).
Этим завершается анализ равномерного исследования. Для изучения линейного исследовании и других типов разрешения коллизий следует строить более реалистичную теорию. Вероятностная модель, которая будет использоваться для этой цели, предполагает, что яге М~ яозможных "хеш-последовательностей" (35) а~ оз...охз 0 < а~ < М, равновероятны.
Здесь ау обозначает начальный хеш-адрес 1-го ключа, вставленного и таблицу. Среднее количество проб в случае успешного поиска прн работе по данному алгоритму поиска, как и выше, обозначим через См; зто значение представляет собой среднее количество проб, которые необходимы для поиска йго ключа, усредненное по всем 1 < 1. < Ж при равновероятных ключах и по всем хеш-последовательностям (35) (все послгдонательности считаются равновероятными).
Аналогична среднее количество проб, необходимых при вставке Х-го ключа, считая все последовательности (35) равновероятными, обозначим как Сч~, эта величина представляет собой среднее количество проб в случае неудачного поиска, начинающегося при наличии в таблице Х вЂ” 1 элемента. При использовании открытой адресации (36) /(М, Л) = (1 — — ) М'. (37) По определению также полагаем, что /(О, 0) = 1. Пусть д(ЛХ, Х, й) — число хешпоследонательностей (35), таких, что алгоритм оставляет позицию 0 пустой, позиции от 1 до и занятыми и позицию й + 1 — пустой.