Почему сложность времени вставки хэш-таблицы в наихудшем случае не равна N log N

Question

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

Рассмотрим хеш-таблицу, в которой каждый сегмент содержит BST, сбалансированный по AVL.Если бы моя хеш-функция возвращала один и тот же индекс для каждого ключа, я бы сохранял все в одном и том же дереве AVL.Я знаю, что эта хеш-функция будет очень плохой и не будет использоваться, но я делаю сценарий наихудшего случая здесь.Итак, через некоторое время скажем, что фактор изменения размера достигнут.Поэтому, чтобы изменить размер, я создал новую хэш-таблицу и попытался вставить все старые элементы в мою предыдущую таблицу.Поскольку хеш-функция отображает все обратно в одно дерево AVL, мне нужно будет вставить все N элементов в один AVL.N вставка в дереве AVL - это N logN.Итак, почему наихудший случай вставки для хеш-таблиц считается O (N)?

Вот доказательство добавления N элементов в Avl три: N logN: Время добавления N элементов в пустое дерево AVL

Answer 1

Короче говоря : это зависит от того, как реализовано ведро.Со связанным списком это можно сделать в O (n) при определенных условиях.Для реализации с деревьями AVL в качестве сегментов это действительно может привести к O (n log n) .Чтобы вычислить временную сложность, реализация блоков должна быть известна.

Часто сегмент не реализуется с помощью дерева AVL или дерева в целом, но со связаннымсписок.Если есть ссылка на запись списка last, добавление может быть выполнено в O (1) .В противном случае мы все равно можем достичь O (1) путем с добавлением связанного списка (в этом случае сегменты хранят данные в обратном порядке вставки).

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

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

Статья Википедии о Хеш-таблица s обсуждает, как сегменты могут быть реализованы.