Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 58
Текст из файла (страница 58)
Таким образом, при неудачном поиске математическое ожидание количества проверяемых элементов равно а, а общее время, необходимое для поиска, включая время вычисления хеш-функции Ь (Ь), равно О (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,...). Если же ключи не являются целыми неотрицательными числами, то можно найти способ их интерпретации как таковых. Например, строка символов может рассматриваться как целое число, записанное в соответствующей системе счисления.
Так, идентификатор р~ можно рассматривать как пару десятичных чисел (112, 116), поскольку в АБСП-наборе символов р = 112 и г. = 116. Рассматривая р~ как число в системе счисления с основанием 128, мы находим, что оно соответствует значению 112 128 + 116 = 14452. В конкретных приложениях обычно не представляет особого труда разработать метод для представления ключей в виде (возможно, больших) целых чисел. Далее при изложении материала мы будем считать, что все ключи представляют целые неотрицательные числа. 11.3.1 Метод деления Построение хеш-функции меиходам деления состоит в отображении ключа к в одну из ячеек путем получения остатка от деления /с на тп, т.е.
хеш-функция имеет вид Й (Й) = Й пюс1 т. Например, если хеш-таблица имеет размер т = 12, а значение ключа й = 100, то 6(й) = 4. Поскольку для вычисления хеш-функции требуется только одна операция деления, хеширование методом деления считается достаточно быстрым. При использовании данного метода мы обычно стараемся избегать некоторых значений т. Например, гп не должно быть степенью 2, поскольку если т = 2", то й(1с) представляет собой просто р младших битов числа к. Если только заранее Глава 11. Хеш-таблицы 293 не известно, что все наборы младших р битов ключей равновероятны, лучше строить хеш-функцию таким образом, чтобы ее результат зависел от всех битов ключа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
