Какова сложность поиска в dict в худшем случае?

Как работает dict в Python

Словарь (dict) в Python реализован на основе хеш-таблицы. Каждый ключ преобразуется в хеш-значение, которое определяет индекс в массиве для хранения пары ключ-значение. В идеале это даёт доступ за O(1).

Почему сложность может ухудшиться

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

Пример кода

# Искусственно создаём коллизии (не делайте так в реальном коде)
class BadKey:
    def __hash__(self):
        return 42  # Все ключи имеют одинаковый хеш

d = {BadKey(): i for i in range(1000)}
# Поиск любого ключа будет O(n), так как все в одной корзине
print(d[BadKey()])  # Медленно

Вывод

Хотя теоретически худший случай O(n), на практике Python использует оптимизации, и коллизии редки. Словари остаются основным инструментом для быстрого поиска данных, если ключи правильно реализуют хеш-функцию.