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

Question

Обычно доступ к словарю близок к O(1), потому что используется хеш-таблица. Но в худшем случае может получиться O(n), если возникает много коллизий и словарю приходится проверять много кандидатов при поиске. Такое бывает при “плохих” хешах, намеренно подобранных ключах или при патологии пользовательских __hash__/__eq__. Тогда поиск превращается почти в линейный проход.

YeaHub · Accepted Answer

Словарь рассчитывает hash(key) и идёт по цепочке/последовательности проверок, пока не найдёт нужный ключ или пустую позицию.Определение: коллизия (collision) — ситуация, когда разные ключи дают одинаковый хеш или попадают в одну и ту же область размещения, из-за чего требуется дополнительная проверка ключей.Когда появляется O(n)Доступ может деградировать до O(n), когда растёт число проверок при поиске:Много коллизий по ключаммного разных ключей дают одинаковый hash(...) или постоянно конфликтуют по размещению;словарь вынужден сравнивать ключи один за другим.Некорректная реализация __hash__ у пользовательских ключейнапример, __hash__ возвращает одну и ту же константу для всех объектов.Дорогой или “плохой” __eq__ у ключейдаже если хеши разные, при коллизиях и проверках сравнения могут быть затратными;если __eq__ тяжёлый, фактическое время поиска заметно растёт.Враждебные (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__ словарю приходится проверять большое число кандидатов вместо нескольких шагов.