Сложность вставки в Hash Table

Question

Рассмотрим изначально пустую хеш-таблицу размера M и хеш-функцию h (x) = x mod M. В худшем случае, какова сложность времени (в обозначении Big-Oh) для вставки n ключей в таблицу, если они разделены Цепочка используется для разрешения коллизий (без перефразирования)? Предположим, что каждая запись (сегмент) таблицы хранит неупорядоченный связанный список. При добавлении нового элемента в неупорядоченный связанный список такой элемент вставляется в начало списка.

Answer 1

При отсутствии столкновений вставка ключа в хеш-таблицу / карту равна O(1), поскольку поиск сегмента - это операция с постоянным временем. Я не ожидал бы, что это изменится в случае коллизий, если предположить, что коллизии разрешаются с использованием связанного списка и , когда новый элемент вставляется в начало списка. Причина этого заключается в том, что добавление нового элемента в заголовок связанного списка также в основном O(1). Таким образом, вставка в соответствии с этими предположениями также должна быть O(1), и, следовательно, вставка n ключей должна быть O(n).