Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 44
Текст из файла (страница 44)
При использовании линейного исследования (алгоритм 1) можно поступить более разумно, еглн, конечно, затратить дополнительные усилия на удаление. Алгоритм К (Удаление при линейном исследовании). Пусть хеш-таблица построена по алгоритму 1.. Алгоритм удаляет запись из данной позиции ТАВЕЕИ. К1. ]Освобождение ячейки.) Пометить ТАВ1.ЕП) как пустую и установить з +- 1, К2. ]Уменьшение Е] Установиты +- 1 — 1 и, если 1 стало отрицательным, установить 1+- з+М. КЗ.
]Проверить ТАВЗЕН).] Если ТАВ1ЕЫ пуст, алгоритм завершается. В противном случае установить т +- А(ЕЕТП)) -- первоначальный хеш-адрсс ключа, который хранится в позиции ь'. Если з < т < у нли если г < з < 1 либо у < 1 < т (другимн словами, если т лежит циклически между 1 и з'), вернуться к шагу К1. К4. [Переместить запись.] Установить ТАВ1 Е Ц) +- ТАВЕЕ Я и вернуться к шагу К1. 3 В упр. 22 показано, что этот алгоритм не вызывает снижения производительности; другими словами, среднее количество проб, предсказанное в формулах (22) и (23), останется тем же (более слабый результат для вставки в дерево был доказан в теореме 6.2.2Н). Однако корректность алгоритма В сильно зависит от того факта.
что используется линейное исследование хеш-таблицы, а потому аналогичный алгоритм удаления при применении алгорит»ла 0 отсутствует. Среднее время работы алгоритма В анализируется в упр. 64. Конечно, при использовании метода цепочек с различнымн списками для всех возможных хеш-значений удаление не вызывает проблем, поскольку сводится к простому удалению из связанного линейного списка. Удаление для алгоритма С обсуждается в упр. 23. Алгоритм В позволяет перемещать некоторые элементы таблицы, что может оказаться нежелательно (например, если на элементы имеются ссылки извне).
Другой подход к проблеме удаленно основывается на адаптированин некоторых идей, используюцгихся при сборке мусора (см. раздел 2.3.5): можно хранить количество ссылок с каждым ключом, говорящим о том, как много других ключей сталкивается с ним; тогда при обнуления счетчика можно преобразовать такие ячейки в пустые. Друтой метод состоит в проходе по всей таблице, как только наберется слиппсом много удаленных элементов, замене всех незанятых позиций пустыми и просмотре всех оставшихся ключей, чтобы выяснить, какие незанятые позиции все еще имеют статус "удаленных". Эти методы, позволяющие избежать перемещения элементов в таблице и работающие с любой хеш-технологией, были впервые предложены в работе Т, Пиву» апд Е. Оо1о, Х 1пйппабоп Ргос.
3 (1960), 1-12. «Анализ алгоритмов. Поскольку при хешировании необходимо опираться на теорию вероятностей, очень важнс» знать поведение метода хеширования в среднем. Наихудший случай использования этих алгоритмов невообразимо плох, поэтому следует убедиться в том, что поведение в среднем очень хорошее. Прежде чем приступить к анализу линейного исследования и других методов хеширования, рассмотрим приближеннук» модель ситуации, называемой равно«»ериным исследованием.
В этой модели, предложенной В. В. Петерсоном (Ж. Ж. Регегэоп) (1ВМ Х НеяеагсЬ 3г Пе»е1ор»лепГ 1 (1967), 136 — 136), предполагается, что каждый ключ размещается в совершенно случайном месте таблицы, так что все (' ) возможных конфигураций из А» занятых и М вЂ” А» пустых ячеек равновероятны. В данной модели игнорируются эффекты первичного или вторичного скучнвания; предполагается, что занятость каждой конкретной ячейки не зависит от занятости остальных. Тогда вероятность того, что для вставки (Х+ 1)-го элемента необходимо в точности г проб, равна количеству конфигураций, в которых г — 1 данная ячейка занята. а еще одна пуста, деленному на ( ), т. е.
Таким образом, среднее количество проб в случае равномерного исследования со- ставляет м Сд —— ~~» гР„= М+1 — ~~» (М+1 — г)Р„ »ю! =М+1 — (М вЂ” Н) =, 1 < Х < М, (32) М-Я+1 М-Я+1' (Мы уже решали, по существу, ту же задачу в связи со случайной выборкой в упр. 3.4.2-5,) Полагая а = Н~ЛХ, точную формулу для С~ можно заменить приближенной: — = 1+О+О +О + (33) 1 — и Яе можно интерпретировать примерно так: с вероятностью а требуется более одной пробы, с вероятностью аз — более двух и т. д.
Соответствующее среднее число проб при успешном поиске равно 1 ч, М+17 1 1 1 Сн= — з С,'= — ( — + — + "+ ж ~0 Н М+1 М М-Н+2 М+1 1 1 = — (Нм+~ — Нм-нч.~) е — !и —. Х а 1 — а (34) (35) аг ат...ан, 0 < а < М, равновероятны. Здесь а обозначает начальный хеш-адрес у-го ключа, вставленного в таблицу. Среднее количество проб в случае успешного понсюз при работе по данному алгоритму поиска, как н выше, обозначим через См; это значение представляет собой среднее количество проб, которые необходимы для поиска йго ключа, усредненное по всем 1 < й < Х при равновероятных ключах и по всем хеш-последовательностям (35) (все последовательности считаются равновероятными).
Аналогично среднее количество проб, необходимых при вставке Л'-го ключа, считая все последовательности (35) равновероятными, обозначим как Сщ ,, эта величина представляет собой среднее количество проб в случае неудачного поиска, начинающегося при наличии в таблице Ю-1 элемента. При использовании открытой адресации Как отмечалось выше, многочисленные тесты показали, что алгоритм В с двумя независимыми хеш-функциями ведет себя, по сути, так же, как при равномерном исследовании для всех практических целей, В действительности двойное хеширование асимптотически эквивалентно равномерному исследованию в пределе при ЛХ -+ со (см. упр. 7О).
Этим завершается анализ равномерного исследования. Для изучения линейного исследования и других типов разрешения коллизий следует строить более реалистичную теорию. Вероятностная модель, которая будет использоваться для этой цели, предполагает, что все Лйл возможных "хеш-последовательностей" Ф-з с = — ~'с,', а=о (3Е) так что можно вывести одну величину из другой, как в (34). Строго говоря, даже эта уточненная модель ие лигпена недостатков. Первый из ннх заключается в том, что не все хеш-последовательности равновероятны, поскольку сами ключи различны.
Это делает вероятность того, что аг = аз, немного меньше, чем 1/М; однако отличие обычно незначительно, поскольку количество всех различных ключей, как правило, гораздо больше, чем М (см. Упр. 24). Более того, хорошая хеш-Функция способна использовать неслучайность типичных данных, дополнительно уменьшая вероятность того, что аг = аз, таким образом, оценки числа проб будут пессимистическими, Другая неточность модели указана на риг. 43: ключи, встретившиеся ранее (за небольшими исключениями), ищутся чаще других. Таким образом, оценки Ск окажутся двазццы пессимистичными и на практике алгоритмы будут иметь ббльшую произвсдительностгч чем предсказано в результате нашего анализа.
С учетом этих предостережений можно приступать к еточнолгуе анализу линейного исследованняе. Пусть |(М, Лг) — число хеш-последовательностей (35), таких, что позиция 0 таблицы будет пуста после вставки ключей с помощью алгоритма 1,. Из циклической симметрии линейного исследования следует, что позиция О пуста так же часто, как и любая другая позиции, поэтому она пуста с вероятностью 1 — Ж~М; другими словами У(М,Щ = (1 — — )М'.
(37) По определению также полагаем, что у(0, 0) = 1. Пусть д(М, )т', к) — число хеш- последовательностей (35), таких, что алгоритм оставляет позицию 0 пустой, позиции от 1 до й занятыми н позицию (с+ 1 — пустой. Имеем д(М,гьг,й) = ~ )у(к+1,9)ЯМ-9-1,Х вЂ” к), г (38) поскольку все такие хеш-последовательности состоят из двух подпоследовательностей. Первая (в ией содержится к элементов а, < к) оставляет позицию 0 пустой, а позиции от 1 до гс занятыми; вторая (в ней содержится )т' — й элементов ау > й + 1) оставляет позицию к + 1 пустой. Существует 7 (й+1, й) последовательностей первого типа, 7'(М-гс-1, Ф-lс) последовательностей второго типа н (,) способов их смешения.
И, наконец, положим Ра равным вероятности того, что при вставке (дд+ 1)-го ключа требуется в точности к+ 1 проб. Отсюда следует (см. Упр. 25), что Ра М™(д(М,зт, гс)+ 9(М,М, й+1) + ' '+ д(МЯ,зт)) ° (39) ь Автор не может не делать вставку автобмографнческого характера: я впервые сформулвровал нредлагаемый вывод в 1962 году, вскоре восле начала работы над "Искусством прогре имнроеакнят Поскольку зто был верный успешно ороаналнзнровавный мною нетрнвнальный алгорнтм, он оказал сильное вчнянне на стогкттот зтнх книг.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
