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

При добавлении пары ключ-значение:

От ключа высчитывается хэш (целочисленное значение) с помощью встроенной функции hash().
Хэш используется для определения индекса (бакета) в массиве, где будет храниться пара.
Если в бакете уже есть элементы (коллизия), используется специальный алгоритм для поиска свободного или разрешения конфликта (например, открытая адресация или связные списки, хотя в CPython используется оптимизированная форма открытой адресации).

При поиске значения по ключу:

От заданного ключа также высчитывается хэш.
Хэш указывает на потенциальный бакет в массиве.
Система проверяет элементы в этом бакете. Поскольку хэши могут совпадать для разных ключей (коллизии), дополнительно сравнивается сам ключ (используя __eq__).

В среднем, этот процесс занимает O(1) (константное время), независимо от количества элементов в словаре. В худшем случае (очень много коллизий и неу_дачное распределение хэшей) время может стремиться к O(n) (линейное время), но на практике это встречается редко благодаря хорошей реализации хэш-функций и механизмов разрешения коллизий.

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

# Пример вычисления хэша
key = "example_key"
hashed_key = hash(key)
print(f"Хэш ключа '{key}': {hashed_key}")

# Словарь
my_dict = {"a": 1, "b": 2, "c": 3}

# Быстрый доступ по ключу
value = my_dict["b"] # O(1) в среднем
print(f"Значение для ключа 'b': {value}")

Почему поиск по ключам в словаре осуществляется быстро?