Анализ хеширования с цепочками

В этом разделе мы оценим время работы операций для хеширования с цепочками.

Пусть Г - хеш-таблица с т позициями, в которую занесено га элементов. Коэффициентом заполнения (load factor) таблицы называется число а = п/т (это число может быть и меньше, и больше единицы). Мы будем оценивать стоимость операций в терминах а.

В худшем случае хеширование с цепочками ведет себя отвратительно: если хеш-значения всех га ключей совпадают, то таблица сводится к одному списку длины га, и на поиск будет тратиться то же время в (га), что и на поиск в списке, плюс ещё время на вычисление хеш-функции. Конечно, в такой ситуации хеширование бессмысленно.

Средняя стоимость поиска зависит от того, насколько равномерно хеш-функция распределяет хеш-значения по позициям таблицы. Вопросу о том, как добиваться этой равномерности, посвящен раздел 12.3; пока же будем условно предполагать, что каждый данный элемент может попасть в любую из тп позиций таблицы с равной вероятностью и независимо от того, куда попал другой элемент. Мы будем называть это предположение гипотезой «равномерного хеширования» (simple uniform hashing).

Будем считать, что для данного ключа к вычисление хеш-значения h(k), шаг по списку и сравнение ключей требует фиксированного времени, так что время поиска элемента с ключом к линейно зависит от количества элементов в списке T[h(k)], которые мы просматриваем в процессе поиска. Будем различать два случая: в первом случае поиск оканчивается неудачей (элемента с ключом к в списке нет), во втором поиск успешен - элемент с требуемым ключом обнаруживается.

Теорема 12.1. Пусть Т - хеш-таблица с цепочками, имеющая коэффициент заполнения а. Предположим, что хеширование равномерно. Тогда при поиске элемента, отсутствующего в таблице, будет просмотрено в среднем а элементов таблицы, а среднее время такого поиска (включая время на вычисление хеш-функции) будет равно 0(1 + а).

Доказательство. Поскольку в предположении равномерного хеширования все позиции таблицы для данного ключа равновероятны, среднее время поиска отсутствующего элемента совпадает со средним временем полного просмотра одного из т списков, то есть пропорционально средней длине наших т списков. Эта средняя длина есть п/т = а, откуда получаем первое утверждение теоремы; второе утверждение получится, если добавить время 0(1) на вычисление хеш-значения.□

Теорема 12.2. При равномерном хешировании среднее время успешного поиска в хеш-таблице с цепочками есть 0(1 + а), где а - коэффициент заполнения.

Доказательство. Хотя формулировка этой теоремы похожа на предыдущую, смысл утверждения несколько иной. В предыдущей теореме мы рассматривали произвольную таблицу с коэффициентом заполнения а и оценивали среднее число действий, необходимых для поиска случайного элемента, равновероятно попадающего во все ячейки таблицы.

В этой теореме так делать нельзя: если мы возьмём произвольную таблицу и, считая все её элементы равновероятными, будем искать среднее время поиска случайно выбранного из них, то оценки вида 0(1+ а) не получится (контрпример: таблица, в которой все элементы попали в один список)

Формулировка подразумевает двойное усреднение: сначала мы рассматриваем случайно выбранную последовательность элементов, добавляемых в таблицу, причём на каждом шаге все значения ключа равновероятны и шаги независимы, а затем в полученной таблице выбираем элемент для поиска, считая все её элементы равновероятными.

Посмотрим на ситуацию в тот момент, когда таблица уже построена, но случайный элемент для поиска ещё не выбран. Чему равно среднее время поиска, усреднённое по всем п элементам таблицы? Надо сложить позиции всех элементов в своих списках и поделить сумму на п (общее число элементов).

Если представить себе, что при заполнении таблицы элементы дописывались в конец соответствующих списков (см. упр. 12.2-3), то упомянутая сумма по порядку величины равна общему число операций, выполненных при заполнении таблицы (поскольку при добавлении в конец и при поиске выполняется одно и то же количество действий).

Теперь вспомним об усреднении по различным возможностям в процессе построения таблицы. При добавлении в неё г-го элемента математическое ожидание числа действий равно 0(1 + [г - 1)/т) (см. доказательство предыдущей теоремы), и потому математическое ожидание общего числа действий при заполнении таблицы, делённое на п, есть

e(±£(i + ))=e(i + J-Bi-i>) =

у п \ т ) Iу птI

\ пт 2 )

= e(1 + i-)=e<1 + 0-

□

Если количество позиций в хеш-таблице считать пропорциональным числу элементов в таблице, то из доказанных теорем вытекает, что среднее время на поиск (в оптимистических предположениях о распределении вероятностей) есть 0(1). В самом деле, если п = О (га), то а = п/т = 0(1) и 0(1 + а) = 0(1). Поскольку стоимость добавления в хеш-таблицу с цепочками есть 0(1) (даже при добавлении в конец, см. упр. 12.2-3), а стоимость удаления элемента есть 0(1) (мы считаем, что списки двусторонне связаны), среднее время выполнения любой словарной операции (в предположении равномерного хеширования) есть 0(1).

Упражнения

12.2-1 Пусть h - случайная хеш-функция, сопоставляющая с каждым из п различных ключей {к\, к2, , кп} одну из га позиций в таблице. Каково математическое ожидание числа коллизий (точнее, числа пардля которых что h(ki) = h(kj))?

12.2-2 Как будет выглядеть хеш-таблица с цепочками после того, как в неё последовательно поместили элементы с ключами 5,28,19,15,20,33,12,17,10 (в указанном порядке)? Число позиций в таблице равно 9, хеш-функция имеет вид h(k) = к mod 9.

12.2-3 Покажите, что математическое ожидание времени добавления нового элемента (в предположении равномерного хеширования) есть 0(1 + а), если мы добавляем новый элемент в конец соответствующей цепочки.

12.2-4 Профессор предполагает, что хеширование с цепочками будет гораздо эффективнее, если списки элементов с данным хеш-значением будут упорядоченными. Как этот подход повлияет на стоимость успешного поиска, поиска отсутствующего элемента, добавления, удаления?

12.2-5 Разработайте реализацию хеш-таблицы с цепочками, в которой записи хранятся внутри самой хеш-таблицы (неиспользуемые позиции связываются в список свободных мест). Считайте, что в каждой позиции могут храниться либо флаг и два указателя, либо флаг, указатель и элемент. Все словарные операции, а также операции по выделению и освобождению места, должны выполняться за время 0(1). Обязательно ли делать список свободных мест двусторонне связанным?

12.2-6 Пусть общее число возможных ключей (размер множества U) превосходит гага, где га - количество хеш-значений. Покажите,