Что хотят услышать интервьюеры:

Доступ к элементу словаря в Python обычно считается за O(1), но в худшем случае может деградировать до O(n). Это происходит, когда возникает большое количество коллизий хешей и ключи попадают в одну и ту же цепочку/структуру поиска. Тогда для нахождения нужного элемента приходится просматривать несколько ключей подряд.

Определение:

Словарь в Python — это хеш-таблица, где ключ сначала преобразуется в хеш, а затем по нему находится позиция хранения значения. Линейное время доступа появляется, когда поиск по хеш-таблице перестает быть “почти мгновенным” из-за конфликтов хешей или из-за необходимости пройти по нескольким кандидатам для проверки равенства ключей. В норме это редкий случай, но теоретически и при плохих ключах возможен.

Пример использования:

Если в словарь положить много объектов с одинаковым __hash__, то поиск будет ухудшаться.

class BadKey:
    def __init__(self, value):
        self.value = value

    def __hash__(self):
        return 1  # все ключи имеют одинаковый хеш

    def __eq__(self, other):
        return isinstance(other, BadKey) and self.value == other.value

d = {BadKey(i): i for i in range(1000)}

key = BadKey(999)
print(d[key])

В таком случае словарю приходится сравнивать ключи последовательно, и доступ к элементу может стать близким к O(n).

Пояснение кода:

Класс BadKey переопределяет __hash__ так, что у всех объектов один и тот же хеш.
При добавлении элементов словарь не может разнести их по разным позициям по хешу.
Чтобы найти BadKey(999), Python сначала выбирает бакет по хешу, а затем проверяет равенство через __eq__.
Поскольку в одном месте хранится много ключей-кандидатов, поиск выполняется не сразу, а по нескольким сравнениям подряд.
Именно это и приводит к линейному времени в худшем случае.

Ключевые моменты:

В среднем доступ к dict — O(1).
Линейное время возникает при большом числе коллизий хешей.
Тогда поиск превращается в последовательную проверку нескольких ключей.
Переопределение __hash__ и __eq__ может сильно влиять на производительность.
На практике Python старается минимизировать коллизии, но худший случай теоретически возможен.

При каких условиях доступ к элементу в словаре осуществляется за линейное время?