Какова асимптотическая сложность поиска ключа в dict в CPython (в среднем и в худшем случае)?

Question

В среднем поиск ключа в dict в CPython работает за O(1), потому что dict — это хеш-таблица: по хешу быстро находится нужная позиция. Иногда возникают коллизии (разные ключи попадают в один “район” таблицы), тогда требуется несколько проверок, но обычно это немного. В худшем случае сложность может стать O(n), если коллизий очень много и приходится проверять множество элементов. На практике CPython старается держать таблицу “разреженной” и хорошо распределять ключи, поэтому O(1) обычно сохраняется.

YeaHub · Accepted Answer

dict в CPython реализован как хеш-таблица: ключ превращается в число (хеш), и по этому числу выбирается место в таблице.ОпределениеОпределение: Хеш-таблица — структура данных, которая хранит пары ключ → значение и использует hash(key) для быстрого поиска места, где лежит значение.Почему в среднем O(1)Обычно поиск выглядит так:Вычисляется h = hash(key)По h выбирается стартовый индекс в массивеЕсли в ячейке не тот ключ, происходит “пробирование” (переход к следующей позиции по специальному правилу)Когда ключ найден (сравнение через ==), возвращается значениеСреднее O(1) достигается потому что:Хеши ключей обычно хорошо распределены по таблицеКоллизии редки и короткиеCPython расширяет таблицу при росте (поддерживает низкую “плотность”)Почему худший случай O(n)Худший случай возникает, когда много ключей попадает в один и тот же кластер (по сути “цепочка проверок” растёт):Тогда поиск может проверять много позиций, вплоть до количества элементов nТеоретически это O(n)Важно: “худший случай” — это про теорию и специально подобранные условия. В обычном коде, с нормальными ключами и корректным __hash__, это почти не встречается.Практический пример (идея коллизий)Если сделать класс с “плохим” __hash__, который всегда возвращает одно и то же, dict начнёт работать заметно медленнее:class BadKey:
    def __init__(self, x):
        self.x = x
    def __hash__(self):
        return 1  # все ключи в одну кучу
    def __eq__(self, other):
        return isinstance(other, BadKey) and self.x == other.x

d = {BadKey(i): i for i in range(10000)}
print(d[BadKey(9999)])  # будет искать дольше из-за коллизий
ВыводВ нормальных условиях dict даёт быстрый поиск O(1) и это одна из причин, почему он так популярен.Следить стоит за тем, чтобы ключи имели корректный и “нормально распределяющий” __hash__.