Как устроен механизм оптимизации словарей Compact Dict, принятый в Python 3.6+? Как разделение словаря на массив хэшей/индексов и массив пар «ключ—значение» сократило потребление памяти и гарантировало сохранение порядка вставки?

Compact Dict хранит разреженную таблицу индексов отдельно от более плотного массива записей. Это уменьшило накладные расходы и позволило обходить элементы в порядке добавления.

Индекс указывает на запись с ключом, значением и необходимой служебной информацией; сами пары не разнесены по всей разреженной таблице. Новые записи добавляются в последовательность, поэтому итерация сохраняет порядок. В CPython 3.6 это было свойством реализации, а с Python 3.7 порядок вставки стал языковой гарантией. Перезапись существующего ключа его не перемещает, удаление с повторным добавлением — перемещает в конец.

Источник: github.com.