Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 60
Текст из файла (страница 60)
(Здесь использовано неравенство (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,..., т — Ц. Равномерное хеширование представляет собой обобщение определенного ранее простого равномерного хеширования, заключающееся в том, что теперь хеш-функция дает не одно значение, а целую последовательность исследований.
Реализация истинно равномерного хеширования достаточно трудна, однако на практике используются подходящие аппроксимации (такие, например, как определенное ниже двойное хеширование). Для вычисления последовательности исследований для открытой адресации обычно используются три метода: линейное исследование, квадратичное исследование и двойное хеширование.
Эти методы гарантируют, что для каждого ключа Ь (Ь ()с,О), Ь (й, 1),..., Ь (Ь, т — 1)) является перестановкой (О, 1,..., т — 1). Однако эти методы не удовлетворяют предположению о равномерном хешировании, так как ни один из них не в состоянии сгенерировать более тз различных последовательностей исследований (вместо т!, требующихся для равномерного хеширования). Наибольшее количество последовательностей исследований дает двойное хеширование и, как и следовало ожидать, дает наилучшие результаты.
Линейное исследование Пусть задана обычная хеш-функция Ь': У вЂ” (О, 1,..., т — 1), которую мы будем в дальнейшем именовать вспомогательной хеш-функцией (апх1!1агу Ьай бшсбоп). Метод линейного исследования для вычисления последовательности исследований использует хеш-функцию Ь(к,() = (Ь'(Ь) + !) шой т, где 1 принимает значения от О до т — 1 включительно. Для данного ключа к первой исследуемой ячейкой является Т [Ь' (к)], т.е.
ячейка, которую дает вспомогательная хеш-функцня. Далее мы исследуем ячейку Т «Ь' (!с) + 1] и далее последовательно все до ячейки Т [т — 1], после чего переходим в начало таблицы и последовательно исследуем ячейки Т [0], Т [1], и так до ячейки Т [Ь' (Ь) — 1]. Поскольку начальная исследуемая ячейка однозначно определяет всю последовательность исследований целиком, всего имеется т различных последовательностей. Линейное исследование легко реализуется, однако с ним связана проблема первичной кластеризации, связанной с созданием длинных последовательностей занятых ячеек, что, само собой разумеется, увеличивает среднее время поиска. Кластеры возникают в связи с тем, что вероятность заполнения пустой ячейки, которой предшествуют 1 заполненных ячеек, равна (1 + 1)/т.
Таким образом, длинные серии заполненных ячеек имеют тенденцию ко все большему удлинению, что приводит к увеличению среднего времени поиска. Глава 11. Хеш-таблицы 303 Квадратичное исследование Квадратичное исследование использует хеш-функцию вида Ь(К,1) = (Ь'(й) + сг1+ сг1 ) шос1 т, (11.5) где Ь' — вспомогательная хеш-функция, с1 и сг ф 0 — вспомогательные константы, а 1 принимает значения от 0 до т — 1 включительно. Начальная исследуемая ячейка — Т [Ь' ()с)]; остальные исследуемые позиции смещены относительно нее на величины, которые описываются квадратичной зависимостью от номера исследования С Этот метод работает существенно лучше линейного исследования, но для того, чтобы исследование охватывало все ячейки, необходим выбор специальных значений сы сг и т (в задаче 11-3 показан один из путей выбора этих параметров).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
