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

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

Определение

Определение: Хеш-таблица — структура данных, которая хранит пары ключ → значение и использует hash(key) для быстрого поиска места, где лежит значение.

Почему в среднем O(1)

Обычно поиск выглядит так:

1. Вычисляется h = hash(key)

2. По h выбирается стартовый индекс в массиве

3. Если в ячейке не тот ключ, происходит “пробирование” (переход к следующей позиции по специальному правилу)

4. Когда ключ найден (сравнение через ==), возвращается значение

Среднее 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__.