Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 60
Текст из файла (страница 60)
Множество Х = (2, 3, 5,8) реальных ключей определяет ячейки в таблице, которые содержат указатели на злементы. Прочие (закрашенные темным цветом) ячейки соаержат значение нп.. 287 Глава !1. Хешираваиие и хеш-таалияи В некоторых приложениях элементы динамического множества могут храниться непосредственно в таблице с прямой адресацией. Иначе говоря, вместо хранения ключей и сопутствующих данных элементов в объектах, внешних по отношению к таблице с прямой адресацией, а в таблице — указателей на эти объекты, эти объекты можно хранить непосредственно в ячейках таблицы (что тем самым приводит к экономии используемой памяти).
При этом для указания пустой ячейки можно воспользоваться специальным значением ключа. Кроме того, зачастую хранение ключа не является необходимым условием, поскольку если мы знаем индекс объекта в таблице, значит, мы знаем и его ключ. Однако если ключ не хранится в ячейке таблицы, то нам нужен какой-то иной механизм для того, чтобы помечать пустые ячейки. Упражнении 11.1.1 Предположим, что динамическое множество Я представлено таблицей с прямой адресацией Т длиной т. Опишите процедуру, которая находит максимальный элемент Я.
Чему равно время работы этой процедуры в наихудшем случае? Блеоаый веклеор представляет собой массив битов (нулей и единиц). Битовый вектор длиной гп занимает существенно меньше места, чем массив из гп указателей. Каким образом можно использовать битовый вектор для представления динамического множества различных элементов без сопутствующих данных? Словарные операции должны выполняться за время О(1).
11.1.3 Предложите способ реализации таблицы с прямой адресацией, в которой ключи храняшихся элементов могут совпадать, а сами элементы — иметь сопутствующие данные. Все словарные операции (1неепт, Оееете и ЯеАксн) должны выполняться за время 0(1). (Не забудьте, что аргументом процедуры ОЕЕЕТЕ являстся указатель на удаляемый обьект, а не ключ.) 11.1.4 * Предположим, что мы хотим реализовать словарь с использованием прямой адресации очень большого массива.
Первоначально в массиве может содержаться "мусор", но инициализация всего массива нерациональна в силу его размера. Разработайте схему реализации словаря с прямой адресацией при описанных условиях. Каждый хранимый объект должен использовать О(1) памяти; операции Белксн, !нзект и Оееете должны выполняться за время О(1); инициализация структуры данных также должна выполняться за время О(1). (Указаниев для определения, является лн данная запись в большом массиве корректной, воспользуйтесь дополнительным массивом, работающим в качестве стека, размер которого равен количеству ключей, сохраненных в словаре.) Часть Ш.
Структуры данных 2ВВ 11.2. Хеш-таблицы Недостаток прямой адресации очевиден: если совокупность юпочей У велика„ хранение таблицы Т размером ~ Ц непрактично, а то и вовсе иевозможио — в зависимости от количества доступной памяти и размера совокупности ключей. Кроме того, множество К реально сохраненных ключей может быть малб по сравнению с совокупностью ключей У, а в этом случае память, выделенная для таблицы Т, в основном расходуется напрасно. Когда множество К хранящихся в словаре ключей гораздо меньше совокупности возможных ключей У, для хеш-таблицы требуется существенно меньше места, чем для таблицы с прямой адресацией.
Точнее говоря, требования к памяти могут быть снижены до 9()К~), при этом время поиска элемента в хештаблице остается равным О(1). Нужно только заметить, что это граница времени поиска в среднем случае, в то время как в случае таблицы с прямой адресацией эта граница справедлива для наихудшего случая. В случае прямой адресации элемент с ключом Й храиится в ячейке /с. При хешировании этот злемеит хранится в ячейке Ь(к), т.е. мы используем хеш-функт(ию Ь для вычисления ячейки для данного ключа Ь.
Функция Ь отображает совокупиость ключей У иа ячейки хеш-тайшцы Т'10 .. пт — Ц: Ь: Г -ь (0,1,...,т — Ц, где размер пт хеш-таблицы обычно гораздо меньше значения ~У~. Мы говорим, что элемент с ключом Й хешируешся в ячейку Ь(к); величина Ь()с) называется хеш-значением ключа Ь. На рис. 11.2 представлена основная идея хеширования. Цель хеш-фуикции состоит в том, чтобы уменьшить рабочий диапазон индексов массива, и вместо размера )Ц значений мы можем обойтись массивом всего лишь размером тп. т :, Л(ьд ) (14) ! й(12) ь(15) ; н(кт) Рис. 112К Применение хеш-функции 6 для отображения ключей в ачейки хеш-таблицы. Ключи йа н кь отображаются в одну ячейку, вызывая коллизию.
глава !!. Хеширование и леш-таблицы !бр Однако здесь есть одна проблема: два ключа могут быть хешированы в одну и ту же ячейку. Такая ситуация называется коллизией. К счастью, имеются эффективные технологии разрешения конфликтов, вызываемых коллизиями. Конечно, идеальным решением было бы полное устранение коллизий. Мы можем попытаться добиться этого путем выбора подходящей хеш-функции Ь. Одна яз идей заключается в том, чтобы сделать функцию Ь "случайной", что позволило бы избежать коллизий или хотя бы минимизировать их количество (этот характер функции хеширования отображается в самом глаголе "1о Ьазй'*, который означает "мелко порубить, перемешать").
Само собой разумеется, функция Ь должна быть детерминистической и для одного и того же значения (с всегда давать одно н то же хеш-значение Ь(Ь). Однако поскольку ~Ц > т, должно существовать как минимум два ключа, которые имеют одинаковое хеш-значение. Таким образом, полностью избежать юллизий невозможно в принципе, и хорошая хеш-функция в состоянии только минимизировать их жзличество. Таким образом, нам все равно нужен метод разрешения возникаюгцих коллизий.
В оставшейся части данного раздела мы рассмотрим простейший метод разрешения коллизий — метод цепочек. В разделе 11.4 вы познакомитесь с егце одним методом разрешения коллизий, который называется методом открытой адресации. Разрешение коллизий с помощью цепочек При разрешении коллизий с налеон(ью г(елочек мы помещаем все элементы, хешированные в одну и ту же ячейку, в связанный список, как показано на рис.
П.З. Ячейка т' содержит указатель на заголовок списка всех элементов, хешзналение ключа которых равно т; если таких элементов нет, ячейка содержит значение нп.. Словарные операции в хеш-таблице с использованием цепочек для разрешения коллизий реализуются очень просто. Т Рве.
11З. Разрешение коллизий с помощью цепочек Кшклая ячейка хеш-таблицы Т((] содержат свлзмшый список всех ключей с хеш-значением !. Например, Ь(lсг) = Ь(lсл) н Ь(1ь) = Ь(кт) = 6(кз). Связанный список мажет быть цлннарно нлн двюкды связанным; мы показываем его как дзажлы связанный, посюльку удаление в атом случае выполняется гораздо быстрее. ! в зм. Згаа Часть Ш. Структуры данныс 290 СнА1неп-НАБн-!Изей(Т, х) 1 Вставка х в заголовок списка Т[)ь(х. Ееу)] СнА1неп-НАзн-беАЕСН(Т, Е) 1 Поиск элемента с ключом )с в списке Т[6(н)) СКА!неп-НАкн-Реьете(Т, х) ! Удаление х из списка Т~Ь(х.)сеу)] Время, необходимое для вставки в наихудшем случае, равно 0(1).
Процедура вставки выполняется очень быстро, в частности, потому, что предполагается, что вставляемый элемент отсутствует в таблице. При необходимости это предположение может быть проверено дополнительной ценой выполнения поиска элемента с ключом х.!сеу перед вставкой. Время работы поиска в наихудшем случае пропорционально длине списка; мы проанализируем эту операцию немного позже. Удаление элемента может быть выполнено за время 0(1) при использовании дважды связанных списков, как на рис.
11.3. (Обратите внимание на то, что процедура СЕА1неп-НАзн-Реьете принимает в качестве аргумента элемент х, а не его ключ, поэтому нег необходимости в предварительном поиске х. Если хеш-таблица поддерживает удаление, ее списки должны быть двусвязными для ускорения процесса удаления. Если список односвязный, то передача в качестве аргумента х не дает нам особого выигрыша, поскольку для корректного обновления атрибута пех! предшественника х нам все равно нужно выполнить поиск х в списке Т[6(х. )сеу)]. В таком случае, как нетрудно понять, удаление и поиск имеют, по сути, одно и то же асимптотическое время работы.) Анализ хешированив с цепочками Насколько высока производительность хеширования с цепочками? В частности, сколько времени требуется для поиска элемента с заданным ключом? Пусть у нас есть хеш-таблица Т с т ячейками, в которых хранятся и элементов.
Определим коэффициент занолнения сг таблицы Т как и/т, т.е. как среднее количество элементов, храняшихся в одной цепочке. Наш анализ будет опираться на значение величины а, которая может быть меньше, равна или больше единицы. В наихудшем случае хеширование с цепочками ведет себя крайне неприятно: все и ключей хешированы в одну и ту же ячейку, создав список длиной и. Таким образом, время поиска в наихудшем случае равно Сэ(п) плюс время вычисления хеш-функции, что ничуть не лучше, чем в случае использования связанного списка для хранения всех и элементов. Понятно, что использование хеш-таблиц в наихудшем случае совершенно бессмысленно. (Идеальное хеширование, применимое в случае статического множества ключей и рассмотренное в разделе 11.5.
обеспечивает высокую производительность даже в наихудшем случае.) Производительность хеширования в среднем случае зависит от того, насколько хорошо хеш-функция Ь распределяет множество сохраняемых ключей по га ячейкам в среднем. Мы рассмотрим этот вопрос подробнее в разделе 11.3, а пока Глава зп Хеширование и леш-таблицы будем полагать, что все элементы хешируются по ячейкам равномерно и независимо, и назовем данное предположение простаки рааномерным кешироеанием (вппр!е пп11опп ЬааЫпя). Обозначим длины списков ТЦ для з = О, 1,..., ги — 1 как и, так что (11.1) п = по + пз +...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
