Алгоритмы - построение и анализ (1021735), страница 56
Текст из файла (страница 56)
Процедура вставки выполняется очень быстро, поскольку предполагается, что вставляемый элемент отсутствует в таблице. При необходимости это предположение может быть проверено путем выполнения поиска перед вставкой. Время работы поиска в наихудшем случае пропорционально длине списка; мы проанализируем эту операцию немного позже. Удаление элемента может быть выполнено за время О (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] = а. Таким образом, при неудачном поиске математическое ожидание количества проверяемых элементов равно а, а общее время, необходимое для поиска, включая время вычисления хеш-функции Ь (Ь), равно О (1+ а). Успешный поиск несколько отличается от неудачного, поскольку вероятность поиска в списке различна для разных списков и пропорциональна юличеству содержащихся в нем элементов. Тем не менее, и в этом случае математичесюе ожидание времени поиска остается равным 9 (1+ а).
Теорема 11.2. В хеш-таблице с разрешением коллизий методом цепочек математическое ожидание времени успешного поиска в предположении простого равномерного хеширования в среднем равно 9 (1+ а). Доказательсшао. Мы считаем, что искомый элемент с равной вероятностью может быть любым элементом, хранящимся в таблице. Количество элементов, проверяемых в процессе успешного поиска элемента х, на 1 больше, чем количество элементов, находящихся в списке перед х. Элементы, находящиеся в списке до х, были вставлены в список после того, как элемент х был сохранен в таблице, так как новые элементы помещаются в начало списка. Для того чтобы найти математическое ожидание юличества проверяемых элементов, мы возьмем среднее значение по всем элементам таблицы, которое равно 1 плюс математическое ожидание количества элементов, добавленных в список после искомого. Пусть х, обозначает 1-й элемент, вставленный в таблицу (г = 1, 2,..., п), а Ц = = Ьеу[кч].
Определим для ключей Ь; и Ь индикаторную случайную величину Х, = 1(Ь (Ц) = Ь (/с )). В предположении простого равномерного хеширования, Рг (Ь(Ь,) = Ь (Ь )) = 1/т и, в соответствии с леммой 5.1, Е [Х, ] = 1/т. Таким образом, математическое ожидание числа проверяемых элементов в случае успешного поиска равно Е[ (в силу линейности математиче- ского ожидания) Часть ПЕ Структуры данных 290 ~) (и — 1) = 1=1 '~'и — ~~' ' 2 и 1п+1) 1 1+— пт 1 1+— ит 1 1+— пгп (в соответствии с (А.1)) =1+ т (2 О = 1+ — — —. 2 2и Следовательно, полное время, необходимое для проведения успешного поиска (включая время на вычисление хеш-функции), составляет 9 (2 + а/2 — а/2п) = = 6(1+ о). Упражнения 11.2-1. Предположим, что у нас есть хеш-функция 6 для хеширования и различных ключей в массив Т, длина которого равна т.
Чему равно математическое ожидание количества коллизий в предположении простого равномерного хеширования (точнее, мощности множества Ц/с, Ц: Й ф 1 н п(к) = Ь(1)))? 11.2-2. Продемонстрируйте вставку ключей 5, 28, 19, 15, 20, 33, 12, 17, 10 в хештаблицу с разрешением коллизий методом цепочек. Таблица имеет 9 ячеек, а хеш-функцня имеет вид и (1с) = й пюс1 9. 11.2-3. Профессор предполагает, что можно повысить эффективность хеширования с разрешением коллизий методом цепочек, если поддерживать списки в упорядоченном состоянии.
Каким образом такое изменение алгоритма повлияет на время выполнения успешного поиска, неудачного поиска, вставки и удаления? Что же означает проведенный анализ? Если количество ячеек в хеш-таблице, как минимум, пропорционально количеству элементов, хранящихся в ней, то и = О (т) и, следовательно, а = п/тп = О (т)/т = О (1), а значит, поиск элемента в хеш-таблице в среднем требует постоянного времени. Поскольку в худшем случае вставка элемента в хеш-таблицу занимает О (1) времени (как и удаление элемента при использовании двусвязных списков), можно сделать вывод, что все словарные операции в хеш-таблице в среднем выполняются за время О (1). Глава 11.
Хеш-таблицы 291 11.2-4. Предложите способ хранения элементов внутри самой хеш-таблицы, при котором неиспользуемые ячейки связываются в один список свободных мест. Считается, что в каждой ячейке может храниться флаг и либо один элемент и указатель, либо два указателя. Все словарные операции и операции над списком свободных мест должны выполняться за время О (1). Должен ли список свободных мест быть двусвязным или можно обойтись односвязным списком? 11.2-5. Покажите, что если ~Ц ) птп, то имеется подмножество пространства ключей У размером и, состоящее из ключей, которые хешируются в одну и ту же ячейку, так что время поиска в хеш-таблице с разрешением коллизий методом цепочек в худшем случае равно 9 (и). 11.3 Хеш-функции В этом разделе мы рассмотрим некоторые вопросы, связанные с разработкой качественных хеш-функций, и познакомимся с тремя схемами их построения.
Две из них, хеширование делением и хеширование умножением, эвристичны по своей природе, в то время как третья схема — универсальное хеширование — использует рандомизацию для обеспечения доказуемого качества. Чем определяется качество хеш-функции Качественная хеш-функция удовлетворяет (приближенно) предположению простого равномерного хеширования: для каждого ключа равновероятно помещение в любую из ти ячеек, независимо от хеширования остальных ключей. К сожалению, это условие обычно невозможно проверить, поскольку, как правило, распределение вероятностей, в соответствии с которым поступают вносимые в таблицу ключи, неизвестно; кроме того, вставляемые ключи могут не быть независимыми.
Иногда распределение вероятностей оказывается известным. Например, если известно, что ключи представляют собой случайные действительные числа, равномерно распределенные в диапазоне О < й < 1, то хеш-функция 6 (й) = 11ст1 удовлетворяет условию простого равномерного хеширования. На практике при построении качественных хеш-функций зачастую используются различные эвристические методики. В процессе построения большую помощь оказывает информация о распределении ключей. Рассмотрим, например, таблицу символов компилятора, в которой ключами служат символьные строки, представляющие идентификаторы в программе.
Зачастую в одной программе встречаются похожие идентификаторы, например, р~ и р~а. Хорошая хешфункция должна минимизировать шансы попадания этих идентификаторов в одну ячейку хеш-таблицы. Часть 111. Структуры данных 292 При построении хеш-функции хорошим подходом является подбор функции таким образом, чтобы она никак не коррелировала с закономерностями, которым могут подчиняться существующие данные. Например, метод деления, который рассматривается в разделе 11.3.1, вычисляет хеш-значение как остаток от деления ключа на некоторое простое число.
Если зто простое число никак не связано с распределением исходных данных, метод часто дает хорошие результаты. В заключение заметим, что некоторые приложения хеш-функций могут накладывать дополнительные требования, помимо требований простого равномерного хеширования. Например, мы можем потребовать, чтобы "близкие" в некотором смысле ключи давали далекие хеш-значения (это свойство особенно желательно при использовании линейного исследования, описанного в разделе 11.4). Универсальное хеширование, описанное в разделе 11.3.3, зачастую приводит к желаемым результатам. Интерпретация ключей как целых неотрицательных чисел Для большинства хеш-функций пространство ключей представляется множеством целых неотрицательных чисел Х = (0,1,2,...).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
