Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 62
Текст из файла (страница 62)
Таким образом, когда с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о~а)~~' и ))я~~~.'„6(а))~р~~~за, Рис. 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п. Доказательство. Поскольку т = пз для 7' = О, 1,..., т — 1, согласно теоре- ме 11.10 мы получаем: Е;] =Е [ Е [ (1 1.7) < 2п, что и требовалось доказать Следствие 11.12.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
