Какие операции добавления, поиска и удаления есть в словаре Python и какова их временная сложность

Что проверяют

Понимаете ли вы, что за словарём стоит хеш-таблица, и откуда берутся «средние» O(1) и худшие O(n). Следом часто просят объяснить, какие объекты годятся в ключи и почему список туда положить нельзя.

Как отвечать

Пройдитесь по операциям с оценками для среднего случая:

• вставка и замена: d[k] = v, d.setdefault(k, v), d.update(other). Одна вставка стоит O(1) амортизированно: при заполнении таблица перестраивается целиком за O(n), но редко. update стоит O(len(other));
• поиск: d[k] (бросает KeyError), d.get(k, default), k in d, всё O(1) в среднем;
• удаление: del d[k] и d.pop(k, default) за O(1), d.popitem() снимает последнюю вставленную пару тоже за O(1), d.clear() за O(n);
• обход: keys(), values(), items() возвращают представления за O(1), а проход по ним стоит O(n).

Дальше про устройство. С версии 3.7 порядок вставки гарантирован языком: в CPython есть плотный массив записей и отдельный разреженный массив индексов, поэтому словарь и компактнее, и хранит порядок. Коллизии разрешаются открытой адресацией с псевдослучайным пробингом, а не цепочками. Ключ обязан быть хешируемым: __hash__ не меняется за время жизни объекта и согласован с __eq__. Поэтому list и dict ключами быть не могут, а tuple из неизменяемых элементов может.

Худший случай O(n) на операцию наступает, когда много ключей дают один хеш. Для строк это закрыто рандомизацией хеша (PYTHONHASHSEED), но собственный класс с плохим __hash__ воспроизводит его легко.

Где спотыкаются

Говорят «O(1) всегда». Правильно так: в среднем и амортизированно, худший случай O(n).

Считают v in d.values() таким же быстрым, как k in d. Поиск по значениям это линейный проход.

Меняют словарь во время обхода. Добавление или удаление ключа внутри for k in d даёт RuntimeError: dictionary changed size during iteration, обходить нужно копию list(d).