В Python порядок вставки в словаре сохраняется благодаря реализации словарей на основе хеш-таблиц начиная с версии 3.7. Это было официально задокументировано в версии 3.7, хотя фактически поведение наблюдалось уже в версии 3.6.
В более ранних версиях Python (до 3.6 включительно) словари не гарантировали порядок элементов.
С тех пор, как словари были изменены для сохранения порядка вставки, при добавлении новых элементов в словарь они сохраняют порядок, в котором были добавлены. Эта особенность была достигнута благодаря изменениям в реализации хеш-таблицы, которая теперь хранит дополнительную информацию для поддержания порядка вставки.
Чтобы сохранить порядок вставки в словарях, в Python была внесена ключевая модификация в структуру данных, лежащую в основе реализации хеш-таблицы. Вот основные изменения:
- Введение массива индексов: хеш-таблица теперь использует дополнительный массив (array of indices), который указывает на другой массив, содержащий фактические элементы (ключи и значения). Этот массив индексов поддерживает порядок вставки.
- Порядок в массиве элементов: второй массив, который хранит ключи и значения (entries), представляет собой динамический массив, где элементы расположены в порядке их вставки. Когда новый элемент добавляется, он добавляется в конец этого массива.
- Синхронизация массивов: массив индексов обновляется таким образом, чтобы он указывал на правильные позиции в массиве элементов. Это обеспечивает, что порядок элементов в массиве индексов соответствует порядку вставки.
- Перехеширование (Rehashing): когда происходит перехеширование (например, при увеличении размера хеш-таблицы), порядок вставки сохраняется, так как массив индексов и массив элементов обновляются синхронно.
- Удаление элементов: когда элемент удаляется, его место в массиве элементов помечается как "удаленный", но порядок остальных элементов остается неизменным. Это позволяет сохранять порядок оставшихся элементов.
Эти изменения были разработаны, чтобы минимизировать накладные расходы и поддерживать высокую производительность операций словаря (вставка, удаление, поиск) при одновременном сохранении порядка вставки.
Примерно так это работает на уровне структуры данных:
Это абстрактный пример. Реальная реализация в CPython намного более оптимизирована и сложна.
Если вы интересуетесь программированием, то напоминаю о нашем курсе по основам программирования Python [START].
В нем много анимации, примеров и разборов домашних заданий. Присоединяйтесь! Ссылка: