Какова временная сложность операций чтения и записи в dict в Python

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

Понимаете ли вы, откуда берётся O(1) у dict и при каких условиях он перестаёт быть O(1). Следом обычно спрашивают, что может быть ключом и почему, а иногда как устроен порядок ключей.

Как отвечать

dict в CPython это хеш-таблица с открытой адресацией: ключ хешируется, по хешу выбирается ячейка, а если она занята, перебираются следующие по псевдослучайной последовательности. Цепочек списков, как в учебнике, нет.

• чтение d[k], k in d, get: O(1) в среднем, O(n) в худшем случае, когда много ключей претендует на одни и те же ячейки;
• запись и удаление: O(1) в среднем. При заполнении таблица перестраивается целиком за O(n), но редко, поэтому вставка амортизированно O(1). Удалённые ключи оставляют служебные метки, которые вычищаются при перестройке;
• обход, копирование, dict(other): O(n);
• стоимость хеша: для строки хеш считается за O(длины), но кешируется в самом объекте и повторно не пересчитывается.

С Python 3.6 словарь хранит компактный массив индексов отдельно от массива записей, поэтому занимает меньше памяти, а с 3.7 порядок вставки гарантирован языком.

Ключ обязан быть хешируемым, и хеш не должен меняться, пока ключ лежит в словаре. Поэтому list ключом быть не может, а tuple из неизменяемых элементов может. Хеши строк рандомизируются при каждом запуске интерпретатора (PYTHONHASHSEED): это защита от атаки подбором коллизий, из-за которой словарь с пользовательскими данными выродился бы в O(n) на операцию.

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

Говорят «всегда O(1)». Худший случай существует: достаточно своего класса с __hash__, возвращающим константу, и каждая операция станет линейной.

Определяют в классе __eq__ и забывают про __hash__. Python в этом случае выставляет __hash__ = None, и объекты перестают годиться в ключи.

Кладут в словарь объект, а потом меняют поле, от которого зависит хеш. Запись остаётся в таблице, но найти её по ключу уже нельзя.