Какова сложность поиска значения в словаре по ключу в Python?

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

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

Как отвечать

Поиск по ключу в dict в среднем O(1), в худшем O(n). Механика в CPython:

• хэш: считается hash(key), по младшим битам выбирается слот. У строк хэш кэшируется в самом объекте, повторный поиск по той же строке его не пересчитывает;
• коллизии: CPython использует открытую адресацию, а не цепочки. Если слот занят чужим ключом, следующий кандидат вычисляется с примесью старших битов хэша, пока не найдётся нужный ключ или пустой слот;
• сравнение: в слоте сначала проверяется тождество is, затем совпадение хэшей и только потом __eq__, поэтому поиск тем же объектом ключа особенно дешёвый;
• рост: таблица расширяется, когда заполнена примерно на две трети. Перестройка стоит O(n), но бывает редко, так что вставка амортизированно O(1);
• порядок: с Python 3.7 порядок вставки гарантирован языком. Внутри компактная раскладка: разреженный массив индексов плюс плотный массив записей.

Худший случай возникает, когда много ключей дают один хэш и поиск перебирает их все. Для str и bytes хэш рандомизирован при каждом запуске интерпретатора (PYTHONHASHSEED), это защита от атак подбором коллизий. В своих классах коллизии легко устроить самому, если __hash__ возвращает константу.

Ключ должен быть хэшируемым: list, dict и set ключом быть не могут, tuple может, если внутри только хэшируемые значения.

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

Говорят, что словарь неупорядочен. Это устарело: порядок вставки гарантирован с 3.7, а в CPython он сохранялся уже в 3.6.

Путают key in d и value in d.values(). Первое O(1), второе перебирает все значения за O(n).

Переопределяют __eq__ в классе и не определяют __hash__. Python тогда выставляет __hash__ = None, и объекты перестают быть хэшируемыми. Обратная ошибка: хэш зависит от изменяемых полей, и после изменения объекта словарь его уже не находит.