Что хотят услышать интервьюеры:

В среднем вставка и доступ по ключу в dict работают за O(1). В худшем случае возможна деградация до O(n) из-за большого числа коллизий или затрат на перераспределение таблицы. На практике Python-словарь обычно ведёт себя как структура с константным временем операций.

Определение:

dict в Python — это хеш-таблица. Для каждого ключа вычисляется хеш, по нему определяется позиция в таблице, и дальше значение ищется или добавляется почти напрямую. Поэтому в среднем операции вставки, обновления и получения элемента выполняются за O(1).

В худшем случае, когда много ключей попадает в одни и те же ячейки или таблицу нужно расширять, время операции может стать O(n). При этом n — число элементов в словаре.

Пример использования:

prices = {}

# вставка
prices["apple"] = 120
prices["banana"] = 90

# обновление
prices["apple"] = 130

# доступ по ключу
value = prices["apple"]
print(value)  # 130

В этом примере каждая вставка и обращение по ключу обычно выполняются за O(1) в среднем.

Пояснение кода:

prices = {} — создаётся пустой словарь.
prices["apple"] = 120 — добавляется новая пара ключ-значение.
prices["banana"] = 90 — добавляется ещё одна пара.
prices["apple"] = 130 — значение по существующему ключу перезаписывается.
prices["apple"] — поиск значения по ключу; обычно это операция O(1) в среднем.

Ключевые моменты:

Средняя сложность вставки в dict — O(1).
Средняя сложность доступа и обновления по ключу — тоже O(1).
Худший случай для этих операций — O(n).
Деградация возникает из-за коллизий и внутренних операций перераспределения памяти.
На практике dict в Python очень эффективен и широко используется для быстрых поисков по ключу.

Какая сложность вставки и индексации в словаре в Python в среднем и в худшем случае?