Страница 8
Хеш-таблица представляет собой эффективную структуру данных для реализации словарей. Хотя на поиск элемента в хеш-таблице может в наихудшем случае потребоваться столько же времени, сколько на поиск в связанном списке, а именно - Θ(n), на практике хеширование исключительно эффективно. При вполне обоснованных допущениях среднее время поиска элемента в хеш-таблице составляет O(1).
Хеш-таблица обобщает обычный массив. Возможность прямой индексации элементов обычного массива обеспечивает доступ к произвольной позиции в массиве за время O(1). Хеширование представляет собой исключительно эффективную и практичную технологию: в среднем все базовые словарные операции выполняются за время O(1).
Недостаток прямой адресации очевиден: если совокупность ключей U велика, хранение таблицы T размером |U| непрактично, а то и вовсе невозможно - в зависимости от количества доступной памяти и размера совокупности ключей. Кроме того, множество K реально сохранённых ключей может быть мало по сравнению с совокупностью ключей U, а в этом случае память, выделенная для таблицы T, в основном расходуется напрасно.
Когда множество K хранящихся в словаре ключей гораздо меньше совокупности возможных ключей U, для хеш-таблицы требуется существенно меньше места, чем для таблицы с прямой адресацией1. Точнее говоря, требования к памяти могут быть снижены до Θ(/K/), при этом время поиска элемента в хеш-таблице останется равным O(1). Нужно только заметить, что это граница времени поиска в среднем случае, в то время как в случае таблицы с прямой адресацией эта граница справедлива для наихудшего случая.
Время, необходимое для вставки в наихудшем случае, равно O(1). Процедура вставки выполняется очень быстро, в частности, потому, что предполагается, что вставляемый элемент отсутствует в таблице. Время работы поиска в наихудшем случае пропорционально длине списка. Удаление элемента может быть выполнено за время O(1) при использовании дважды связанных списков.
Пусть у нас есть хеш-таблица T с m ячейками, в которых хранятся n элементов. В наихудшем случае хеширование с цепочками ведёт себя крайне неприятно: все n ключей хешированы в одну и ту же ячейку, создав список длиной n. Таким образом, время поиска в наихудшем случае равно Θ(n) плюс время вычисления хеш-функции, что ничуть не лучше, чем в случае использования связного списка для хранения всех n элементов. Понятно, что использование хеш-таблиц в наихудшем случае совершенно бессмысленно.
В хеш-таблице с разрешением коллизий методом цепочек время неудачного поиска в среднем случае в предположении простого равномерного хеширования составляет Θ(1 + a).
В хеш-таблице с разрешением коллизий методом цепочек время успешного поиска в среднем случае в предположении простого равномерного хеширования в среднем равно Θ(1 + a).
Если количество ячеек в хеш-таблице как минимум пропорционально количеству элементов, хранящихся в ней, то n = O(m) и, следовательно, коэффициент заполнения равен n/m = O(m)/m = O(1). Таким образом, поиск элемента в хеш-таблице в среднем требует постоянного времени. Поскольку в худшем случае вставка элемента в хеш-таблицу занимает O(1) времени (как и удаление элемента при использовании дважды связанных списков), можно сделать вывод, что все словарные операции в хеш-таблице в среднем выполняются за время O(1).
Мы проанализируем математическое ожидание количества исследований для хеширования с открытой адресацией в предположении равномерного хеширования и начнём с анализа количества исследований в случае неудачного поиска.
Математическое ожидание количества исследований при неудачном поиске в хеш таблице с открытой адресацией и коэффициентом заполнения a = n/m < 1 в предположении равномерного хеширования не превышает 1/(1-a).
Вставка элемента в хеш-таблицу с открытой адресацией и коэффициентом заполнения a в предположении равномерного хеширования требует в среднем не более 1/(1-a) исследований.
Математическое ожидание количества исследований при удачном поиске в хеш-таблице с открытой адресацией и коэффициентом заполнения a < 1, в предположении равномерного хеширования и равновероятного поиска любого из ключей не превышает
1В данном контексте автор, упоминая таблицу с прямой адресацией, не применяет термин хеш, так как, предположительно, в примере оригинальной книги не используется хеш-функция для операций поиска элемента или все операции вставки элемента являются инъективными и не нуждаются в решении проблем коллизий.
2Все доказательства теорем представлены в книге автора с целью описания минимума методического материала