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

коэффициент загрузки (а) 1/2 2/3 3/4 9/10

попадание при поиске 1.4 1.6 1.8 2.6 промах при поиске 1.5 2.0 3.0 5.5

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

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

Лемма 14.5 Сохраняя коэффициент загрузки меньшим, чем \-\/ft для линейного зондирования, и меньшим, чем 1 -1 / Г для двойного хеширования, можно обеспечить, чтобы в среднем для выполнения всех поисков требовалось менее t зондирований.

Установите значения выражений для промахов при поиске равными 1 и решите уравнения относительно а.

Например, для обеспечения, чтобы среднее количество зондирований для поиска было меньшим 10, необходимо сохранять таблицу пустой по меньшей мере на 32 процента при использовании линейного зондирования, но лишь на 10 процентов при использовании двойного хеширования. При необходимости обработки 10 элементов, чтобы иметь возможность выполнить безрезультатный поиск менее чем за 10 зондирований, требуется свободное пространство всего для Ю* дополнительных элементов. Для сравнения: при использовании раздельного связывания потребовалась бы дополнительная память для более чем 10 связей, а при использовании деревьев бинарного поиска потребовался бы вдвое больший объем памяти.

РИСУНОК 14.11 ЗАТРАТЫ НА ВЫПОЛНЕНИЕ ПОИСКА С ИСПОЛЬЗОВАНИЕМ ОТКРЫТОЙ АДРЕСАЦИИ

На этих графиках показаны затраты на построение хеш-таблицы, размер которой равен 1000, путем вставки ключей в первоначально пустую таблицу с использованием линейного зондирования (вверху) и двойного хеширования (внизу). Каждый вертикальный столбец представляет затраты на вставку 20 ключей. Серые кривые представляют теоретически предсказанные затраты (см. леммы 14.4 и 14.5).

Метод реализации операции remove, приведенный в программе 14.5 (повторное хеширование ключей, которые могут иметь путь поиска, содержащий удаляемый элемент), не годится для двойного хеширования, поскольку удаленный ключ может присутствовать во множестве различных последовательностей зондирования, затрагивающих ключи, разбросанные по всей таблице. Поэтому необходимо прибегнуть к другому методу, рассмотренному в конце раздела 12.3: удаленный элемент заменяется служебным элементом, помечающим позицию таблицы как занятую, но не соответствующим ни одному из ключей (см. упражнение 14.33).

Подобно линейному зондированию, двойное хеширование - неподходящее основание для реализации полнофункционального АТД таблицы символов, в котором необходимо поддерживать операции sort или select.

Упражнения

> 14.31 Приведите содержимое хеш-таблицы, образованной в результате вставки элементов с ключами EASYQUTIONb указанном порядке в первоначально пустую таблицу размером Л/ = 16 при использовании двойного хеширования. Воспользуйтесь хеш-функцией 11 Л: mod Л/для первоначального зондирования и второй хеш-функцией {к mod 3) + 1 для шага поиска (когда ключ - к-тгя буква алфавита).

> 14.32 Выполните упражнение 14.31 для М= 10.

14.33 Реализуйте удаление для двойного хеширования с использованием служебного элемента.

14.34 Измените решение упражнения 14.27, чтобы в нем использовалось двойное хеширование.

14.35 Измените решение упражнения 14.28, чтобы в нем использовалось двойное хеширование.

14.36 Измените решение упражнения 14.29, чтобы в нем использовалось двойное хеширование.

о 14.37 Реализуйте алгоритм, который аппроксимирует случайное хеширование, предоставляя ключ в качестве исходного значения для встроенного генератора случайных чисел (как в программе 14.2).

14.38 Предположите, что таблица, размер которой равен 10, заполнена наполовину, причем занятые позиции распределены случайным образом. Вычислите вероятность того, что все позиции, индексы которых кратны 100, заняты.

> 14.39 Предположите, что в коде реализации двойного хеширования присутствует ошибка, приводящая к тому, что одна или обе хеш-функции всегда возвращают одно и то же значение (не 0). Опишите, что происходит в каждой из следующих ситуаций: (/) когда первая функция неверна, (н) когда вторая функция неверна, ( 7) когда обе функции неверны.

14.5 Динамические хеш-таблицы

с увеличением количества ключей в хеш-таблице производительность поиска уменьшается. При использовании раздельного связывания время поиска увеличивается постепенно - когда количество оючей в таблице удваивается, время поиска удваивается. Это же справедливо по отношению к таким методам с открытой адресацией, как линейное зондирование и двойное хеширование для разреженных таблиц, но по мере заполнения таблицы затраты возрастают коренным образом и, что гораздо хуже, наступает момент, когда никакие дополнительные ключи вообще не могут быть вставлены. Эта ситуация отличается от деревьев поиска, в которых рост происходит естественным образом. Например, в RB-дереве затраты на поиск возрастают лишь несущественно (на одно сравнение) при каждом удвоении количества узлов в дереве.

Один из способов обеспечения роста в хеш-таблицах - удвоение размера таблицы, когда она начинает заполняться. Удвоение размера таблицы ~ дорогостоящая операция, поскольку все элементы в таблице должны быть вставлены повторно, однако она выполняется нечасто. Программа 14.7 - реализация роста путем удвоения при использовании линейного зондирования. Пример показан на рис. 14.12.

) n S ©

1 n S (х) G

1 n S x G

© ( n S x G

Р 1 n S x G(l)

012345678 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

РИСУНОК 14.12 ДИНАМИЧЕСКОЕ РАСШИРЕНИЕ ХЕШ-ТАБЛИЦЫ

На этой диаграмме продемонстрирован процесс вставки ключей AS Е R CHlNGXMPLe динамическую хеш-таблицу, которая расширяется путем удвоения хеш-значений, приведенных в верхней части рисунка, и разрешения конфликтов с помощью линейного зондирования. В четырех строках под ключами приводятся хеш-значения для размера таблицы равного 4, 8, 16 и 32. Начальный размер таблицы равен 4, затем ои удваивается до 8 для Е, до 16 для С и до 32 для G. При каждом удвоении размера таблицы для всех ключей выполняется повторное хеширование и повторная вставка. Все вставки выполняются в разреженные таблицы (менее чем на одну четверть для повторной вставки и от одной четверти до одной второй в остальных случаях), поэтому возникает мало конфликтов.