Алгоритмы - построение и анализ (1021735), страница 60
Текст из файла (страница 60)
а тп — п а 1 — а Если хеш-таблица заполнена наполовину, ожидаемое количество исследований при успешном поиске не превышает 1.387; при заполненности на 90то это количество не превышает 2.559. Упражнения 11.4-1. Рассмотрите вставку ключей 1О, 22, 31, 4, 15, 28, 17, 88, 59 в хеш-таблицу длины тп = 11 с открытой адресацией и вспомогательной хешфункцией Ь' (к) = lс шот1 тп. Проиллюстрируйте результат вставки приведенного списка ключей при использовании линейного исследования, квадратичного исследования с ст = 1 и сз = 3, и двойного хеширования с Ьз (Й) = 1+ (Й шот1 (т — 1)).
1! .4-2. Запишите псевдокод процедуры Нлзн 13н.нте, описанной в тексте, и модифицируйте процедуру Клен 1нзект для обработки специального значения 0ЕЕЕТЕ0 (удален). 308 Часть И1. Структуры данных * 11.4-3. Предположим, что для разрешения коллизий мы используем двойное хеширование, те. хеш-функцию Ь (к, г) = 1Ь1 (и) + гЬз (и)) шоп т. Покажите, что если тп и Ьз (Й) для некоторого ключа /с имеют наибольший общий делитель д > 1, то неуспешный поиск ключа Ь проверяет (1/с~)-ю часть хеш-таблицы до того, как возвращается в ячейку Ь1 (й). Таким образом, когда а' = 1, т.е.
тп и Ьз (Й) взаимно простые числа, поиск может исследовать всю хеш-таблицу. (Указание: см. главу 31). 11.4-4. Пусть у нас есть хеш-таблица с открытой адресацией в предположении равномерного хеширования. Оцените верхнюю границу математического ожидания количества исследований при неуспешном поиске и при удачном поиске для коэффициентов заполнения таблицы 3/4 и 7/8. * 11.4-5. Пусть у нас есть хеш-таблица с открытой адресацией и коэффициентом заполнения о. Найдите ненулевое значение о, при котором математическое ожидание количества исследований в случае неуспешного поиска в два раза превышает математическое ожидание количества исследований в случае удачного поиска. Воспользуйтесь для решения поставленной задачи границами, приведенными в теоремах 11.6 и 11.8.
* 11.5 Идеальное хеширование Хотя чаще всего хеширование используется из-за превосходной средней производительности, возможна ситуация, когда реально получить превосходную производительность хеширования в наихудшем случае. Такой ситуацией является статическое множество ключей, т.е. после того как все ключи сохранены в таблице, их множество никогда не изменяется. Ряд приложений в силу своей природы работает со статическими множествами ключей.
В качестве примера можно привести множество зарезервированных слов языка программирования или множество имен файлов на компакт-диске. Идеальным хешированием мы называем методику, которая в наихудшем случае выполняет поиск за 0 11) обращений к памяти. Основная идея идеального хеширования достаточно проста. Мы используем двухуровневую схему хеширования с универсальным хешированием на каждом уровне (см.
рис. 11.6). Первый уровень по сути тот же, что и в случае хеширования с цепочками: п ключей хешируются в т ячеек с использованием хеш-функции Ь, тщательно выбранной из семейства универсальных хеш-функций. Однако вместо того, чтобы создавать список ключей, хешированных в ячейку т', мы используем маленькую вторичную хеш-шаблону Я со своей хеш-функцией Ь . Путем точного выбора хеш-функции Ь мы можем гарантировать отсутствие коллизий на втором уровне.
309 Глава 11. Хеш-таблицы и, а. а а~ --+а(,'!О )О Ь~ — -;-п~ 1 . 'и (а ас,' ьа"; '" п с а 0 — — (-в ( з ! ."з зх)4о~а)~~' и !)я~~~.'„ф~Ы~~~~~~за, Рис. 11.6. Использование идеального хеширования для хранения множества К = (10,22,37,40, 60, 70, 76) Рассмотрим детальнее пример на рис. 1 !.б, где показано сохранение статического множества ключей К = (10,22, 37, 40, 00, 70, 75) в хеш-таблице с использованием технологии идеального хеширования.
Внешняя хеш-функция имеет вид Ь (!с) = ((а!с + 6) шод р) шос! т, где а = 3, Ь = 42, р = 101 и т = 9. Например, )т (75) = 2, так что ключ 75 хешируется в ячейку 2. Вторичная хеш-таблица Я хранит все ключи, хешированные в ячейку у. Размер каждой таблицы Яу равен ту, и с ней связана хеш-функция Б. (lс) = Ца !с + 6 ) шод р) птос) т . Поскольку Ьз (75) = 1, ключ 75 хранится в ячейке 1 вторичной хеш-таблицы Яз.
Ни в одной из вторичных таблиц нет ни одной коллизии, так что время поиска в худшем случае равно константе. Для того чтобы гарантировать отсутствие коллизий на втором уровне, требуется, чтобы размер т хеш-таблицы Я был равен квадрату числа та ключей, хешированных в ячейку у. Такая квадратичная зависимость тп от и может показаться чрезмерно расточительной, однако далее мы покажем, что при корректном выборе хеш-функции первого уровня ожидаемое количество требуемой для хештаблицы памяти остается равным О (та). Мы выберем хеш-функцию из универсальных множеств хеш-функций, описанных в разделе 11.3.3.
Хеш-функция первого уровня выбирается из множества Нр, где, как и в разделе 11.3.3, р является простым числом, превышающим значение любого из ключей. Ключи, хешированные в ячейку 3, затем повторно хешируются во вторичную хеш-таблицу Я размером тп с использованием хешфункции )а;, выбранной из класса Нр ! Прн и; = паз = 1 ддя ячейки У хеш-функпня не нужна; прн выбора хеш-функцнн Ь,,а ((с) = = ((ай + Ь) шос) р) шос) паз дяя такой ячейки мы просто выбираем а = 6 = О. 310 Часть йй Структуры данных Работа будет выполнена в два этапа.
Сначала мы выясним, как гарантировать отсутствие коллизий во вторичной таблице. Затем мы покажем, что ожидаемое количество памяти, необходимой для первичной и вторичной хеш-таблиц, равно 0(п). Теорема 11.9. Если и ключей сохраняются в хеш-таблице размером т = из с использованием хеш-функции 6, случайно выбранной из универсального множества хеш-функций, то вероятность возникновения коллизий не превышает 1/2.
Доказалюельсгпво. Всего имеется Щ) пар ключей, которые могут вызвать коллизию. Если хеш-функция выбрана случайным образом из универсального семейства хеш-функций Н, то для каждой пары вероятность возникновения коллизии равна 1/т. Пусть Х вЂ” случайная величина, которая подсчитывает количество коллизий. Если т = пз, то математическое ожидание числа коллизий равно (Обратите внимание на схожесть данного анализа с анализом парадокса дней рождения из раздела 5.4.1.) Применение неравенства Маркова (В.29), Рг1Х > 1) < < Е [Х)/1, при 1 = 1 завершает доказательство. В ситуации, описанной в теореме 11.9, когда т = пз, произвольно выбранная из множества Н хеш-функция с большей вероятностью не приведет к коллизиям, чем приведет к ним.
Для данного множества К, содержащего п ключей (напомним„что К вЂ” статическое множество), найти хеш-функцию Ь, не дающую коллизий, возможно после нескольких случайных попыток. Если значение п велико, таблица размера пз = из оказывается слишком большой и приводит к ненужному перерасходу памяти. Тогда мы принимаем двухуровневую схему хеширования. Хеш-функция 6 первого уровня используется для хеширования ключей в т = и ячеек. Затем, если в ячейку 3 оказывается хешировано н ключей, для того чтобы обеспечить отсутствие коллизий, используется вторичная хеш-таблица о размером тп = пз. 1' Вернемся к вопросу необходимого для описанной схемы количества памяти.
Поскольку размер т 3-ой вторичной хеш-таблицы растет с ростом и. квадратично, возникает риск, что в целом потребуется очень большое количество памяти. Если хеш-таблица первого уровня имеет размер т = п, то, естественно, нам потребуется количество памяти, равное О (и), для первичной хеш-таблицы, а также для хранения размеров т вторичных хеш-таблиц и параметров ау и Ь, определяющих вторичные хеш-функции й (выбираемые из множества Нр, из раздела 11.3.3 (за исключением случая, когда и = 1; в этом случае мы просто принимаем а = Ь = 0)). Следующая теорема и следствия из нее позволяют нам вычислить границу суммарного размера всех вторичных таблиц. Глава 11. Хеш-таблицы Теорема 11.10.
Если мы сохраняем п ключей в хеш-таблице размером т = и с использованием хеш-функции Ь, выбираемой случайным образом из универ- сального множества хеш-функций, то Е [ < 2п, где и — количество ключей, хешированных в ячейку ). Доказаигельсгиво. Начнем со следующего тождества, которое справедливо для любого неотрицательного целого а: аз а+2 (11.6) Итак, мы имеем Е [ ( 1.|-2( ))] (в соответствии с (11.б)) + 2Е (в силу линейности математи- ческого ожидания) = Е~п!+2Е (в соответствии с (11.1)) = и+2Е (поскольку п не является слу- чайной переменной).
Для того чтобы вычислить сумму ~~~ „' 1"~), заметим, что это просто общее количество коллизий. В соответствии со свойством универсального хеширования, математическое ожидание значения этой суммы не превышает п'1 1 п(п — 1) п — 1 2/т 2т 2 так как т = п. Таким образом, =Е [ =Е[ ~о-1 Е ~~) п < п+ 2 — = 2п — 1 < 2п. п — 1 2 у=о Часть 111. Структуры данных 312 Следствие 11.11. Если мы сохраняем п ключей в хеш-таблице размером т = и с использованием хеш-функции и, выбираемой случайным образом из универсального множества хеш-функций, и устанавливаем размер каждой вторичной хеш-таблицы равным т = пз (у = О, 1,..., т — 1), то математическое ожидание количества необходимой для вторичных хеш-таблиц в схеме идеального хеширования памяти не превышает величины 2п. Доказательство.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
