Каков алгоритм оптимизации Compact Dict (PEP 468) и как он гарантирует порядок вставки?

Compact dict разделяет разреженную таблицу индексов и плотное хранение записей, что экономит место и упрощает обход в порядке вставки. PEP 468 посвящён порядку **kwargs, а не полному алгоритму dict.

Новые записи добавляются в упорядоченную область, а хеш-таблица указывает, где искать соответствующую запись. Замена значения существующего ключа не переносит его в конец; удаление и повторная вставка создают новую позицию. В современных Python порядок вставки является языковой гарантией, тогда как конкретная раскладка — деталь CPython. Не нужно выводить правила языка только из одного исторического PEP об именованных аргументах.

Источник: peps.python.org, mail.python.org.