Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 42
Текст из файла (страница 42)
Пе вхо к глг юнюом Е С+Е-1 С+Е С+Е С+Š— Я С+Š— Я Е+1 — Я 1 — Я 1 — Я 1~-1 — 1. Выход, если К = ХЕТ В1, Переход к шагу 1Д прн непустом ТАВЬЕОВ. Переход к шагу ЬЗ с 1+- М, если 1 = — 1. Ъ4. Вставка. Выход но условию переполнения, если У = М вЂ” 1. РЕСХ 1 ЯТХ 7АСАНС1ЕЯ ЯТА ТАВ1.Е,1 1 — Я 1 — Я 1 — Я Увеличение 1У на 1.
тАВьебП +- К. Как н в программе С, переменная С описывает количество проб, а 5 указывает, успешным ли был поиск. Проигнорировать переменную Е, которм равна 1, можно только в случм проверки фиктивного узла ТАВ1.Е( — 11; ее среднее значение равно (С вЂ” 1)/М. Опыты с линейным исследованием показывают, что алгоритм хорошо работает в начале заполнения таблицы„однако по мере заполнения процесс замедляется, а длинные серии проб становятся все более частыми. Причину такого поведения можно понять, рассмотрев следующую гипотетическую хеш-таблицу при ЛХ = 19 и 1'х' = 9.
0 1 2 3 4 о 6 7 8 9 10 11 12 13 14 13 16 17 18 С~ ю - ~1+ ( — ) ) (неудачный поиск), (1- )) 11 1 См ю -~1+ — 1) (успешный поиск), 1М (22) (23) Темные квадраты представляют собой занятые позиции. Следующий ключ К, вставляемый в таблицу, попадет в одно нз десяти пустых мест, которые, однако, отнюдь не равновероятны, Так, К будет вставлен в позицию 11 при 11 < Ь(К) < 15, в то время как в позицию 8 он попадет, только когда А(К) 8. Следовательно, вероятность попадания в ячейку 11 в пять раз больше, чем вероятность попадания в ячейку 8; общая тенденция такова, что длинные списки стремятся стать еще длиннее.
Этого явления, тем не менее, самого по себе недостаточно для описания происходящего, поскольку подобная ситуация склвдывмтся и при использовании алгоритма С (вероятность увеличения списка из четырех элементов в четыре раза больше вероятности увеличения списка из одного элемента). Впрочем, настоящие неприятности начинаютсл при вставке в ячейку типа 4 или 16, когда разные списки объединятся в один (в то время как в алгоритме С списки никогда не удлинялись при вставке более чем на 1 элемент).
Следовательно, при приближении Х к М производительность алгоритма резко снижмтся. Ниже в этом разделе будет доказано, что среднее количество проб, требуемое алгоритмом 1, составляет примерно где а = Ю/М вЂ” — коэффициент заполненности таблицы. Таким образом, программа Ь практически столь же быстра, как н программа С при заполненности таблицы менее чем иа 75%, несмотря на то что программа С работает с неправдоподобно короткими ключами. С другой стороны, когда а -+ 1, лучшее, что можно сказать о программе Ь, — это то, что она работает медленно, но верно.
В самом деле, при 1Т = М вЂ” 1 в таблице имеется только одно вакантное место, а потому среднее число проверок при неудачном поиске составит (М + 1)/2; мы докажем также„ что среднее количество проб при успешном поиске в заполненной таблице равно примерно ь/хМ/8. Явление скучивания, которое делает линейное исследование дорогостоящим при почти заполненных таблицах, усугубляется при хпшировании методом деления, если вероятно появление последовательных значений ключей (Л, К+1, К+2,...), поскольку эти ключи будут иметь последовательные хеш-коды, Мультипликативное хеширование позволяет успешно разбить такие кластеры. Другой путь защиты от последовательных хеш-кодов состоит в установке на шаге 1,3 1 <- 1 — с вместо 1 +- ю' — 1. Можно использовать любое положительное значение с, взазьмно вросшее с М, поскольку последовательность проб в этом случае будет проверять в конечном счете все позиции таблицы без исключения.
Такое изменение немного замедлит работу программы Ь из-за проверки ю' < О. Уменьшение на с вместо уменьшения на 1 не устранит явление скучивання, так как теперь будут формироваться группы записей на расстоянии с одна от другой: формулы (22) и (23) останутся приемлемыми.
Однако в этой ситуации последовательные ключи (К, К+1, К+2,...) станут не помехой, а помощниками. Хотя фиксированное значение с не приводит к устранению скучивання, можно существенно улучшить ситуацию, сделав с зависящим от К. Эта идея позволяет выполнить важную модификацию алгоритма Ь, впервые предложенного Гюи де Бальбином (Опу Ое Ва154пе) (РЬ. В. 1Ьсьйз„Сайб 1пзк о[ТесЬпо!ояу (19б$), 149 — 150).
Алгоритм Т1 (Ошкрмшвл адресация с двойнььм хешпрованием). Этот алгоритм почти идентичен алгоритму Ь, но проверяет таблицу немного иначе, используя две хеш-функции: 6~ (К) и Ьз(К). Как обычно,:значения Аз(К) находятся в диапазоне от О до М вЂ” 1 включительно; функция Ьз(К) должна порождать значения от 1 до М вЂ” 1, взаимно простые с М. (Например, если М простое число, то Ьз(К) может быть любой величиной от 1 до М вЂ” 1 включительно; или, если М = 2, Аз(К) может быть любым нечегпнььм числом от 1 до 2"' — 1.) Ш. «Первое хеширование.) Установиты <- 6~ (К).
Р2. 1Первая проба.) Если ТАВЬЕ[П пуст, перейти к шагу 08. В противном случае, если КЕТ П) = К, алгоритм завершается успешно. РЗ. (Второе хеширование.) Установить с +- Ьз(К). [14. (Переход к следующему.) Установиты' е- 1 — с; если после этого 1 < О, установить 1~ — 1+ М. 115. (Сравнение.) Если ТАВЬЕ [13 пуст, перейти к шагу Вб. В противном случае, если КЕТЫ = К. алгоритм завершается успешно; иначе — вернуться к шагу 04. 118. (Вставка.) Если )Т = 51 — 1, выполнение алгоритма прекращается в связи с переполнением.
В противном случае установить Ж < — 1Т + 1, пометить узел ТАВ1,Е[П как занятый и установить КЕТЫ +- К. $ (25) Для вычисления Ла(К) было предложено несколько различных вариантов. Если М вЂ” простое число и Ь1(К) = К пюй М., можно положкгь Ьг(К) = 1 + (К пюй (М вЂ” Ц); однако, поскольку М вЂ” 1 четно, было бы лучше положить Ьт(К) = 1+ (К шоб (М вЂ” 2)). Это приводит к мысли о таком выборе М, что М и М вЂ” 2 были "простыми близнецами" наподобие 1021 и 1019. Кроме того, ьюжно взять Ьз(К) = 1 + ЦК/М) пюс1 (М вЂ” 2)) в связи с тем, что частное (К(М) может быть получено в регистре как побочный результат вычисления Ь1(К). Если М = 2 и используется мультипликативное хеширование, Ьт(К) может быть вычислена методом простого сдвига на пт дополнительных битов влево с вы- полнением операции "ИЛН" с 1, так что к последовательности команд (б) необходимо добавить следующее.
ЕВТА О Очистить гА. Я«а ш Сдвинуть гАХ па ят бнт влево. (24) оа ~1 гА«-гАч1. Эти операции выполняются быстрее метода деления, В каждом из предложенных выше методов Ь~ (К) и Ьт(К) существенно незави- симы — в том смысле, что для различных ключей вероятность совпадения Ь1 и Ья пропорциональна 11Мз, а не 11М. Эмпирические тесты показывают, что число проб в алгоритме 1) с независимыми хеш-функциями неотличимо от числа проб, требующихся при случайной вставке ключей в таблицу; в этой ситуации практически отсутствует "скучивание", или "кластеризация", как в алгоритме 1.
Можно также допустить зависимость Ьт(К) от Ь1(К), как было предложено Гари Кноттом (баку Кпогг) в 1968 году; например, при простом М можно положить Ь(К)=0; А1 — Ь1(К), если Ь1(К) > О. К Этот метод выполняется быстрее повторного деления, однако он вызывает опреде- ленную вторичную кластеризацию, что приводит к небольшому увеличению числа проб из-за повышения вероятности того, .что два илн несколько ключей пойдут по одному и тому же пути. Выведенные ниже формулы могут использоваться для определения того, превьппает ли выигрыш во времени хеширования потери времени на дополнительных пробах.
Алгоритмы 1 и В очень похожи, однако между ними найдется достаточно раз- личий, чтобы было полезно сравнить время работы соответствующих ИТХ-программ. двойн««м хешированием). Поскольку эта оиа представлена здесь без комментариев. Программа 12 (Ошкрмшая адресация с программа очень похожа на программу 1„ В программе г12 кн с — 1. 01 ЯТАВТ 00Х К 00 ЕИТА 0 08 017 ~И= 04 ЯТХ «+1(0:2) 05 ЕИТ1 « бб 1.0Х ТАВ1.Е,1 07 СИРХ Н 00 ЛЕ ЯУССЕЯЯ 00 ЛХХ 4Р 10 ЯВАХ 11 017 10 ЯТХ 18 ЕИТ2 Ц 10А 10 ЗН 0ЕС1 1б 11ИИ 17 ТИС1 10 СИРА б "-И-2= «+1(0:2) К 1,2 «+2 И ТАВ1.Е, 1 А — Я1 А — 51 А — З1 А — 81 А — Я1 С вЂ” 1 С-1 В С вЂ” 1 !У ЛЕ БВССЕББ С- 1 А( УР 10Х ТАВ1.Е, 1 С вЂ” 1 — 52 Аб 21 3ХМ2 ЗВ С вЂ” 1-52 Яб Яб 4Н 1.ОХ ЧАСАМС1ЕБ 1 — Я 27 Аб 3ХХ ОЧЕВР1.0М ! — 5 Счетчики частот А, С, 51, 52 здесь имеют тот же смысл, что и в программе С, приведенной выше.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
