Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 62

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 62)

При использовании данного метода мы обычно стараемся избегать некоторых значений т. Например, т не должно быть степенью 2, поскольку если т = 2Р, то л(к) представляет собой просто р младших битов числа 1е. Если только заранее не известно, что все наборы младших р битов ключей равновероятны, лучше строить хеш-функцию таким образом, чтобы ее результат зависел от всех битов ключа. В упр.

11.3.3 требуется показать неудачность выбора гп = 2Р— 1, когда ключи представляют собой строки символов, интерпретируемые как числа в системе счисления с основанием 2", поскольку перестановка символов ключа не приводит к изменению его хеш-значения. Зачастую хорошие результаты можно получить, выбирая в качестве значения лп простое число, достаточно далекое от степени двойки. Предположим, например, что мы хотим создать хеш-таблицу с разрешением коллизий методом цепочек для хранения порядка п = 2000 символьных строк, размер символов в которых равен 8 бит.

Нас устраивает проверка в среднем трех элементов при неудачном поиске, так что мы выбираем размер таблицы равным т = 701. Число 701 выбрано как простое число, близкое к величине 2000/3 и не являюшееся степенью 2. Рассматривая каждый ключ й как целое число, мы получаем искомую хеш-функцию Ь(а) = к шое) 701 .

Часть Лб Структуры данных 11З.2. Метод умножении Построение хеш-функции митппдам умножения выполняется в два этапа. Сначала мы умножаем ключ и на константу 0 < А < 1 и выделяем дробную часть полученного произведения. Затем мы умножаем полученное значение на т и применяем к нему функцию "пол". Короче говоря, хеш-функция имеет вид )ь()с) = ~тп(кА шос(1)! где выражение *')сА шос( 1о означает получение дробной части произведения )сА, т.е. величину lсА — 1дА).

Преимущество метода умножения заключается в том, что значение тп перестает быть критичным. Обычно величина т из соображений удобства реализации функции выбирается равной степени 2 (тп = 2Р для некоторого натурального р), поскольку такая функция легко реализуема на большинстве компьютеров. Пусть у нас имеется компьютер с размером слова ш бит и )с помещается в одно слово.

Ограничим возможные значения константы А дробями вида л/2, где л — целое число из диапазона 0 < л < 2 . Тогда мы сначала умножаем и на еп-битовое целое число л = А 2 . Результат представляет собой 2ш-битовое число г12 + то, где т.т — старшее слово произведения, а го — младшее. Старшие р бит числа то представляют собой искомое р-битовое хеш-значение (рис. 11.4). ш бит (::::.""::.:: й:, -.:-':.:::;.) х,:.." -: а;ьх,Ал 2.",'. .т'- -; З во.

. — ' Извлечение р бит ~ й(й) ! Рис. 11УК Хеширование методом умнсокения. ш-битовое представление ключа й умножается иа ш-битовое значение о = А 2 . р старших битов младшей побитовой половины произведения образует искомое хеш-значение п(й) Хотя описанный метод работает с любыми значениями константы А, одни значения дают лучшие результаты по сравнению с другими. Оптимальный выбор зависит от характеристик хешируемых данных. В [210)1 Кнут (Клпбт) предложил использовать дающее неплохие результаты значение А — (чГ5 — 1)/2 = 0.6180339887 ..

(П.2) В качестве примера предположим, что )с = 123456, р = 14, тп = 2"4 = 16384 и тл = 32. Принимая предложения Кнута, выберем А в виде дроби л/2зз, бли- хнмеехся русский перевал: д. Кнут. Искусство ороеранниооеанна и. Х Сортшннш и новел, у-е иэд.— Мл И.Д.

"Вильямс", 2000. 297 Глаеа П. Хеигиуаеаиие и «еиетаа«ици жайшей к значению (Л вЂ” 1)/2, так что А = 2654435769/2зз. Тогда Й в = 327706022297664 = (76300 2зз) + 17612864, и, таким образом, г| = 76300 и гс = 17612864. Старшие 14 бит числа го дают хеш-значение 6(к) = 67. * 11.3.3 Универсальное хеширование Если недоброжелатель будет умышленно выбирать ключи для хеширования с использованием конкретной хеш-функции, то он сможет подобрать и значений, которые будут хешироваться в одну и ту же ячейку таблицы, приводя к среднему времени выборки 9(п). Таким образом, любая фиксированная хеш-функция становится уязвимой, и единственный эффективный выход из ситуации — случайный выбор хеш-функции, не зависящий от того, с какими именно ключами ей предстоит работать.

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

