Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 61
Текст из файла (страница 61)
+ и„, а ожидаемое значение и. равно Е [и ] = гл = п1гп. Мы полагаем, что для вычисления хеш-значения )з()е) достаточно времени 0(1), так что время, необходимое для поиска элемента с ключом к, линейно зависит от длины пь(ь) списка Т[Ь(/с)]. Не учитывая время 0(1), требующееся для вычисления хеш-функции и доступа к ячейке 6()е), рассмотрим математическое ожидание количества элементов, которое должно быть проверено алгоритмом поиска (т.е. количество элементов в списке Т[)л()е)], которые проверяются на равенство их ключей величине )е). Мы должны рассмотреть два случая; во-первых, когда поиск неудачен и в таблице нет элементов с ключом lс и, во-вторых, когда поиск заканчивается успешно и в таблице определяется элемент с ключом )с.
Теорема 11.1 В хеш-таблице с разрешением коллизий методом цепочек время неудачного поиска в среднем случае в предположении простого равномерного хеширования составляет Й(1+ се). Доказааеельсаеао. В предположении простого равномерного хеширования любой кпюч )е, который еще не находится в таблице, может быть помещен с равной вероятностью в любую из ги ячеек. Математическое ожидание времени неудачного поиска ключа к равно времени поиска до конца списка Т[й()е)], ожидаемая длина которого — Е [и„<ь)] = се. Таким образом, при неудачном поиске математическое ожидание количества проверяемых элементов равно а, а общее время, необходимое для поиска, включая время вычисления хеш-функции 6(к), равно 6(1+ а). Успешный поиск несколыю отличается от неудачного, поскольку вероятность поиска в списке различна для разных списков и пропорциональна количеству содержащихся в нем элементов. Тем не менее и в этом случае математическое ожидание времени поиска остается равным 9(1+ ге).
Теорема 11.2 В хеш-таблице с разрешением коллизий методом цепочек время успешного поиска в среднем случае в предположении простого равномерного хеширования в среднем равно 9(1 + се). Доказаазелвсаеео. Мы полагаем, что искомый элемент с равной вероятностью может быть любым элементом, хранящимся в таблице. Количество элементов, проверяемых в процессе успешного поиска элемента к, на 1 больше, чем количество элементов, находящихся в списке перед х. Элементы, находящиеся в списке Часть!П. Струквуры даииьсс до х, были вставлены в список после того, как элемент к был сохранен в таблице, так как новые элементы помещаются в начало списка.
Для того чтобы найти математическое ожидание количества проверяемых элементов, мы возьмем среднее по всем и элементам х в таблице значение, которое равно 1 плюс математическое ожидание количества элементов, добавленных в список к после самого искомого элемента. Пусть х; обозначает г-й элемент, вставленный в таблицу (1 = 1, 2,..., п), и пусть )с, = кп йеу. Определим для ключей Ь, и /с индикаторную случайную величину Х, = 1(Ь(Ь;) = Ь(/с,)). В предположении простого равномерного хеширования Рг (Ь(Ьз) = Ь(/сэ)) = 1/гп и, в соответствии с леммой 5.1, Е [Х, ] = 1/т. Таким образом, математическое ожидание количества проверяемых элементов в случае успешною поиска равно Š— ~~ 1+ ~~~ Х; п / и — ~1+ ~~~ Е [Х;.[ (из линейности математического ожидания) п гу 1=.
У1 .—'Е( ° Е -') 1 1+ — ~~ (и — г') ~=1 1+ — ~~~ п — ~~ 1 1+ — [п 1 / з п(п+1)1 /1 (согласно (А. 1)) 2 и — 1 =1+ 2т и о =1+ — — —. 2 2п Таким образом, полное время, необходимое для проведения успешного поиска (включая время вычисления хеш-функции), составляет 9(2 + а/2 — сг/2п) = й(1+ сь). О чем говорит проведенный анализ? Если количество ячеек в хеш-таблице как минимум пропорционально количеству элементов, хранящихся в ней, то и = 0(гп) и, следовательно, о = п/пз = О(гп)/т = О(1).
Таким образом, поиск элемента в хеш-таблице в среднем требует постоянного времени. Поскольку в худшем случае вставка элемента в хеш-таблицу занимает 0(1) времени (как и удаление элемента при использовании дважды связанных списков), можно сделать вывод, что все словарные операции в хеш-таблице в среднем выполняются за время 0(1). «93 Г«ава и.
Хеширование и «еш-таввицы Упражнения п.гп Предположим, что мы используем хеш-функцию 6 для хеширования и различных ключей в массив Т, длина которого равна т. Чему равно математическое ожидание количества коллизий в предположении простого равномерного хеширования? Говоря точнее, каюва ожидаемая мощность множества ((к,1): к ф 1 и 6(/с) = Ь(1))? п.г.г Продемонстрируйте происходящее при вставке в хеш-таблицу с разрешением коллизий методом цепочек ключей б, 28, 19, 15, 20, 33, 12, 17, 10.
Таблица имеет 9 ячеек, а хеш-функция имеет вид 6(к) = к щи 9. п.г.з Профессор выдвинул гипотезу о том, что можно существенно повысить эффективность хеширования с разрешением коллизий методом цепочек, если поддерживать списки в упорядоченном состоянии. Каким образом такое изменение алгоритма повлияет на время выполнения успешного поиска, неудачного поиска, вставки и удаления? П,гой Предложите способ выделения и освобождения элементов внутри самбй хештаблицы, при котором неиспользуемые ячейки связываются в один список свободных мест.
Считается, что в каждой ячейке может храниться флаг и либо один элемент и указатель, либо два указателя. Все словарные операции и операции над списком свободных мест должны выполняться за ожидаемое время 0(1). Должен ли список свободных мест быть двусвязным или можно обойтись односвязным списком? п.г.5 Предположим, что необходимо хранить множество из и ключей в хеш-таблице размером т. Покажите, что если ключи выбираются из совокупности П с ((7! > пт, то П имеет подмножество размером и, состоящее из ключей, хешируемых в одну и ту же ячейку, так что время поиска при хешировании с цепочками в наихудшем случае составляет ~Э(п).
п.г. 6 Предположим, что необходимо хранить множество из и ключей в хеш-таблице размером т, с разрешением коллизий методом цепочек, и что известна длина каждой цепочки, включая длину Ь самой длинной из них. Опишите процедуру, которая случайным образом выбирает ключ среди всех ключей таблицы за ожидаемое время 0(1 (1+ 1/о)) (все вероятности выбора каждого из ключей одинаковы). 294 Часть Н1.
Ояруквурм данными 11.3. Хеш-функции В этом разделе мы рассмотрим некоторые вопросы, связанные с разработкой качественных хеш-функций, и познакомимся с тремя схемами их построения. Две из них, хеширование делением и хеширование умножением, эвристичны по своей природе, в то время как третья схема — универсальное хеширование — использует рандомизацию для обеспечения доказуемо высокой производительности, Чем определяется качество хеш-функции Качественная хеш-функция удовлетворяет (приближенно) предположению простого равномерного хеширования: для каждою ключа равновероятно помещение в любую из т ячеек независимо от хеширования остальных ключей.
К сожалению, это условие обычно невозможно проверить, поскольку, как правило, распределение вероятностей, в соответствии с которым поступают вносимые в таблицу ключи, неизвестно. Более того, вставляемые ключи могут не быть независимымн. Иногда распределение вероятностей оказывается известным. Например, если известно, что ключи представляют собой случайные действительные числа, равномерно распределенные в диапазоне О < и < 1, то хеш-функция Ь()с) = ~)ст) удовлетворяет условию простого равномерного хеширования. На практике при построении качественных хеш-функций зачастую используются различные эвристические методики.
В процессе построения большую помощь оказывает информация о распределении ключей. Рассмотрим, например, таблицу символов компилятора, в которой ключами служат символьные строки, представляющие идентификаторы в программе. Зачастую в одной программе встречаются похожие идентификаторы, например рг. и р1в. Хорошая хешфункция должна минимизировать шансы попадания этик идентификаторов в одну ячейку хеш-таблицы.
При построении хеш-функции хорошим подходом является подбор функции таким образом, чтобы она никак не коррелировала с закономерностями, которым могут подчиняться существующие данные. Например, метод деления, который рассматривается в разделе 11.3.1„вычисляет хеш-значение как остаток от деления ключа на некоторое простое число.
Если это простое число никак не связано с распределением исходных данных, метод часто дает хорошие результаты. В заключение заметим, что некоторые приложения хеш-функций могут накладывать более строгие требования по сравнению с требованиями простого равномерного хеширования. Например, мы можем потребовать, чтобы "близкие" в некотором смысле ключи давали далекие хеш-значения (это свойство особенно желательно при использовании линейного исследования, описанного в разделе 11.4). Универсальное хеширование, описанное в разделе 11.3.3, часто приводит к желаемым результатам.
Глава П. Хеширование и леш-тайницы Интерпретация ключей как целых неотрицательных чисел Для большинства хеш-функций совокупность ключей представляется множеством целых неотрицательных чисел И = 10,1,2,...). Если же ключи не являются целыми неотрицательными числами, то можно найти способ их интерпретации как таковых. Например, строка символов может рассматриваться как целое число, записанное в соотвегствуюШей системе счисления. Так, идентификатор рб можно рассматривать как пару десятичных чисел (112, 116), поскольку в АЗСП-наборе символов р = 112 и с = 116. Рассматривая рб как число в системе счисления с основанием 128, мы находим, что оно соответствует значению (112 128) + 116 = 14452. В конкретных приложениях обычно не представляет особого труда разработать метод для представления ключей в виде (возможно, больших) целых чисел.
Далее при изложении материала мы будем считать, что все ключи представляют собой целые неотрицательные числа. 11.3.1. Метод деления Построение хеш-функции мелладом деления состоит в отображении ключа к в одну из т ячеек путем получения остатка от деления /с на т, т.е. хеш-функция имеет вид Ь(/с) = Й шол) т . Например, если хеш-таблица имеет размер т = 12, а значение ключа /с = 100, то л(/с) = 4. Поскольку для вычисления хеш-функции требуется только одна операция деления, хеширование методом деления достаточно быстрое.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
