Алгоритмы - построение и анализ (1021735), страница 58
Текст из файла (страница 58)
Глава 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 из Ер, т.е.
й ф 1. Пусть для данной хеш-функции Ь ь 298 Часть 1П. Структуры данньж а ф О, приводят к различным парам (т,з), в которых г ~ ж Чтобы убедиться в этом, достаточно рассмотреть возможность однозначного определения а и Ь по данным г и ьз а = ((г — а) ((к — 1) 1 шой р) ) шой р, Ь = (г — ай) пюс1 р, где ((Ь вЂ” 1) з пюс1 р) обозначает единственное мультипликативное обратное по модулю р значения Ь вЂ” 1. Поскольку имеется только р(р — 1) возможных пар (г, з), таких что г ~ а, то имеется взаимнооднозначное соответствие между парами (а, Ь), где а ф О, и парами (г, з), в которых г ~ ж Таким образом, для любой данной пары входных значений й и 1 при равномерном случайном выборе пары (а, Ь) из 2„* х 2р, получаемая в результате пара (г, а) может быть с равной вероятностью любой из пар с отличающимися значениями по модулю р. Отсюда можно заключить, что вероятность того, что различные ключи Й и 1 приводят к коллизии, равна вероятности того, что т = з (шод пз) при произвольном выборе отличающихся по модулю р значений т и з.
Для данного значения т имеется р — 1 возможное значение в. При этом число значений а, таких что а ф г и з = г (шест р), не превышает (р/гп1 — 1 < ((р+ т — 1)/т) — 1 = (р — 1)/т. (Здесь использовано неравенство (3.6).) Вероятность того, что з приводит к кол- лизии с г при приведении по модулю гп, не превышает ((р — 1)/ )(р — 1) =1/(р — 1) =1/ Следовательно, для любой пары различных значений Ь,1 е Ер Рг (Ьа,6 Ж) = Ьа,ь (1)) ~ ~1/пз~ так что множество хеш-функций Н„является универсальным. Упражнения 11.3-1. Предположим, что мы выполняем поиск в связанном списке длиной п, в котором каждый элемент содержит ключ Й вместе с хеш-значением 6 (1с).
Каждый ключ представляет собой длинную символьную строку. Как можно использовать наличие хеш-значения при поиске элемента с заданным ключом? Глава 11. Хеш-таблицы 299 11.3-4. Рассмотрим хеш-таблицу размером тп = 1000 и соответствующую хешфункцию Ь (Ь) = 1тп (ЬА шот1 1)1 для А = (д/5 — 1)/2. Вычислите номера ячеек, в которые хешируются ключи 61, 62, 63, 64 и 65. * 11.3-5. Рг(Ь(Ь) = Ь(1)1 < е, 1 1 е ~) — — —. (В) )Ц * 11.3-6. Ьь((оо,ад,...,а д)) = ~д азЬ', 1 1.3-2.
1 1.3-3. Предположим, что строка из г символов хешируется в т ячеек путем ее интерпретации как числа, записанного в 128-рнчной системе счисления, и использования метода деления. Число т легко представимо в виде 32-битового машинного слова, но представление строки как целого числа требует много слов. Каким образом можно применить метод деления для вычисления хеш-значения символьной строки с использованием фиксированного количества дополнительных машинных слов? Рассмотрим версию метода деления, в которой Ь(к) = Ь шоб тп, где т = 2л — 1, а Ь вЂ” символьная строка, интерпретируемая как целое число в системе счисления с основанием 2".
Покажите, что если строка х может быть получена из строки у перестановкой символов, то хешзначения этих строк одинаковы. Приведите пример приложения, где это свойство хеш-функции может оказаться крайне нежелательным. Определим семейство хеш-функций Н, отображающих конечное множе- ство У на конечное множество В как е-универсальное, если для всех пар различных элементов й и 1 из У где вероятность вычисляется для случайного выбора хеш-функции Ь из множества Н. Покажите, е-универсальное семейство хеш-функций долж- но обладать тем свойством, что Пусть У вЂ” множество наборов из и чисел, выбирающихся из Ер, и пусть В = Ер, где р — простое число.
Определим хеш-функцию Ьь . ст — В для 5 Е Ер и входного набора (ао, ад,..., а„д) Е У следующим образом: и пусть Н = (Ль: Ь Е Ерг. Докажите, что Н является ((тд — 1)/р)-универ- сальным множеством в соответствии с определением, данным в упраж- нении 11.3-5. (Указание: см. упражнение 31.4-4.) Часть 01. Структуры данных 300 11.4 Открытая адресация При использовании метода открьииой адресации все элементы хранятся непосредственно в хеш-таблице, т.е. каждая запись таблицы содержит либо элемент динамического множества, либо значение ып..
При поиске элемента мы систематически проверяем ячейки таблицы до тех пор, пока не найдем искомый элемент или пока не убедимся в его отсутствии в таблице. Здесь, в отличие от метода цепочек, нет ни списков, ни элементов, хранящихся вне таблицы. Таким образом, в методе открытой адресации хеш-таблица может оказаться заполненной, делая невозможной вставку новых элементов; коэффициент заполнения о не может превышать 1. Конечно, при хешировании с разрешением коллизий методом цепочек можно использовать свободные места в хеш-таблице для хранения связанных списков (см.
упражнение 11.2-4), но преимущество открытой адресации заключается в том, что она позволяет полностью отказаться от указателей. Вместо того чтобы следовать по указателям, мы вычисляем последовательность проверяемых ячеек. Дополнительная память, освобождающаяся в результате отказа от указателей, позволяет использовать хеш-таблицы большего размера при том же общем количестве памяти, потенциально приводя к меньшему количеству коллизий и более быстрой выборке. Для выполнения вставки при открытой адресации мы последовательно проверяем, или исследуем (ргоЬе), ячейки хеш-таблицы до тех пор, пока не находим пустую ячейку, в которую помещаем вставляемый ключ.
Вместо фиксированного порядка исследования ячеек О, 1,..., пт — 1 (для чего требуется 9 (и) времени), последовательность исследуемых ячеек зависит от вставляемого в таблицу ключа. Для определения исследуемых ячеек мы расширим хеш-функцию, включив в нее в качестве второго аргумента номер исследования (начинающийся с 0).
В результате хеш-функция становится следующей: й: Ух (0,1,...,т — Ц- (0,1,...,т — Ц. В методе открытой адресации требуется, чтобы для каждого ключа к иоследова- тельность исследований (6 (lс, О), Ь ()с, 1),..., 6 (к, пт — 1) ) представляла собой перестановку множества (О, 1,..., тп — 1), чтобы в конечном счете могли быть просмотрены все ячейки хеш-таблицы.
В приведенном далее псевдокоде предполагается, что элементы в таблице Т представляют собой ключи без сопутствующей информации; ключ к тождественен элементу, содержащему ключ 1с. Каждая ячейка содержит либо ключ, либо значение яь (если она не заполнена): Глава 11. Хеш-таблицы 301 Нлзн 1нзпкт(Т, й) 1 㻠— О 2 гереаг 7' — Ь(к,г) 3 11 Т(7] = нн.
4 тпеп Т(7'] — к 5 геФнгп 2' б е)зе 1 -1+1 7 ппт11 г = т 8 еггог "Хеш-таблица переполнена" Алгоритм поиска ключа Й исследует ту же последовательность ячеек, что и алгоритм вставки ключа й. Таким образом, если при поиске встречается пустая ячейка, поиск завершается неуспешно, поскольку ключ к должен был бы быть вставлен в эту ячейку в последовательности исследований, и никак не позже иее.
(Мы предполагаем, что удалений из хеш-таблицы не было.) Процедура Нлзн Бплпсн получает в качестве входных параметров хеш-таблицу Т и ключ )с и возвращает номер ячейки, которая содержит ключ 1с (или значение нп., если ключ в хештаблице не обнаружен): Нлзн Яплксн(Т, к) 1 1 — О 2 гереа$7' — 6()с, 1) 3 11Т[Я = й 4 гпеп гетнгп 2' 5 1 — 1+1 6 ппЯ Т(7] = нш нли1= т 7 гегцгп нп.
Процедура удаления из хеш-таблицы с открытой адресацией достаточно сложна. При удалении ключа из ячейки 1 мы не можем просто пометить ее значением нп.. Поступив так, мы можем сделать невозможным выборку ключа й, в процессе вставки которого исследовалась и оказалась занятой ячейка 1. Одно из решений состоит в том, чтобы помечать такие ячейки специальным значением ппьптнз вместо нп..
При этом мы должны слегка изменить процедуру Нлзн 1нзпкт, с тем чтобы она рассматривала такую ячейку как пустую и могла вставить в нее новый ключ. В процедуре Нлзн Бплксн никакие изменения не требуются, поскольку мы просто пропускаем такие ячейки при поиске и исследуем следующие ячейки в последовательности. Однако при использовании специального значения пш.птю время поиска перестает зависеть от коэффициента заполнения а, и по этой причине, как правило, при необходимости удалений из хеш-таблицы в качестве метода разрешения коллизий выбирается метод цепочек.
Часть 111. Структуры данных 302 В нашем дальнейшем анализе мы будем исходить из предположения равномерного хеширования, т.е. мы предполагаем, что для каждого ключа в качестве последовательности исследований равновероятны все т! перестановок множества (О, 1,..., т — Ц. Равномерное хеширование представляет собой обобщение определенного ранее простого равномерного хеширования, заключающееся в том, что теперь хеш-функция дает не одно значение, а целую последовательность исследований. Реализация истинно равномерного хеширования достаточно трудна, однако на практике используются подходящие аппроксимации (такие, например, как определенное ниже двойное хеширование).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