Возвращаясь к примеру с таблицей символов иэмпилятора, мы обнаружим, что никакой выбор программистом имен идентификаторов не может привести к постоянно низкой производительности хеширования. Такое снижение возможно только тогда, когда компилятором выбрана случайная хеш-функция, которая приводит к плохому хешированию конкретных входных данных; однако вероятность такой ситуации очень мала и одинакова для любого множества идентификаторов одного и то же размера. Пусть 74 — конечное множество хеш-функций, которые отображают данную совокупность ключей г7 в диапазон (О, 1,..., т — Ц.

Такое множество называется универсальным, если для каждой пары различных ключей Й, 1 6 ГГ количество хеш-функций 6 Е 7/, для которых Ь(lс) = Ь(1), не превышает ~74~ /т. Другими словами, при случайном выборе хеш-функции из 74 вероятность коллизии между различными ключами и и 1 не превышает вероятности совпадения двух случайным образом выбранных хеш-значений из множества (О, 1,..., т — 1), которая равна 1/т. Следующая теорема показывает, что универсальный класс хеш-функций обеспечивает хорошую среднюю производительность.

В приведенной теореме по как уже упоминалось, обозначает длину списка Т(г]. Теорема 11.3 Пусп, хеш-функция (г, случайным образом выбранная из универсального множества хеш-функций, применяется для хеширования п ключей в таблицу Т размером т с использованием для разрешения коллизий метода цепочек. Если ключ 79 отсУтствУет в таблице, то математическое ожидание Е ~пь<ь1) длины списка, в ко- Час!нь 111. ьннрунтуры данньи тарый хешируется ключ й, не превышает коэффициента заполнения гь = п/т. Если ключ 6 находится в таблице, то математическое ожидание Е [пь(ь)] длины списка, в котором находится ключ Й, не превышает 1 + !з.

У„=~ Х„, !еТ !фь Таким образом, мы имеем Е[У![ = Е Х„ = ~Е [Хм) (из линейности математического ожидания) !ЕТ !фь 1 <~— !ЕТ Оставшаяся часть доказательства зависит от того, находится ли ключ /с в табли- це Т. Если 6 К Т, то пь(ь) = У!, и [(1:1Е Ти1ф 6)[ = п. Таким образом, Е [пь(„)~ = Е [У!,[ < п/т = а. Если 6 Е Т, то, поскольку ключ 6 находится в списке Т[6(6)[ и количество Уь не включает ключ 6, мы имеем пь(ь) = Уь + 1 и [(1: 1 Е Т и 1 ф й) [ = и — 1. Таким образом, Е [пь(ь)1 = Е [Уь[+1 < (п — 1)/т+1 = 1+о — 1/т < 1+!з. ° Следствие из данной теоремы гласит, что универсальное хеширование обеспечивает желаемый выигрыш: теперь невозможна выбрать последовательность операций, которые приведут к наихудшему времени работы. Путем рандомизации выбора хеш-функции в процессе работы программы гарантируется хорошее среднее время работы алгоритма для любых входных данных.

Доказавзвльслгво. Заметим, что математическое ожидание вычисляется на множестве выборов функций и не зависит от каких бы то ни было предположений о распределении ключей. Определим для каждой пары различных ключей 6 и 1 индикаторную случайную величину Хы = 1(6(6) = 6(1)). Поскольку по определению универсального множества пара ключей вызывает коллизию с вероятностью не выше 1/т, получаем, что Рг(6(6) = 6(1)) < 1/т. Следовательно, в соответствии с леммой 5.1 мы имеем Е [Хы[ < 1/гп.

Далее для каждого ключа 6 определим случайную величину Уы которая равна количеству ключей, отличающихся от 6 и хешируемых в ту же ячейку, что и ключ 6, так что «99 Глава ЕЕ Хеширование и «еш-тайлииы Следсятвае 11.4 Использование универсального хеширования и разрешения коллизий методом цепочек в изначально пустой хеш-таблице с тп ячейками дает математическое ожидание времени выполнения любой последовательности из п вызовов 1НЗЕКТ, 8ехксн и Пееете, в которой содержится О(т) операций 1мзект, равное ез(п). Доказвятельсятво. Поскольку юличество вставок равно 0(тп), мы имеем и = 0(ти) и, соответственно, а = О(1). Время работы операций 1нзект и Пеевте— величина постоянная, а в соответствии с теоремой 11.3 математичесюе ожидание времени выполнения каждой операции поиска равно 0(1).

Характеристики

Список файлов книги