Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 57
Текст из файла (страница 57)
Однако если ключ не хранится в ячейке таблицы, то нам нужен какой-то иной механизм для того, чтобы помечать пустые ячейки. Упражнения 11.1-1. Предположим, что динамическое множество Я представлено таблицей с прямой адресацией Т длины т. Опишите процедуру, которая находит максимальный элемент Я. Чему равно время работы этой процедуры в наихудшем случае? 11.1-2.
Битовый вектор представляет собой массив битов (нулей и единиц). Битовый вектор длиной т занимает существенно меньше места, чем массив из т, указателей. Каким образом можно использовать битовый вектор для представления динамического множества различных элементов без сопузствующих данных? Словарные операции должны выполняться за время О ~11. 11.1-3. предложи ге способ реализации таблицы с прямой адресацией, в которой ключи хрцнящнхся элементов могут совпадать, а сами элементы — иметь сопутствующие данные.
Все словарные операции — вставки, удаления и поиска — должны выполняться за время 0(1). (Не забудьте, что ар- Глава 11. Хеш-таблицы 285 гументом процедуры удаления является указатель на удаляемый обьект, а не ключ.) * 11.1-4. Предположим, что мы хотим реализовать словарь с использованием прямой адресации очень большого массива. Первоначально в массиве может содержаться "мусор", но инициализация всего массива нерациональна в силу его размера. Разработайте схему реализации словаря с прямой адресацией при описанных условиях.
Каждый хранимый объект должен использовать О (1) памяти; операции вставки, удаления и поиска должны выполняться за время О (1); инициализация структуры данных также должна выполняться за время О (1). ( хказание: для определения, является ли данная запись в большом массиве корректной или нет, воспользуйтесь дополнительным стеюм, размер юторого равен количеству ключей, сохраненных в словаре.) 11.2 Хеш-таблицы Недостаток прямой адресации очевиден: если пространство ключей У велико, хранение таблицы Т размером ~Ц непрактично, а то и вовсе невозможно — в зависимости от количества доступной памяти и размера пространства ключей.
Кроме того, множество К реально сохраненных ключей может быть малб по сравнению с пространством ключей У, а в этом случае память, выделенная для таблицы Т, в основном расходуется напрасно. Когда множество К хранящихся в словаре ключей гораздо меньше пространства возможных ключей У, хеш-таблица требует существенно меньше места, чем таблица с прямой адресацией. Точнее говоря, требования к памяти могут быть снижены до 9 (~К~), при этом время поиска элемента в хеш-таблице остается равным О (1). Надо только заметить, что это граница среднего времени поиска, в то время как в случае таблицы с прямой адресацией эта граница справедлива для наихудшего случая.
В случае прямой адресации элемент с ключом й хранится в ячейке й. При хешировании этот элемент хранится в ячейке Ь (Й), т.е. мы используем хеш-функиию Ь для вычисления ячейки для данного ключа (с. Функция Ь отображает пространство ключей У на ячейки хеш-таблииы Т [О..т — 1]: Ь: ь1- (0,1,...,т — 1). Мы говорим, что элемент с ключом (с хешируется в ячейку 6 ()г); величина л (й) называется хеш-значением ключа й.
На рис. 11.2 представлена основная идея хеширования. Цель хеш-функции состоит в том, чтобы уменьшить рабочий диапазон индексов массива, и вместо ~Ц значений мы можем обойтись всего лишь т значениями. Соответственно снижаются и требования к количеству памяти. 286 Часть 1!!. Структуры данных Рнс. 11.2. Использование хеш-функции 6 для отображения ключей в ячейки хеш-таблицы. Ключи !сз и Ц отображаются в одну ячейку, вызывая коллизию Однако здесь есть одна проблема: два ключа могут быть хешированы в одну и ту же ячейку. Такая ситуация называется коллизией. К счастью, имеются эффективные технологии для разрешения конфликтов, вызываемых коллизиями. Конечно, идеальным решением было бы полное устранение коллизий.
Мы можем попытаться добиться этого путем выбора подходящей хеш-функции 6. Одна из идей заключается в том, чтобы сделать 6 "случайной", что позволило бы избежать коллизий или хотя бы минимизировать их количество (этот характер функции хеширования отображается в самом глаголе "1о !зазЬ", который означает "мелко порубить, перемешать"). Само собой разумеется, функция Ь должна быть детерминистической и для одного и того же значения Й всегда давать одно и то же хеш-значение 6(к). Однако поскольку !У! ) пз, должно существовать как минимум два ключа, которые имеют одинаковое хеш-значение. Таким образом, полностью избежать коллизий невозможно в принципе, и хорошая хеш-функция в состоянии только минимизировать количество коллизий.
Таким образом, нам крайне необходим метод разрешения возникающих коллизий. В оставшейся части данного раздела мы рассмотрим простейший метод разрешения коллизий — метод цепочек. В разделе 11.4 вы познакомитесь с еще одним методом разрешения коллизий, который называется методом открытой адресации. Разрешение коллизий при помощи цепочек При использовании данного метода мы объединяем все элементы, хешированные в одну и ту же ячейку, в связанный список, как показано на рис. 11.3. Ячейка з содержит указатель на заголовок списка всех элементов, хеш-значение ключа которых равно з; если таких элементов нет, ячейка содержит значение мь.
На Глава 11. Хеш-таблицы 287 Рис. 11.3. Разрешение коллизий при помощи цепочек рис. 11.3 показано разрешение коллизий, возникающих из-за того, что 6(6~) = = 6 (Й4)~ 6 (65) = 6 (62) = 6 (Йт) И 6 (68) = 6 (Йб). Словарные операции в хеш-таблице с использованием цепочек для разрешения коллизий реализуются очень просто: СнАпчю НАзн 1изект(Т,х) Вставить х в заголовок списка Т[6(6еу[х])] СнАпчю НАзн БеАксн(Т,6) Поиск элемента с ключом 6 в списке Т[6(к)] СнАпчн> НАзн Пн.ете(Т, х) Удаление х из списка Т[6(кеу[к])] Время, необходимое для вставки в наихудшем случае, равно 0(1).
Процедура вставки выполняется очень быстро, поскольку предполагается, что вставляемый элемент отсутствует в таблице. При необходимости это предположение может быть проверено путем выполнения поиска перед вставкой. Время работы поиска в наихудшем случае пропорционально длине списка; мы проанализируем эту операцию немного позже. Удаление элемента может быть выполнено за время О (1) при использовании двусвязных списков. (Обратите внимание на то, что процедура СнАпчеп НАзн Пеьете принимает в качестве аргумента элемент к, а не его ключ, поэтому нет необходимости в предварительном поиске х. Если список односвязный, то передача в качестве аргумента х не дает нам особого выигрыша, поскольку для корректного обновления поля пех1 предшественника и нам все равно надо выполнить поиск ж в списке Т [6 (кеу[т])].
В таком случае, как нетрудно понять, удаление и поиск имеют по сути одно и то же время работы.) Часть 111. Структуры данных 288 Анализ хеширования с цепочками Насколько высока производительность хеширования с цепочками? В частности, сколько времени требуется для поиска элемента с данным ключом? Пусть у нас есть хеш-таблица Т с т ячейками, в которых хранятся и элементов. Определим коэффициент заполнения таблицы Т как а = п/т, т.е. как среднее количество элементов, хранящихся в одной цепочке. Наш анализ будет опираться на значение величины а, которая может быть меньше, равна или больше единицы. В наихудшем случае хеширование с цепочками ведет себя крайне неприятно: все и ключей хешированы в одну и ту же ячейку, создавая список длиной п.
Таким образом, время поиска в наихудшем случае равно 9 (и) плюс время вычисления хеш-функции, что ничуть не лучше, чем в случае использования связанного списка для хранения всех и элементов. Понятно, что использование хештаблиц в наихудшем случае совершенно бессмысленно. (Идеальное хеширование (применимое в случае статического множества ключей), которое будет рассмотрено в разделе 11.5, обеспечивает высокую производительность даже в наихудшем случае.) Средняя производительность хеширования зависит от того, насколько хорошо хеш-функция 6 распределяет множество сохраняемых ключей по т ячейкам в среднем. Мы рассмотрим этот вопрос подробнее в разделе 11.3, а пока будем полагать, что все элементы хешируются по ячейкам равномерно и независимо, и назовем данное предположение "простым равнамерным хешированием" (вппр1е нл11опп лазЬшй).
Обозначим длины списков Т [э] для з = 0,1,...,т — 1 как и, так что (11.1) и = по + п1 + . + и а среднее значение и равно Е [и ] = о = п(т. Мы считаем, что хеш-значение 6 (й) может быть вычислено за время О (1), так что время, необходимое для поиска элемента с ключом й, линейно зависит от длины п„1ь) списка Т [Ь ()с)]. Не учитывая время О (1), требующееся для вычисления хеш-функции и доступа к ячейке 6 (Й), рассмотрим математическое ожидание количества элементов, которое должно быть проверено алгоритмом поиска (т.е. количество элементов в списке Т [1з (1с)], которые проверяются на равенство их ключей величине к). Мы должны рассмотреть два случая: во-первых, когда поиск неудачен и в таблице нет элементов с ключом 1с, и, во-вторых, когда поиск заканчивается успешно и в таблице определяется элемент с ключом й.
Теорема 11.1. В хеш-таблице с разрешением коллизий методом цепочек математическое ожидание времени неудачного поиска в предположении простого равномерного хеширования равно 6 (1+ а). Глава 11. Хеш-таблицы 289 Доказательство. В предположении простого равномерного хеширования любой ключ /с, который еще не находится в таблице, может быть помещен с равной вероятностью в любую из т ячеек. Математическое ожидание времени неудачного поиска ключа Ь равно времени поиска до конца списка Т [Ь (к)], математическое ожидание длины которого Е ~пь1ь1] = а.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
