6.3. Трудоёмкость операций

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

• хеширование ключа элемента и вычисление индекса заголовка списка в массиве цепочек коллизий,

• поиск в списке элемента с заданным ключом,

• выполнение операции над элементом.

Трудоёмкость операций зависит от средней длины списков, которую можно вычислить как α = n/m, где n – число занесенных в таблицу элементов, m – размер хеш-таблицы. С учётом первоначального хеширования ключа перед просмотром списка оценку трудоёмкости можно записать, как O(1+α/2) [3]. Величина α учитывает фактор заполнения таблицы и называется коэффициентом заполнения таблицы. Трудоёмкость операций в хеш-таблице зависит не от числа элементов n, содержащихся в ней, а от коэффициента заполнения α. Для хеш-таблиц с цепочками коллизий величина α может быть меньше и больше единицы.

Зависимость трудоёмкости операций от заполнения справедлива и для хеш-таблиц с открытой адресацией. Чем более заполнена хеш-таблица, тем больше возникает коллизий и проб при зондировании. Приведённые в приложении 5 алгоритмы трёх основных операций для хеш-таблицы с открытой адресацией демонстрируют этот процесс.

Так же, как при анализе хеширования с цепочками коллизий, трудоёмкость операций с открытой адресацией оценивается в терминах коэффициента заполнения α. Для открытой адресации α ≤ 1. Анализ трудоёмкости операций для хеш-таблиц с открытой адресацией более сложен, чем для хеш-таблиц с цепочками коллизий [3, 4, 6]. Помимо коэффициента α трудоёмкость операции зависит от её алгоритма, метода зондирования, вероятности промахов операций. Поскольку в основе всех операций лежит определение наличия или отсутствия ключа в таблице, то трудоёмкость операций оценивается в количестве проб зондирования, выполненных при поиске ключа. Ниже приведены оценки трудоёмкости успешного или не успешного поиска ключа в зависимости от метода зондирования [4]:

Таблица 3

Метод зондирования	Успешный поиск ключа	Не успешный поиск ключа
Линейное зондирование	1/2(1+ 1/(1- α))	(1/2(1+ 1/(1- α))^2
Квадратичное зондирование	-ln(1- α)/ α	1/(1- α)
Зондирование с двойным хешированием	-ln(1- α)/ α	1/(1- α)

Обход хеш-таблицы заключается в просмотре элементов, хранящихся в хеш-таблице для выполнения над ними некоторой операции. Для хеш-таблиц с цепочками коллизий обход сводится к просмотру всех непустых списков. Поэтому трудоёмкость обхода можно оценить, как сумму длин просмотренных списков, которая равна числу элементов в таблице. То есть, трудоёмкость обхода имеет оценку O(n). В хеш-таблице с открытой адресацией ведётся поиск всех занятых ячеек, хранящих данные. Трудоёмкость просмотра соответствует размеру хеш-таблицы и выражается оценкой O(m).