Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 59
Текст из файла (страница 59)
В упражнении 11.3-3 требуется показать неудачность выбора т = 2" — 1, когда ключи представляют собой строки символов, интерпретируемые как числа в системе счисления с основанием 2Я, поскольку перестановка символов ключа не приводит к изменению его хеш-значения. Зачастую хорошие результаты можно получить, выбирая в качестве значения т простое число, достаточно далекое от степени двойки.
Предположим, например, что мы хотим создать хеш-таблицу с разрешением коллизий методом цепочек для хранения и = 2000 символьных строк, размер символов в которых равен 8 битам. Нас устраивает проверка в среднем трех элементов при неудачном поиске, так что мы выбираем размер таблицы равным т = 701. Число 701 выбрано как простое число, близкое к величине 2000/3 и не являющееся степенью 2. Рассматривая каждый ключ Й как целое число, мы получаем искомую хеш-функцию: 6 ()с) = )с шос) 701. 11.3.2 Метод умножения Построение хеш-функции мелсодом умножения выполняется в два этапа. Сначала мы умножаем ключ й на константу 0 < А < 1 и получаем дробную часть полученного произведения. Затем мы умножаем полученное значение на пз и применяем к нему функцию "пол" т.е.
6(/с) = 1тп()сА шос) 1Ц, А = ~Л вЂ” 1) /2 = О.б180339887 (11.2) где выражение ")сА пюс1 1" означает получение дробной части произведения )сА, т.е. величину 1сА — 1)сА). Достоинство метода умножения заключается в том, что значение т перестает быть критичным. Обычно величина т из соображений удобства реализации функции выбирается равной степени 2.
Пусть у нас имеется компьютер с размером слова ю битов и )с помещается в одно слово. Ограничим возможные значения константы А видом а/2, где а — целое число из диапазона 0 < з < 2 . Тогда мы сначала умножаем )с на и-битовое целое число в = А 2 . Результат представляет собой 2ю-битовое число т~2'"+ го, где гз — старшее слово произведения, а гав младшее. Старшие р битов числа го представляют собой искомое р-битовое хешзначение (рис. 11А). Хотя описанный метод работает с любыми значениями константы А, некоторые значения дают лучшие результаты по сравнению с другими.
Оптимальный выбор зависит от характеристик хешируемых данных. В 1185) Кнут предложил использовать дающее неплохие результаты значение 294 Часть ПЕ Структуры данных ь6л яв и Бымжыььябшов Ьф~ ! Рис. 11А. Хеширование методом умножения Возьмем в качестве примера й = 123456, р = 14, т = 2ы = 16384 и тл = 32. Принимая предложение Кнута, выбираем значение А в виде а/2, ближайшее к величине (т/5 — 1)/2, так что А = 2654435769/2зз. Тотда 1т а = 327706022297664 = (76300. 2зз) + 17612864, и, соответственно, гт = 76 300 и гс = 17 612 864. Старшие 14 битов числа го дают нам хеш-значение 6 (й) = 67. * 11.3.3 Универсальное хеширование Если недоброжелатель будет умышленно выбирать ключи для хеширования при помощи конкретной хеш-функции, то он сможет подобрать п значений, которые будут хешироваться в одну и ту же ячейку таблицы, приводя к среднему времени выборки О (и).
Таким образом, любая фиксированная хеш-функция становится уязвимой, и единственный эффективный выход из ситуации — случайный выбор хеш-функции, яе зависяи~ий от того, с какими именно ключами ей предстоит работать. Такой подход, который называется универсальным хешированием, гарантирует хорошую производительность в среднем, независимо от того, какие данные будут выбраны злоумышленником. Главная идея универсального хеширования состоит в случайном выборе хешфункции из некоторого тщательно отобранного класса функций в начале работы программы. Как и в случае быстрой сортировки, рандомизация гарантирует, что одни и те же входные данные не могут постоянно давать наихудшее поведение алгоритма. В силу рандомизации алгоритм будет работать всякий раз поразному, даже для одних и тех же входных данных, что гарантирует высокую среднюю производительность для любых входных данных.
Возвращаясь к примеру с таблицей символов компилятора, мы обнаружим, что никакой выбор программистом имен идентификаторов не может привести к постоянному снижению производительности хеширования. Такое снижение возможно только тогда, когда компилятором выбрана случайная хеш-функция, которая приводит к плохому Глава 11. Хеш-таблицы 295 хешированию конкретных входных данных; однако вероятность такой ситуации очень мала и одинакова для любого множества идентификаторов одного и то же размера. Пусть Н вЂ” конечное множество хеш-функций, которые отображают пространство ключей У в диапазон (О, 1, 2,..., т — 1).
Такое множество называется универсальным, если для каждой пары различных ключей Й,1 е У количество хешфункций Ь Е Н, для которых Ь (1с) = Ь (1), не превышает [Н[/т. Другими словами, при случайном выборе хеш-функции из Н вероятность коллизии между различными ключами Ь и 1 не превышает вероятности совпадения двух случайным образом выбранных хеш-значений из множества (О, 1, 2,..., т — Ц, которая равна 1/т.
Следующая теорема показывает, что универсальные хеш-функции обеспечивают хорошую среднюю производительность. В приведенной теореме и,, как уже упоминалось, обозначает длину списка Т [1). Теорема 11.3. Пусть хеш-функция Ь, выбранная из универсального множества хеш-функций, используется для хеширования гс ключей в таблицу Т размера т, с использованием для разрешения коллизий метода цепочек. Если ключ Ь отсутствует в таблице, то математическое ожидание Е [пь(ь1 ~ длины списка, в который хешируется ключ Ь, не превышает сз.
Если ключ Ь находится в таблице, то математическое ожидание Е [пь1ь1~ длины списка, в котором находится ключ 1с, не превышает 1+ а. Доказаюиельсгнво. Заметим, что математическое ожидание вычисляется на множестве выборов функций и не зависит от каких бы то ни было предположений о распределении ключей. Определим для каждой пары различных ключей Ь н 1 индикаторную случайную величину Хьс = 1 (Ь (1с) = Ь (1) ). Поскольку по определению пара ключей вызывает коллизию с вероятностью не выше 1/т, получаем, что Рг (Ь(Ь) = Ь(1)) ( 1/т, так что, в соответствии с леммой 5.1, Е [Хы] < 1/т.
Далее для каждого ключа 1с определим случайную величину Уы которая равна количеству ключей, отличающихся от й и хешируемых в ту же ячейку, что и ключ 1с: 1я =,'~'Хы. сет с~я Часть 1П. Структуры данных 296 Соответственно, получаем: Е[У„] =Е ~~ Х 1ет 1фь (в силу линейности математического ожидания) = ~~> Е [Хм] < гет 1~а 1 < ~~~ !ет 1~а Оставшаяся часть доказательства зависит от того, находится ли ключ 1с в таб- лице Т. ° Если 1с Т.
Т, то пь1ь1 = Уь и [(1:1Е Т и 1ф 1с)[ = и. Соответственно, Е [пь1ь1] = Е [Уь] < п/т = гх. ° Если 1с е Т, то поскольку 1с находится в списке Т [и (1с)] и значение Уь не включает ключ 1с, мы имеем пь1ь1 = Уь + 1 и [(1: 1 Е Т и 1 ф к) [ = п — 1. Таким образом, Е [пь1ь11 = Е [Уь] + 1 < (и — 1)/т + 1 = 1 + сх — 1/т < < 1+а. Следствие из данной теоремы гласит, что универсальное хеширование обеспечивает желаемый выигрыш: теперь невозможно выбрать последовательность операций, которые приведуг к наихудшему времени работы.
Путем рандомизации выбора хеш-функции в процессе работы программы гарантируется хорошее среднее время работы алгоритма для любых входных данных. Следствие 11.4. Использование универсального хеширования и разрешения кол- лизий методом цепочек в хеш-таблице с т ячейками дает математическое ожи- дание времени выполнения любой последовательности из п вставок, поисков и удалений, в которой содержится О (т) вставок, равное О (и). Доказаюиельсхиоо. Поскольку количество вставок равно О (т), п = О (т) и, соответственно, а = О (1). Время работы операций вставки и удаления — величина постоянная, а в соответствии с теоремой 11.3 математическое ожидание времени выполнения каждой операции поиска равно О(1).
Таким образом, используя свойство линейности математического ожидания, получаем, что ожидаемое время, необходимое для выполнения всей последовательности операций, равно О (и). Поскольку каждая операция занимает время П (1), отсюда следует граница О (и). Глава 11. Хеш-таблицы 297 Построение универсального множества хеш-функций Построить такое множество довольно просто, что следует из теории чисел.
Если вы с ней незнакомы, то можете сначала обратиться к главе 31. Начнем с выбора простого числа р, достаточно большого, чтобы все возможные ключи находились в диапазоне от О до р — 1 включительно. Пусть Ер обозначает множество (0,1,...,р — Ц, а Ер — множество (1,2,...,р — Ц. Поскольку р — простое число, мы можем решать уравнения по модулю р при помощи методов, описанных в главе 31. Из предположения о том, что пространство ключей больше, чем количество ячеек в хеш-таблице, следует, что р ) т. Теперь определим хеш-функцию 6 ь для любых а Е Ер и Ь Е Ер следующим образом: Ьвь(1с) = ((ай+ Ь) шоб р) шос1 т.
(11.3) Например, при р = 17 и т = б Ьз4 (8) = б. Семейство всех таких функций образует множество Нжт = (Ьа,ь: ае Ер иЬеЕл). (1 1.4) Каждая хеш-функция 6 ь отображает Ер на Е . Этот класс хеш-функций обладает тем свойством, что размер т выходного диапазона произволен и не обязательно представляет собой простое число. Это свойство будет использовано нами в разделе 11.5. Поскольку число а можно выбрать р — 1 способом, и р способами— число 6, всего во множестве Нр содержится р(р — 1) хеш-функций. Теорема 11.5. Множество хеш-функций Нр, определяемое уравнениями (11.3) и (11.4), является универсальным.
г = (ай + 6) щось р, в = (а1 + Ь) шод р. Заметим, что г ф. в. Почему? Рассмотрим разность г — в = — а(к — 1) (п1обр) . Поскольку р — простое число, причем как а, так и (й — 1) не равны нулю по модулю р, то отсюда следует что г ф в, так что и их произведение также должно быть отлично от нуля по модулю р согласно теореме 31.6. Следовательно, вычисление любой хеш-функции Ь ь е Нр ы для различных ключей 1с и 1 приводит к различным хеш-значениям г и в по модулю р. Таким образом, коллизии "по модулю р" отсутствуют. Более того, каждая из р (р — 1) возможных пар (а, Ь), в которых Доказаигвльство.
Рассмотрим два различных ключа й и 1 из Ер, т.е. й ф 1. Пусть для данной хеш-функции Ь ь 298 Часть 1П. Структуры данньж а ф О, приводят к различным парам (т,з), в которых г ~ ж Чтобы убедиться в этом, достаточно рассмотреть возможность однозначного определения а и Ь по данным г и ьз а = ((г — а) ((к — 1) 1 шой р) ) шой р, Ь = (г — ай) пюс1 р, где ((Ь вЂ” 1) з пюс1 р) обозначает единственное мультипликативное обратное по модулю р значения Ь вЂ” 1.
Поскольку имеется только р(р — 1) возможных пар (г, з), таких что г ~ а, то имеется взаимнооднозначное соответствие между парами (а, Ь), где а ф О, и парами (г, з), в которых г ~ ж Таким образом, для любой данной пары входных значений й и 1 при равномерном случайном выборе пары (а, Ь) из 2„* х 2р, получаемая в результате пара (г, а) может быть с равной вероятностью любой из пар с отличающимися значениями по модулю р. Отсюда можно заключить, что вероятность того, что различные ключи Й и 1 приводят к коллизии, равна вероятности того, что т = з (шод пз) при произвольном выборе отличающихся по модулю р значений т и з. Для данного значения т имеется р — 1 возможное значение в. При этом число значений а, таких что а ф г и з = г (шест р), не превышает (р/гп1 — 1 < ((р+ т — 1)/т) — 1 = (р — 1)/т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
