Как устроен словарь под капотом

Словарь в Python реализован как хеш-таблица с открытой адресацией. Основные моменты:

1. Хеш-функция – ключи преобразуются в хеш (через __hash__()), который определяет индекс в таблице.
2. Разрешение коллизий – если два ключа имеют одинаковый хеш, используется открытая адресация (поиск следующего свободного слота).
3. Динамическое расширение – при заполнении на 2/3 таблица увеличивается в размере, все элементы перехешируются.
4. Порядок элементов – с Python 3.7 словари сохраняют порядок добавления элементов.

Пример работы хеширования:

d = {}
d['key'] = 'value'  # Хеш 'key' определяет позицию в таблице

Оптимизации:

• Используется псевдослучайное пробирование для поиска свободных слотов
• Маленькие словари (до 5 элементов) используют компактное представление