Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 65
Текст из файла (страница 65)
ти т — 1 ги — 2 т — г'+2 Теперь воспользуемся уравнением (В.25) для получения границы ожидаемого ко- личества исследований: Е[Х) =~~~ Рг(Х >1) в=1 < ~~, 'о~ — з е=1 из з=о 1 1 — о Полученная граница 1/(1 — а) = 1+ гг+ аз+ ггз+ имеет интуитивную интерпретацию.
Одно исследование выполняется всегда. С вероятностью, приблизительно равной гг, первое исследование проводится над заполненной ячейкой, и требуется выполнение второго исследования. С вероятностью, приблизительно равной ггз, две первые ячейки оказываются заполненными, и требуется проведение третьего исследования, и т.д. Если гг — константа, то теорема 11.6 предсказывает, что неудачный поиск выполняется за время 0(1). Например, если хеш-таблица заполнена наполовину, то среднее количество исследований при неудачном поиске не превышает 1/(1 — .6) = 2. При заполненности хеш-таблицы на 90% среднее количество исследований не превышает 1/(1 — .9) = 10. Теорема 11.6 практически непосредственно дает оценку производительности процедуры НАИН-1НЗЕКТ.
Следствие 11. 7 Вставка элемента в хеш-таблицу с открытой адресацией и коэффициентом заполнения а в предположении равномерного хеширования требует в среднем не более 1/(1 — а) исследований. Доказаягельсгаво. Элемент может быть вставлен в хеш-таблицу только в том случае, если в ней есть свободное место, так что а < 1. Вставка ключа требует проведения неудачного поиска, за которым следует размещение ключа в найден- Гаева !!. Хешираваиие и хеив-табвици 309 иой пустой ячейке.
Следовательно, математическое ожидание количества иссле- дований не превышает 1/(1 — вз). Вычисление математического ожидания количества исследований при успешном поиске требует немного больше усилий. Теорема 11. В Математическое ожидание количества исследований при удачном поиске в хеш- таблице с открытой адресацией и коэффициентом заполнения вз < 1, в предполо- жении равномерного хеширования и равновероятного поиска любого из ключей, не превышает 1 1 — 1п 1 — ет п~ т — 1 в=о и — ! т е 1 и а т — г в=о 1 1 ге !е ь=т-а+! ! Ги < — ~ (1/к) Их еи-и (согласно неравенству (А.12)) 1 т — 1п св т — п 1 1 — 1п «е 1 — ее В наполовину заполненной хеш-таблице ожидаемое количество исследований при удачном поиске оказывается меньше 1.387.
Если хеш-таблица заполнена на 90%„ожидаемое количество исследований меньше 2.559. Упражнения 11.4.1 Рассмотрите вставку ключей 10, 22, 31, 4, 15, 28, 17, 88, 59 в хеш-таблицу длиной т = 11 с открытой адресацией и вспомогательной хеш-функцией Ь'(!е) = !е. Проиллюстрируйте результат вставки приведенного списка ключей при исполь- юваиии линейного исследования, квадратичного исследования с сз = 1 и сз = 3 н двойного хеширования с )з|(Й) = !с и Йз(Й) = 1 + (!с шов! (т — 1)).
Докозоовольетоо. Поиск ключа к выполняется той же последовательностью исследований, что и его вставка. В соответствии со следствием 11.7, если !е был (1+ 1)-м ключом, вставленным в хеш-таблицу, то математическое ожидание количества проб при поиске !е не превышает 1/(1 — г/т) = т/(т — !). Усреднение по всем и ключам в хеш-таблице дает нам среднее количество исследований при удачном поиске: Часть Ш.
Структуры даииы» 3!О П.4.г Запишите псевдокод процедуры Нлзн-Рееете, описанной в тексте, и модифицируйте процедуру Нлзн-1мзккт так, чтобы она могла обрабатывать специальное значение пн.ктю. 11.4.3 Рассмотрим хеш-таблицу с открытой адресацией при условии равномерного хеширования. Найдите верхнюю границу ожидаемого количества исследований при неудачном поиске и ожидаемого количества исследований при удачном поиске, когда коэффициент заполнения равен 3/4 и когда он равен 7/8. Л.4.4 * Предположим, что для разрешения коллизий мы используем двойное хеширование, те.
хеш-функцию Ь(и,1) = (Ьг(к) + йз(/г)) щи т. Покажите, что если гл и /зз(к) для некоторого ключа и имеют наибольший общий делитель Н > 1, то неудачный поиск ключа /с проверяет (1/д)-ю часть хеш-таблицы до того, как возвращается в ячейку йз(й). Таким образом, когда г( = 1, т.е. т и йз(/с) — взаимно простые числа, поиск может исследовать всю хеш-таблицу. (Указание: см. главу 31.) 11.4.5 * Рассмотрим хеш-таблицу с открытой адресацией и коэффициентом заполнения а. Найдите ненулевое значение а, при котором математическое ожидание количества исследований в случае неудачного поиска в два раза превышает математическое ожидание количества исследований в случае удачного поиска.
Воспользуйтесь для решения поставленной задачи границами, приведенными в теоремах 11,6 и 11.8. * 11.5. Идеальное хеширование Хотя чаше всего хеширование используется из-за превосходной средней производительности, возможна ситуация, когда можно обеспечить превосходную производительность хеширования в наихудшем случае. Такой ситуацией является статическое множество ключей, т.е. после того как все ключи сохранены в таблице, их множество никогда не изменяется. Ряд приложений в силу своей природы работает со статическими множествами ключей. В качестве примера можно привести множество зарезервированных слов языка программирования или множество имен файлов на компакт-диске.
Идеальньии хеигированием мы называем методику, которая выполняет поиск за О(1) обращений к памяти в наихудшем случае. Для создания схемы идеального хеширования мы используем двухуровневую схему хеширования с универсальным хешированием на каждом уровне (см. рис. 11.6). Глава 11.
Хеширование и леш-таблицы 7»си ии Ьа = ао о', ч —.;,— ) 4 ) 0,1 а4т', 1 .иг а, 2; — '., -г ) Ф')11)7"15 Сй)с!3 75. О ! ' 3 4 5 6 7 В 4 и»» а» Ь» --, -с» 1 1 0» 0370' , и4 101'79135 46~52) 77 37 а о с 2 э 4 5 4 7 В 4»»» 1»»2 и 14 С5 Рнс. 11.6. Использование идеального хеширования дяя хранения множессва К = (10, 22, 37, 40, 52, бб, 70, 72, 75). Внешняя хеш-функция имеет внд Ь(!с) = ((ай + Ь) шоб р) шоб т, где а = 3, Ь = 42, р = 101 и т = 9. Например, Ь(75) = 2, так что ключ 75 хешируется в ачейку 2 таблицы Т. Всоричная хеш-таблица Ял хранит все ключи, хешированные в ячейку 7. Размер каждой таблицы Ял Равен т„= пг, и с ней свазана хеш-фУнкциа йл(/с) = ((а,!с+ Ьл) шод Р) пюд т,.
Посволькг Ьг(75) = 7, ключ 75 хранится в ячейке 7 вторичной хеш-таблицы Яг. Ни в одной из вторичных таблиц нет ии одной коллизии, так что время поиска в худшем случае равно константе. Первый уровень по сути тот же, что и в случае хеширования с цепочками: и ключей хешируются в т ячеек с использованием хеш-функции Ь, тщательно выбранной из семейства универсальных хеш-функций.
Однако вместо того, чтобы создавать список ключей, хешированных в ячейку 1, мы используем маленькую вторичную хеш-твблицу Я со связанной с ней хеш-функцией Ь . Путем аккуратного выбора хеш-функцин Ь мы можем гарантировать отсутствие коллизий на втором уровне. Чтобы гарантировать отсутствие коллизий на втором уровне, требуется, чтобы размер т хеш-таблицы Я был равен квадрату числа и ключей, хешированных в ячейку 7'. Такая квадратичная зависимость т от п. может показаться чрезмерно расточительной, однако далее мы покажем, что при должном выборе хеш-функции первого уровня ожидаемое количество требуемой для хеш-таблицы памяти можно ограничить значением 0(п).
Мы выбираем хеш-функцию из универсальных классов хеш-функций из раздела 11.3.3. Хеш-функция первого уровня выбирается из класса 74р, где, как и в разделе 11.3.3, р является простым числом, превышающим значение любого из ключей. Ключи, хешированные в ячейку 7, затем повторно хешируются во вюричную хеш-таблицу Я размером т с использованием хеш-функции Ь, выбранной из класса 'Нр Работа будет выполнена в два зтапа. Сначала мы выясним, как гарантировать отсутствие коллизий во вторичной таблице.
Затем мы покажем, что общее ожидаемое количество памяти, необходимой для первичной и всех вторичных хештаблиц, равно 0(п). гнри и = са = 1 дяв ячейки 2' хеш-функция ие пужая; при выборе каи-функпии Ь 4(Я) = ((аа + Ь) икк1 р) шод т дяя такой ячейки мы просто выбираем а = Ь = О.
Часть Ш. Структуры даннын Теорема 11.9 Предположим, что и ключей сохраняются в хеш-таблице размером т = иг с использованием хеш-функции 6, случайно выбранной из универсального класса хеш-функций. Тогда вероятность возникновения коллизий оказывается меньше 1/2. Доказательство. Всего имеется ('г) пар ключей, которые могут вызвать коллизию. Если хеш-функция выбрана случайным образом из универсального семейства хеш-функций 9(, то для каждой пары вероятность возникновения коллизии равна 1/т.
Пусть Х вЂ” случайная величина, которая подсчитывает количество коллизий. Если т = иг, то математическое ожидание числа коллизий равно г и — и 1 г 2 иг < 1/2. (Обратите внимание на схожесть данного анализа с анализом парадокса дней рождения из раздела 5.4.1.) Применение неравенства Маркова (В.ЗО), Рг(Х > г) ( Е [Х],Ч, при 1 = 1 завершает доказательство. В ситуации, описанной в теореме 11.9, когда гп = иг, произвольно выбранная из множества Я хеш-функция с большей вероятностью ке приведет к коллизиям, чем приведет к ним.
Для заданного множества К, содержащего и ключей (напомним, что К вЂ” статическое множество), найти хеш-функцию Ь, не дающую коллизий, можно после нескольких случайных попыток. Однако если значение и велико, таблица размером т = иг оказывается слишком большой и приводит к ненужному перерасходу памяти.
Поэтому мы принимаем двухуровневую схему хеширования и используем подход из теоремы 11.9 только для хеширования записей в пределах каждой ячейки. Внешняя хеш-функция 6 первого уровня используется для хеширования ключей в гп = и ячеек. Затем, если в ячейку 1 хешировано и. ключей, для того чтобы обеспечить отсутствие коллизий и поиск за константное время, используется вторичная хештаблица 5. размером тп = иг.
Вернемся к вопросу необходимого для описанной схемы количества памяти. Поскольку размер 1-й вторичной хеш-таблицы т растет с ростом и квадратично, возникает риск, что в целом потребуется очень большое количество памяти. Если хеш-таблица первого уровня имеет размер т = и, то, естественно, нам потребуется количество памяти, равное О(гь), для первичной хеш-таблицы, а также для хранения размеров тп. вторичных хеш-таблиц и параметров а и Ь, определяющих вторичные хеш-функции 6, выбираемые из класса Яр,„из раздела 11.3.3 (за исключением случая, когда и = 1; в этом случае мы просто принимаем а = Ь = О). Следующая теорема и следствие из нее позволяют нам вычислить границу суммарного размера всех вторичных таблиц. Второе следствие Глава 3!.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
