Алгоритмы - построение и анализ (1021735), страница 57
Текст из файла (страница 57)
Если же ключи не являются целыми неотрицательными числами, то можно найти способ их интерпретации как таковых. Например, строка символов может рассматриваться как целое число, записанное в соответствующей системе счисления. Так, идентификатор р~ можно рассматривать как пару десятичных чисел (112, 116), поскольку в АБСП-наборе символов р = 112 и г. = 116. Рассматривая р~ как число в системе счисления с основанием 128, мы находим, что оно соответствует значению 112 128 + 116 = 14452. В конкретных приложениях обычно не представляет особого труда разработать метод для представления ключей в виде (возможно, больших) целых чисел.
Далее при изложении материала мы будем считать, что все ключи представляют целые неотрицательные числа. 11.3.1 Метод деления Построение хеш-функции меиходам деления состоит в отображении ключа к в одну из ячеек путем получения остатка от деления /с на тп, т.е. хеш-функция имеет вид Й (Й) = Й пюс1 т. Например, если хеш-таблица имеет размер т = 12, а значение ключа й = 100, то 6(й) = 4. Поскольку для вычисления хеш-функции требуется только одна операция деления, хеширование методом деления считается достаточно быстрым. При использовании данного метода мы обычно стараемся избегать некоторых значений т.
Например, гп не должно быть степенью 2, поскольку если т = 2", то й(1с) представляет собой просто р младших битов числа к. Если только заранее Глава 11. Хеш-таблицы 293 не известно, что все наборы младших р битов ключей равновероятны, лучше строить хеш-функцию таким образом, чтобы ее результат зависел от всех битов ключа. В упражнении 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), отсюда следует граница О (и).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
