Какова временная сложность добавления и удаления элемента в словарь в Python?

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

Понимаете ли вы, что за d[k] = v стоит хеш-таблица, и различаете ли средний и худший случай. Вопрос лёгкий на входе, но следом спросят, почему бывает O(n), какие объекты годятся в ключи и что происходит при росте словаря.

Как отвечать

Короткий ответ: вставка, удаление и поиск это O(1) в среднем и амортизированно, O(n) в худшем случае. Дальше объясните, откуда эти оценки.

• устройство: dict в CPython это хеш-таблица с открытой адресацией и псевдослучайным пробированием, а не цепочки списков. С версии 3.7 порядок вставки гарантирован языком: индексная таблица хранит позиции, а сами пары лежат подряд в плотном массиве;
• средний случай: хеш считается за константу для чисел, а у строк кешируется прямо в объекте, дальше один или несколько пробников по таблице;
• худший случай: если у множества ключей совпадают хеши, поиск вырождается в перебор. Для строк от подбора коллизий защищает рандомизация хеша при старте процесса (PYTHONHASHSEED), а вот собственный __hash__, возвращающий константу, легко превращает словарь в список;
• амортизация: при заполнении примерно на две трети таблица перестраивается с переносом всех записей, то есть отдельная вставка изредка стоит O(n). Усреднённая по последовательности вставок цена всё равно O(1);
• удаление: del не сжимает таблицу, а помечает слот как удалённый. Память сама по себе не возвращается, компактизация идёт только при перестройке;
• требования к ключу: хешируемость и согласованность __hash__ с __eq__. Изменяемый объект в ключах недопустим, а ключ, изменённый после вставки, теряется в таблице.

Полезное дополнение: k in d это O(1), а v in d.values() это O(n), и на такой замене регулярно теряют производительность.

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

Говорят «O(1) всегда» и не могут назвать сценарий деградации. Продолжения про коллизии интервьюер и ждёт.

Считают O(1) стоимость хеширования любого ключа. Хеш длинной строки или большого кортежа считается по всем элементам, то есть зависит от размера ключа, просто не зависит от размера словаря.

Приписывают словарю свойства списка. del lst[0] это O(n) из-за сдвига хвоста, del d[k] ничего не сдвигает и такой цены не имеет.