Алгоритмы - построение и анализ (1021735), страница 55
Текст из файла (страница 55)
Более подробно прямая индексация рассматривается в разделе 11.1; она применима, если мы в состоянии выделить массив размера, достаточного для того, чтобы для каждого возможного значения ключа имелась своя ячейка. Если количество реально хранящихся в массиве ключей малб по сравнению с количеством возможных значений ключей, эффективной альтернативой массива с прямой индексацией становится хеш-таблица, которая обычно использует массив с размером, пропорциональным количеству реально хранящихся в нем ключей.
Вместо непосредственного использования ключа в качестве индекса массива, индекс вычисляется по значению ключа. В разделе 11.2 представлены основные идеи хеширования, в первую очередь направленные на разрешение коллизий (когда несколько ключей отображается в один и тот же индекс массива) при помощи 283 Глава 11. Хеш-таблицы цепочек. В разделе 11.3 описывается, каким образом на основе значений ключей могут быть вычислены индексы массива.
Здесь будет рассмотрено и проанализировано несколько вариантов хеш-функций. В разделе 11.4 вы познакомитесь с методом открытой адресации, представляющим собой еще один способ разрешения коллизий. Главный вывод, который следует из всего изложенного материала: хеширование представляет собой исключительно эффективную и практичную технологию — в среднем все базовые словарные операции требуют только О [1) времени. В разделе 11.5 будет дано пояснение, каким образом "идеальное хеширование'* может поддерживать наихудшее время поиска О (1) в случае использования статического множества хранящихся ключей 1т.е.
когда множество ключей, будучи сохраненным, более не изменяется). 11.1 Таблицы с прямой адресацией Прямая адресация представляет собой простейшую технологию, которая хорошо работает для небольших множеств ключей. Предположим, что приложению требуется динамическое множество, каждый элемент которого имеет ключ из множества У = 10, 1,..., гп — Ц, где ги не слишком велико.
Кроме того, предполагается, что никакие два элемента не имеют одинаковых ключей. Для представления динамического множества мы используем массив, или таблицу с прямой адресацией, который обозначим как Т (О..т — 1], каждая позиция, или ячейка 1роз1йоп, а1о1), которого соответствует ключу из пространства ключей У. На рис. 11.! представлен данный подход.
Ячейка к указывает на элемент множества с ключом к. Если множество не содержит элемента с ключом к, то Т [к] = Н11.. На рисунке каждый ключ из пространства У = 10, 1,..., 9) соответствует индексу таблицы. Множество реальных ключей К = 12, 3, 5, 8) определяет ячейки таблицы, которые содержат указатели на элементы. Остальные ячейки 1закрашенные темным цветом) содержат значение н1ы Реализация словарных операций тривиальна: 13!кест Аппкезз 8еАксн1Т, /с) гегцгп Т[к] 13~кест Аппкезе 1нзект[Т,х) Т[пеу(х]] — х 131кест Аппкезз 1з~.ете[Т, х) Т[йер(х]] — нш Каждая из приведенных операций очень быстрая: время их работы равно О (1). В некоторых приложениях элементы динамического множества могут храниться непосредственно в таблице с прямой адресацией.
То есть вместо хранения 284 Часть 1П. Структуры данных Рис. 11.1. Реализация динамического множества с использованием таблицы с прямой адресацией ключей и сопутствующих данных элементов в объектах, внешних по отношению к таблице с прямой адресацией, а в таблице — указателей на эти объекты, этн объекты можно хранить непосредственно в ячейках таблицы (что тем самым приводит к экономии используемой памяти). Кроме того, зачастую хранение ключа не является необходимым условием, поскольку если мы знаем индекс объекта в таблице, мы тем самым знаем и его ключ. Однако если ключ не хранится в ячейке таблицы, то нам нужен какой-то иной механизм для того, чтобы помечать пустые ячейки.
Упражнения 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).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
