Как устроен словарь (dict) в Python? Какая структура данных лежит в его основе?

Question

dict в CPython реализован на основе хеш‑таблицы с открытой адресацией. Ключи хешируются, индекс указывает на слот в массиве записей, где хранится пара (хеш, ключ, значение). При росте таблицы происходит расширение и перехеширование.

YeaHub · Accepted Answer

Хеш‑таблица: массив слотов фиксированного размера, расширяемый по порогу заполненности (≈2/3).Открытая адресациия: при коллизии применяется алгоритм perturbation для поиска следующего индекса.Каждый слот хранит:Поле с хешем, ключ и значение.Расширение:При достижении заполненности таблица удваивается, и все пары перехешируются.Сохранение порядка:С Python 3.7 порядок вставки поддерживается встроенно.