Как работает словарь под капотом в Python?

В Python словарь (dict) реализован как хеш-таблица с открытой адресацией и разрешением коллизий через пробирование (open addressing с linear probing или похожим методом).

Основные моменты:

• Ключи хешируются с помощью встроенной функции hash(), результат используется для определения индекса в массиве.
• При коллизии (когда два ключа попадают в один индекс) происходит поиск следующей свободной ячейки по определённой стратегии (например, линейное или двойное пробирование).
• Словарь динамически расширяется при достижении определённой загрузки, чтобы сохранить эффективность операций.
• Для оптимизации словарь хранит пары ключ-значение в массиве, а также специальный маркер для удалённых элементов.

Это обеспечивает амортизированное время доступа, вставки и удаления близкое к O(1).

Пример:

my_dict = {}
my_dict['key'] = 'value'  # Хешируется 'key', находится индекс, вставляется значение
value = my_dict.get('key')  # Быстрый доступ по хешу

Таким образом, словарь в Python — это высокоэффективная структура данных, оптимизированная для быстрого доступа и динамического изменения.