В каких случаях доступ к словарю может деградировать до O(n)?

Словарь рассчитывает hash(key) и идёт по цепочке/последовательности проверок, пока не найдёт нужный ключ или пустую позицию.

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

Когда появляется O(n)

Доступ может деградировать до O(n), когда растёт число проверок при поиске:

1. Много коллизий по ключам

   • много разных ключей дают одинаковый hash(...) или постоянно конфликтуют по размещению;

   • словарь вынужден сравнивать ключи один за другим.

2. Некорректная реализация __hash__ у пользовательских ключей

   • например, __hash__ возвращает одну и ту же константу для всех объектов.

3. Дорогой или “плохой” __eq__ у ключей

   • даже если хеши разные, при коллизиях и проверках сравнения могут быть затратными;

   • если __eq__ тяжёлый, фактическое время поиска заметно растёт.

4. Враждебные (adversarial) входные данные

   • когда ключи специально подобраны, чтобы вызывать коллизии и заставлять словарь делать много шагов.

Маленький пример “плохого” ключа

class BadKey:
    def __init__(self, x): self.x = x
    def __hash__(self): return 1          # все ключи в одну "кучу"
    def __eq__(self, other): return self.x == other.x

d = {BadKey(i): i for i in range(10_000)}
print(d[BadKey(9999)])  # работать будет, но может быть заметно медленнее

Важная оговорка про O(n)

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

Вывод

Деградация до O(n) появляется, когда из-за коллизий и/или плохих __hash__/__eq__ словарю приходится проверять большое число кандидатов вместо нескольких шагов.