AOP_Tom3 (1021738), страница 152
Текст из файла (страница 152)
Если при поиске К согласно определенной этим ключом последовательности встречается пустая позиция, можно сделать вывод о том, что К в таблице отсутствует (поскольку та же последовательность проверок должна выполняться при каждом поиске К). Этот общий класс методов назван огпкрмшвй адресацией (см. Ж. Ж. Ре~егэоп, 1ВМ Х ЯевеагсЬ й 11еее!ортел1 1 (1957), 130-146). Простейшая схема открытой адресации, известная как линейное исследование, использует цикдическую последовательность проверок Ь(К), Ь(К) — 1, ..., О, М вЂ” 1, М вЂ” 2,, Ь(К) + 1 (20) и описывается следующим образом.
Алгоритм 1 (Линейное исследование н вставка). Этот алгоритм выполняет поиск данного ключа К в таблице с М узлами. Если К отсутствует в таблице и таблица не полна, ключ К будет вставлен в таблицу. Узлы таблицы обозначаются как ТАЕЬЕИ, 0 < 1 < М, и могут быть двух типов — пустммп и заняп1ыми. В занятых узлах содержатся ключи КЕТП) и, возможно, другие паля. Вспомогательная переменная Х используется для отслеживания количества занятых узлов; она рассматривается как часть таблицы и унеличивается на 1 при каждой вставке нового ключа.
Алгоритм использует хеш-функцию Ь(К) н линейнун1 последователы<ость проб (20) для адресации таблицы. Модификации этой последовательности обсуждаются ниже. Ь1. [Хеширование.] Установить 1 < — А(К). (Теперь О < 1 < М.) Ь2. [Сравнение.] Если узел ТАВ~.8[П пуст, перейти к и~агу Ь4. В противном случае, если КЕУ Н3 = К, алгоритм успешно завершается. ЬЗ.
[Переход к следующему.] Установить 1 +- 1 — 1; если теперь 1 < О, установить 1 < — 1+ М. Вернуться к шагу 1,2. Ь4. [Вставка.] (Поиск оказался неудачным.) Если Х = М вЂ” 1, алгоритм завершается в связи с переполнением (условие полного заполнения таблицы полностью в данном алгоритме выглядит как Л = М вЂ” 1, а не как Ж = М; см. упр. 15). В противном случае установить Х < — Д' + 1, пометить узел ТАЕТЕ [13 как занятый и установить КЕУ [13 < — К. 1 На рис. 41 показано, что происходит при вставке семи ключей нашего примера с норвежскими цифрами согласно алгоритму Ь из примера с хеш-кодами 2, 7, 1, 8, 2, 8, 1; при этом последние трн ключа, ГЕИ, БЕКЕ и БУУ, смещены со своих начальных позиций 6(К). Рис.
41, Линейная открытая адресация. 01 БТАЕТ ЬОХ К 00 ЕИТА О ОЯ 017 =И= 04 БТХ я+1[0:2) 00 ЕИТ1 06 ЬРА К 07 ЛИР 2Г мх ~д~ 1»- А(й). Программа Ь (Линейное исследование н встиавка). Эта программа работает с ключами, занимающими полное слово; однако ключ О использовать нельзя, поскольку нулевое значение ключа означает, что данный узел в таблице свободен (другое решение состоит, например, в том, чтобы наложить на ключи условие неотрицательности, а пустые позиции пометить значением — 1), Размер таблицы — М (предполагвется, что это простое число), а узлы таблицы ТАЕЬЕ [13 имеют адреса ТАВЬЕ+г, О < 1 < М.
Для ускорения внутреннего цикла в ячейке ТАЕЬŠ— 1 содержится О. В ячейке ЧАСАИСТЕБ хранится значение М вЂ” 1 — )т'; и, наконец, гА гн Х, гП гн 1. Для ускорения внутреннего цикла этой программы из него удалена проверка "г < О", так что в нем остались только существенные части шагов Ь2 и ЬЗ. Общее время работы программы на фазе поиска составляет (7С+ 98+ 21 — 4о) и, а вставка в случае неудачного поиска добавляет к этой величине еще 8и.
1НС1 И+1 РЕС1 1 СИРА ТАВЕЕ,1 ЗЕ БОССЕББ ЕРХ ТАВЕЕ,1 ЗХНЕ ЗВ 11Н ВВ ЕОХ ЧАСАНС1ЕБ ЭХЕ ОУЕЕРЕОН 00 8Н 00 ЗН 10 2Н П 12 10 14 15 4Н 10 ЪЗ. Пе ехо к сле хю ем Е С+Š— 1 С+Е С+Е С+Š— 5 С+Š— 5 Е+1 — 5 1 — 5 1 — 5 1 ~- 1 — 1. Гы Выход, если К = КЕТЫ. Переход к шагу ЕЗ прн непустом ТАВЗЕН . Переход к шагу 1 3 с 1 с — Л1, если 1 = -1, Ъ4. Вставка Выход по условию переполнения, если Х=М вЂ” 1. 1 — 5 1 — 5 1 — 5 РЕСХ 1 БТХ УАСАНС1ЕБ БТА ТАВЕЕ,1 17 10 10 Увеличение 1У на 1. тАВееП1 ~.— К.
Как и в программе С, переменная С описывает количество проб, а 5 указывает, успешным ли был поиск. Проигнорировать переменную Е, которая равна 1, можно только в случае проверки фиктивного узла ТАВЕЕ[-1); ее среднее значение равно (С вЂ” 1) /М. Опыты с линейным исследованием показывают, что алгоритм хорошо работает в начале заполнения таблицы, однако по мере заполнения процесс замедляется, а длинные серии проб становятся все более частыми.
Причину такого поведения можно понять, рассмотрев следующую гипотетическую хеш-таблицу при ЛХ = 19 н Ж = 9. О 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 (21) С~ ъ — ~1+ ~ — ) / (неудачный поиск), г~ Ь-а)/ 1/ 1 Сн ш -~1+ — ~ (успешный поиск), 21 1 — а/ (22) (23) Темные квадраты представляют собой занятые позиции.
Следующий ключ К, вставляемый в таблицу, попадет в одно из десяти пустых мест, которые, однако, отнюдь не равновероятны. Так, К будет вставлен в позицию 11 при 11 < 5(К) < 15, в то время как в позицию 8 он попадет, только когда Ь(К) = 8. Следовательно, вероятность попадания в ячейку 11 в пять раз больше, чем вероятность попадания в ячейку 8; общая тенденция такова, что длинные списки стремятся стать еще длиннее. Этого явления, тем не менее, самого по себе недостаточно для описания происходящего, поскольку подобная ситуация складывается и при использовании алгоритма С (вероятность увеличения списка из четырех элементов в четыре раза больше вероятности увеличения списка из одного элемента). Впрочем, настоящие неприятности начинаются при вставке в ячейку типа 4 или 16, когда разные списки объединятся в один (в то время как в алгоритме С списки никогда не удлинялись при вставке более чем на 1 элемент).
Следовательно, при приближении )У к М производительность алгоритма резко снижается. Ниже в этом разделе будет доказано, что среднее количество проб, требуемое алгоритмам [п составляет примерно где и = 1У/ЛТ вЂ” — коэффициент заполненности таблицы. Таким образом, програм- ма Ь практически столь же быстра, как и программа С при заполненности таблицы менее чем на 75%, несмотря на то что программа С работает с неправдоподобно короткими ключами. С другой стороны, когда а -+ 1, лучшее, что можно сказать о программе Ь, — это то, что она работает медленно, но верно. В самом деле, при зУ = М вЂ” 1 в таблице имеется только одно вакантное место, а потому среднее число проверок при неудачном поиске составит (М + 1)/2; мы докажем также, что среднее количество проб при успешном поиске в заполненной таблице равно примерно ь/хМ~8. Явление скучивания, которое делает линейное исследование дорогостоящим при почти заполненных таблицах, усугубляется при хешировании методом деления, если вероятно появление последовательных значений ключей (К, К+1, К+2,...), по- скольку зти ключи будут иметь последовательные хеш-кодьь У1ультипликативное хеширонание позволяет успешно разбить такие кластеры.
Другой путь защиты от посяедовательных хеш-кодов состоит в установке на шаге 1,3 1 +- 1 — с вместо 1 +- 1 — 1. Можно использовать любое положительное значение с, взаимна простое с М, поскольку последовательность проб в этом случае будет проверять в конечном счете все позиции таблицы без исключения. Такое изменение немного замедлит работу программы Ь из-за проверки 1 с О. Уменьшение на с вместо уменьшения на 1 не устранит явление скучивания, так как теперь будут формироваться группы записей на расстоянии с одна от другой; формулы (22) и (23) останутся приемлемыми. Однако в этой ситуации последовательные ключи (К, К+1, К+2,...) станут не помехой, а помощниками, Хотя фиксированное значение с не приводит к устранению окучивания, можно существенно улучшить ситуацию, сделав с зависящим от К, Эта идея позволя- ет выполнить важную модификацию алгоритма Ь, впервые предложенного Гюи де Бальбином (Оиу с1е Ва!Ь1пе) [РЬ.
П. 1Ьев1в, Са1К. 1пвп о[ ТесЬпо)ойу (1968), 149-150]. Алгоритм Р (Открытая адресация с двойным хешированием). Этот алгоритм почти идентичен алгоритму Ь, но проверяет таблицу немного иначе, используя две хеш-функции: 1п(К) и Ьз(К). Как обычно, значения Ь,(К) находятся в диапазоне от О до М вЂ” 1 включительно; функция Ьа(К) должна порождать значения от 1 до М вЂ” 1, вваильна яростные с М.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
