Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 66
Текст из файла (страница 66)
Хешаравалие и леш-таблацы 3!3 ограничивает вероятность того, что объединенный размер всех вторичных хеш- таблиц надлинеен (в действительности вероятность того, что он равен или пре- вышает 4п). Теорема 11.10 Предположим, что мы сохраняем и ключей в хеш-таблице размером гп = п с ис- пользованием хеш-функции )з, выбираемой случайным образом из универсально- го класса хеш-функций. Тогда мы имеем Е ~~ пз (2п, где и — количество ключей, хешированных в ячейку 3.
а =а+2 (11.6) Мы имеем л1! ] =Е ~У п +2 =Е ~~! п +2Е (согласно уравнению (11.6)) (из линейности математического ожидания) = Е(п1+ 2Е = и+2Е (согласно уравнению (11.1)) (так как и не является случайной величиной) Для того чтобы вычислить сумму 2,',. „' ("'), заметим, что это просто общее количество коллизий. В соответствии со свойством универсального хеширования математическое ожидание значения этой суммы не превышает и 1 п(п — 1) Доказаавааьсавео. Начнем со следующего тождества, которое справедливо для любого неотрицательного целого а: Часть ГП. Структуры данны» 314 поскольку т = п.
Таким образом, Е ~~~ п~~ <п+2 = 2п, — 1 < 2п. Следствие 11. 11 Если мы сохраняем п ключей в хеш-таблице размером гп = п с использованием хеш-функции й, выбираемой случайным образом из универсального класса хешфункций, и устанавливаем размер каждой вторичной хеш-таблицы равным т. = пз, 1' = О, 1,..., т — 1, то математическое ожидание количества необходимой для вторичных хеш-таблиц в схеме идеального хеширования памяти не превышает величины 2п. Доказательство. Посюльку т = ~и для з = О, 1,..., т — 1, теорема 11.10 дает Е ~~~ гп = Е ~ пй < 2п, (11.7) что и требовалось доказать.
Следствие 11. 12 Если мы сохраняем п ключей в хеш-таблице размером т = п с использованием хеш-функции й, выбираемой случайным образом из универсального класса хешфункций, и устанавливаем размер каждой вторичной хеш-таблицы равным т пз, з = О, 1,..., т — 1, то вероятность того, что общее количество необходимой для вторичных хеш-таблиц памяти не менее 4п, меньше, чем 1/2. Доказательслгво.
Вновь применим неравенство Маркова (В.ЗО), Рг(Х ) г) < Е~Х~,Й, на этот раз — к неравенству(11.7), с Х = 2 ™ о т. и 1 = 4п: ,, (~=', ~, Е,=о'тЛ 4п у=о 2п <— 4п = 1/2 Из следствия 11.12 видно, что если проверить несколько случайным образом выбранных из универсального семейства хеш-функций, то достаточно быстро бу- плова П, Хеширование и кеш<таблачы дет найдена хеш-функция, обеспечивающая умеренные требования к количеству памяти. упражнения 11.5.1 * Предположим, что мы вставляем п ключей в хеш-таблицу размером т с использованием открытой адресации и равномерного хеширования.
Обозначим через р(п, т) вероятность отсутствия коллизий. Покажите, что р(п, т) < е "(" В1з (Указание: см. уравнение (3.12).) Докажите, что при п, превосходящем ~/т, вероятность избежать коллизий быстро уменьшается до нуля. Задачи 11.1. Наибольшее число исследований при хешировании Предположим, что мы используем хеш-таблицу размером т для хранения и < т/2 злементов. а Покажите, что в предположении равномерного хеширования вероятность того, что для любого з = 1, 2,...,и для вставки 1-го ключа требуется более й исследований, не превышает 2 ". б. Покажите, что для 1 = 1,2,..., и вероятность того, что вставка з-го ключа требует выполнения более 2 1к п исследований, не превышает 1/пз.
Пусп. Х; — случайная величина, обозначающая количество исследований, необходимое при вставке (-го ключа. В подзадаче (б) нужно было показать, что Рг(Х; > 2!кп) = 0(1/пз). Обозначим через Х максимальное количество исследований, необходимое при любой из и вставок: Х = шахз<,<„Хь в Покажите, что Рг (Х > 2 !к п) = 0(1/и). а Покажите, что математическое ожидание Е (Х ! длины наибольшей последовательности исследований равно О(1б и).
11.2. Длины цепочек при хешировании Предположим, что имеется хеш-таблица с и ячейками и разрешением коллизий методом цепочек. Пусть в таблицу вставлено и ключей. Вероятность каждого ключа попасть в любую из ячеек одинакова для всех ключей и всех ячеек. Пусть М вЂ” максимальное количество ключей в ячейке после того, как все ключи вставлены в таблицу. Ваша задача — доказать, что математическое ожидание Е !М] имеет верхнюю границу О(!к и/ !к 1к и). Часть Ш. Структуэаа данны Ззб о. Докажите, что вероятность Яь того, что в определенной ячейке находится ровно Й ключей, равна 6. Пусть Рь — вероятность того, что М = й, т.е.
вероятность того, что ячейка, содержащая наибольшее количество ключей, содержит их ровно Й. Покажите, что Рь < пЯы в. Воспользуйтесь приближением Стирлинга (3.18), чтобы показать, что Яь < еь/Йь. г. Покажите, что существует константа с > 1, такая, что Яьь < 1/п для йо = с18 и/ 1818 и.
Выведите отсюда, что Рь < 1/пз для й > ко = с 18 п/18 18 п. д. Докажите, что Сделайте вывод, что Е [М) = О(18 п/ 18 18 п). 11.3. Кводротичное исследование Предположим, что есть ключ к, который нужно найти в хеш-таблице с ячейками О, 1,..., т — 1, и пусть есть хеш-функция Ь, отображающая пространство ключей в множество (О, 1,..., гп — Ц. Схема поиска выглядит следующим образом. 1. Вычисляем значение з = )ь(й) и присваиваем г' = О. 2. Исследуем ячейку з на соответствие искомому ключу и. Если ключ найден или если ячейка пуста, поиск прекращается.
3. Присваиваем 1 = 1+ 1. Если 1 равно пз, поиск прекращается. В противном случае присваиваем з = (1+ з) шоб пь и возвращаемся к шагу 2. Предположим, что т является степенью 2. о. Покажите, что описанная схема представляет собой частный случай общей схемы "квадратичного исследования" с соответствующими константами сз и сз в уравнении (11.5).
6. Докажите, что этот алгоритм в наихудшем случае исследует каждую ячейку таблицы. 11.4. Хеширование и оутентификоция Пусть 'Н представляет собой класс хеш-функций, в котором каждая хеш-функция )ь Е 'Н отображает совокупность ключей У на множество (О, 1,..., т — 1). Глава ГЬ Хеширование и хеш-шаблицы 317 Мы говорим, что 'Н является Ь-уннверсальным, если для каждой фиксированной последовательности из й различных ключей (хц), х<~),..., х(~)) и случайным образом выбранной из Н хеш-функции Ь последовательность (Ь(х10), Ь(х(з)), ..., Ь(хуб)) с равной вероятностью является любой из гп" последовательностей длиной )е из элементов множества (О, 1,..., т — 1). а Покажите, что если семейство Я хеш-функций 2-универсально, то оно является универсальным.
б. Предположим, что совокупность Ьг представляет собой множество п-кортежей значений, выбранных из Жр — — (0,1,...,р — 1), где р — простое число. Рассмотрим элемент х = (хо, хы...,х„1) Е Ьг. Для любого п-кортежа а = (ао, аы., ., а„1) Е ЬГ определим хеш-функцию Ь„следующим образом: и-1 Ь,(х) = ~~> а х пюс1 р .
з=о Пусть Я = (Ь,). Покажите, что 'Н универсальна, но не 2-универсальна.(Указание: найдите ключ, для которого все хеш-функцни из 'Н дают одно и то же значение.) к Предположим, что мы слегка изменили 'Н из п. (б): для любого а е 17 и для любого Ь Е е.'р определим а-1 Ьвь(х) = ~~в а,х, + Ь шодР з=о и Не = (Ь~~).
Докажите, что класс Я' является 2-универсальным. (Указание: рассмотрите фиксированные и-кортежи х Е вз' и у Е с7, с х, ф у, для некоторого з? Что произойдет с Ь', (х) и Ь' „(у) при пробегании а, и Ь всех значений из Ур?) а Два друга по секрету договорились о хеш-функции Ь из 2-универсального семейства хеш-функций Н.
Каждая функция Ь е Я отображает совокупность ключей ЬГ на Ер, где р — простое число. Один из друзей шлет сообщение т другому через Интернет. Он подписывает это сообщение, пересылая одновременно с ним дескриптор 1 = Ь(т), а его друг проверяет„удовлетворяет ли полученная им пара (т, е) условию 1 = Ь(т). Предположим, что злоумышленник перехватывает сообщение (т, 1) и пытается обмануть получателя, подсунув ему собственное сообщение (т', ~'). Покажите, что вероятность того, что злоумышленник сможет успешно совершить подмену, не превышает 1/р, независимо от того, какими вычислительными мощностями он обладает, даже если он заранее знает семейство используемых хеш-функций 'Н. Часть !у!. Структуры данныя 3!В Заключительные замечании Алгоритмы хеширования прекрасно изложены в книгах Кнута (КпШЬ) (210]з и Гонне (боппег) !144].
Согласно Кнуту хеш-таблицы и метод цепочек были изобретены ГП. Лунем (Н.Р. 1пЬп) в 1953 году. Примерно тогда же Ж.М. Амдаль (б.М. Апи1аЫ) предложил идею открытой адресации. Универсальные множества хеш-функций были предложены Картером (Санат) и Вегманом (ииейшап) в 1979 году !57]. Схему идеального хеширования для статических множеств, представленную в разделе 11.5, разработали Фредман (Ргеь)!пап), Комлес (Кош!оз) и Семереди (Бхешегегй) [111]. Расширение этого метода для динамических множеств, обрабатывающее вставки и удаления за амортизированное ожидаемое время 0(1), предложено Дицфельбингером (П!егх(е1Ь!пбег) и др.
!85]. Вимеется русский перевод: Д. Киус. Искусство лрограииироаании т. К Сортироака и поиск, 2-е изд— Мс И.Д. "Вильямс", 2000. Глава 12. Бинарные деревья поиска Деревья поиска представляют собой структуры данных, которые поддерживают многие операции с динамическими множествами, включая ЯеАкСН, М!н!мОМ, МАх!мцм, Ркепесе550к, ЯОссе550к, 1нзект и Оееете. Таким образом, дерево поиска может использоваться и как словарь, и как очередь с приоритетами.
Основные операции в бинарном дереве поиска выполняются за время, пропорциональное его высоте. Для полного бинарного дерева с и узлами эти операции выполняются за время 9(18 и) в наихудшем случае. Однако, если дерево представляет собой линейную цепочку из и узлов, те же операции выполняются в наихудшем случае за время ез(п). Как будет показано в разделе 12.4, математическое ожидание высоты построенного случайным образом бинарного дерева равно 0(18 и), так что все основные операции над динамическим множеством в таком дереве выполняются в среднем за время 9(18 и).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
