Какова сложность операций со словарём в Python?

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

Оценка включает предположение о хорошем распределении хешей и ограниченной стоимости hash/eq. При расширении таблицы отдельная вставка дороже, поэтому говорят об амортизированном поведении. key in d проверяет ключ эффективно, а поиск значения среди d.values() требует обхода. Ключи должны быть hashable, а равные ключи — иметь одинаковый хеш. Сохранение порядка вставки не превращает словарь в отсортированную структуру и не ускоряет запросы диапазона.