Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 63
Текст из файла (страница 63)
Таким образом, используя свойство линейности математического ожидания, получаем, что ожидаемое время, необходимое для выполнения всей последовательности из и операций, равно 0(п). Поскольку каждая операция занимает время Й(1), отсюда следует граница еь(п). Построение уныверсальнага класса хеш-функций Построить такое множество довольно просто, что следует из теории чисел.
Если вы с ней незнакомы, то можете сначала обратиться к главе 31. Начнем с выбора простого числа р, достаточно большого, чтобы все возможныс ключи находились в диапазоне от О до р — 1 включительно. Пусть е.р обозначает множество (О, 1,..., р — 1), а Жр — множество (1, 2,..., р — Ц. Поскольку р — простое число, мы можем решать уравнения по модулю р с помощью методов, описанных в главе 31. Из предположения о том, что пространство ключей больше, чем количество ячеек в хеш-таблице, следует, что р ) т. Теперь определим хеш-функцию Ь,ь для любых а е Жр и Ь б е.р, используя линейное преобразование с последующим приведением по модулю р, а затем по модулю тп: Ьаь()е) = ((ай + Ь) щи р) шод пь . (11.3) Например, при р = 17 и то = 6 мы имеем Ьз 4(8) = б. Семейство всех таких функций образует множество Нр — — ( Ь,ь: а Е .'Ер и Ь Е 'е'р ) (11.4) Каждая хеш-функция Ь ь отображает Тр в Ж .
Этот класс хеш-функций обладает тем свойством, что размер пт выходного диапазона произволен и не обязательно представляет собой простое число. Это свойство будет использовано нами в разделе 11.5. Поскольку число а можно выбрать р — 1 способом, а число Ь вЂ” р способами, всего во множестве 'Нр содержится р(р — 1) хеш-функций. Теорема 11.5 Класс Я хеш-функций, определяемых уравнениями (11.3) и (11.4), является универсальным.
Часть ЗП. Структуры данны» ЗОО Донсиательстесь Рассмотрим два различных ключа lс и 1 из Жр, так что Ь ф 1. Пусть для данной хеш-функции Ьаь т = (ай + Ь) шос( р, в = (а1+Ь) пюс( р. Заметим сначала, что т ф в. Почему? Обратите внимание, что т — в = а(Й вЂ” 1) (шос( р) . Отсюда следует, что т ф в, поскольку р — простое число, и как а, так и (Й вЂ” 1) ненулевые по модулю р, так что и их произведение должно быть ненулевым по модулю р согласно теореме 31.6.
Следовательно, вычисление любой хеш-функции Ь,ь Е 'Н отображает различные входные значения Ь и 1 на различные значения т и в по модулю р; так что коллизии "по модулю р" отсутствуют. Более того, каждый из р(р — 1) возможных выборов пар (а, Ь) с а ~ О дает различные пары (т, в) с т ?1 в, поскольку по заданным т и в можно найти а и Ь: а = ((г — в)((к — 1) ~ шосз р)) пюсз р, Ь = (т — аЬ) пюс1 р, где ((Ь вЂ” 1) ' пюс1 р) обозначает единственное мультипликативное обратное по модулю р значения Ь вЂ” 1. Поскольку имеется только р(р — 1) возможных пар (т, в), таких что т ~ в, то имеется взаимно однозначное соответствие между парами (а, Ь) с а ~ О н парами (т, в), в которых т ф ж Таким образом, для любой данной пары входных значений Ь и 1 при равномерном случайном выборе пары (а, Ь) из К„* ьс е,р, получаемая в результате пара (т, в) может быть с равной вероятностью любой из пар с отличающимися по модулю р значениями. Отсюда можно заключить, что вероятность того, что различные ключи Ь и 1 приводят к коллизии, равна вероятности того, что г »в а в (гаос( пз) при случайном выборе отличающихся по модулю р значений т и ж Для данного значения т имеется р — 1 возможных значений в.
При этом число значений в, таких, что в ф т и в = т (аспас( т), не превышает ~р/т1 — 1 < ((р+ т — 1)/гп) — 1 (согласно неравенству (3.6)) = (р — 1)/пз . Вероятность того, что в приводит к коллизии с г при приведении по модулю та„ не превышает ((р — 1)/т)/(р — 1) = 1/т.
Следовательно, для любой пары различных значений Ь,1 е ар Рг(Ьаь(Ь) = Ь,ь(1)) < 1/т, так что множество хеш-функций Я, является универсальным. Г«аеа ц. Хеширование и «еш-тайлицы 30! Упражнения 11.3.1 Предположим, что мы выполняем поиск в связанном списке длиной п, в котором каждый элемент содержит ключ )с вместе с хеш-значением Ь(Ь). Каждый ключ представляет собой длинную символьную строку. Как можно использовать наличие хеш-значения при поиске элемента с заданным ключом? п.з.г Предположим, что строка из т символов хешируется в т ячеек путем ее интерпретации как числа, записанного в 128-ричной системе счисления, и использования метода деления.
Число т легко представимо в виде 32-битового машинного слова, но представление строки из г символов как целого 128-ричного числа требует много слов. Каким образом можно применить метод деления для вычисления хеш-зпачения символьной строки с использованием не более чем фиксированного количества дополнительных машинных слов, помимо самбй строки? 11.3.3 Рассмотрим версию метода деления, в которой Ь(?е) = lс шод т, где т = 2г — 1, а Ь вЂ” символьная строка, интерпретируемая как целое число в системе счисления с основанием 2г. Покажите, что если строка х может быть получена из строки и перестановкой символов, то хеш-значения этих строк одинаковьь Приведите пример приложения, в котором зто свойство хеш-функции может оказаться крайне нежелательным.
11.3.4 Рассмотрим хеш-таблицу размером т = 1000 и соответствующую хеш-функцию Ь(Ь) = ~еп (ЙА шод 1)), где А = (з/5 — 1)/2. Вычислите номера ячеек, в которые хешируются ключи 61, 62, 63, 64 и 65. 11.3.5 * Определим семейство хеш-функций Я, отображающих конечное множество 11 иа конечное множество В, как е-универсальное, если для всех пар различных элементов Ь и 1 из 11 Рг(Ь(/с) = Ь(1)) ( е, где вероятность вычисляется для случайного выбора хеш-функции Ь из множества 'Н. Покажите, что е-универсальное семейство хеш-функций должно обладать тем свойством, что 1 1 е) — — — .
)В) 1Ц ' 11З.б * Пусть 11 — множество и-кортежей значений, выбираемых из Кр, и пусть В = Ер, где р — простое число. Определим хеш-функцию Ьь . 11 -+ В для Ь е Кр Часть Лх Структуры даниьп зог и входного кортежа (ао, аы,,,, а„~) из У следуюшим образом: /и — з Ьь((ао, ам..., а„з)) = ~~ ауУ шоб р, з=о и пусть Н = (Ьь . 6 е Жр). Докажите, что М является ((и — 1)/р)-универсальным множеством в соответствии с определением, данным в упр. 11.3.5. (Указание: см. упр. 31,4.4.) 11.4. Открытая адресация При использовании метода ошкрмтой адресации все элементы хранятся непосредственно в хеш-таблице, т,е. каждая запись таблицы содержит либо элемент динамического множества, либо значение иь.
При поиске элемента мы систематически проверяем ячейки таблицы до тех пор, пока не найдем искомый элемент или пока не убедимся в его отсутствии в таблице. Здесь, в отличие от метода цепочек, нет ни списков, ни элементов, хранящихся вне таблицы. Таким образом, в методе открытой адресации хеш-таблица может оказаться заполненной и сделать невозможной вставку новых элементов; одним из следствий этого является то, что коэффициент заполнения а не может превышать 1. Конечно, при хешировании с разрешением коллизий методом цепочек можно использовать свободные места в хеш-таблице для хранения связанных списков (см. упр. 11.2.4), но преимущество открытой адресации заключается в том, что она позволяет полностью отказаться от указателей.
Вместо того чтобы следовать по указателям, мы вычисляем последовательность проверяемых ячеек. Дополнительная память, освобождающаяся в результате отказа от указателей, позволяет использовать хеш-таблицы большего размера при том же общем количестве памяти, потенциально приводя к меньшему количеству коллизий и более быстрой выборке. Для выполнения вставки при открытой адресации мы последовательно проверяем, или исследуем (ргобе), ячейки хеш-таблицы до тех пор,пока не находим пустую ячейку, в которую помещаем вставляемый ключ.
Вместо фиксированного порядка исследования ячеек О, 1,..., т — 1 (для чего требуется 9(п) времени), последовательность исследуемых ячеек зависит ое вставляемого в таблицу ключа. Для определения исследуемых ячеек мы расширим хеш-функцию, включив в нее в качестве второго аргумента номер исследования (начинающийся с 0). В результате хеш-функция становится следуюшей: ЗйЗ Рвала ЕА Хеширование и «еш-таоличы В методе открытой адресации требуется, чтобы дяя каждого ключа )е лоследвва- гоельноеть исследований (Ь(1е, О), А()е, 1),..., А()е, т — 1)) представляла собой перестановку множества (О, 1,..., ел — 1), чтобы в конечном счете могли быть просмотрены все ячейки хеш-таблицы.
В приведенном далее псевдокоде предполагается, что элементы в таблице Т представляют собой ключи без сопутствующей информации; ключ й тождествен элементу, содержащему ключ )с. Каждая ячейка содержит либо ключ, либо значение яп.. Процедура НАзн-11чзект получает в качестве входных данных хеш-таблицу Т и ключ к. Она либо возвращает номер ячейки, в которую записывается ключ Зе, либо сообщает об ошибке, связанной с заполненностью таблицы. НАзн-!хзект(Т, й) 1 1=0 2 гереаг 3 З = А(к,1) 4 МТЦ == н!е 5 ТЦ=Зе 6 гегпгп З 7 е!аев' =1+1 8 пвгй 1 == еп 9 еггог "переполнение хеш-таблицы" Алгоритм поиска ключа /с исследует ту же последовательность ячеек, что и алгоритм вставки ключа lс.
Таким образом, если при поиске встречается пустая ячейка, поиск завершается неудачей, поскольку ключ )с должен был бы быть вставлен в эту ячейку в последовательности исследований, и никак не позже иее. (Предполагается, что удалений из хеш-таблицы не было.) Процедура НАзнЯелксн получает в качестве входных параметров хеш-таблицу Т н ключ )е и возвращает номер ячейки, которая содержит ключ /с (или значение нп., если ключ в хеш-таблице не обнаружен). НАБн-ЗеАксн(Т, Й) 1 1=0 2 гереаг 3 3 = Ь()е,4) 4 ГТ[Я == )е 5 гетпгп З 6 1=1+1 7 алгй Т(З] == и11. или 1 == пз 8 гепзгп мп.
Процедура удаления из хеш-таблицы с открытой адресацией достаточно сложна. При удалении ключа из ячейки 1 мы не можем просто пометить ее пустым 304 Часть Ш. Струнтуры данник значением мш. Поступив так, мы можем сделать невозможным выборку ключа (с, в процессе вставки которого исследовалась и оказалась занятой ячейка 1. Одно из решений состоит в том, чтобы помечать такие ячейки специальным значением ОЕЕЕтЕП вместо М1Е. При этом мы должны слегка изменить процедуру НАЗН1мзект, чтобы она рассматривала такую ячейку как пустую и могла вставить в нее новый ключ. В процедуре НАзн-БеАксн никакие изменения не требуются, поскольку мы просто пропускаем такие ячейки при поиске и исследуем следуклцие ячейки в последовательности. Однако при использовании специального значения пееетеп время поиска перестает зависеть от коэффициента заполнения о, и по этой причине, как правило, при необходимости удалений из хеш-таблицы в качестве метода разрешения коллизий выбирается метод цепочек.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
