Как устроен словарь в Python?

Словарь в Python (dict) — это изменяемая неупорядоченная коллекция элементов, где каждый элемент представляет собой пару "ключ-значение". Ключи должны быть неизменяемыми (строки, числа, кортежи), уникальными, а значения могут быть любого типа. Реализован как хеш-таблица для быстрого доступа к элементам.

Ключевые особенности:

• Хеширование: Ключи хешируются для быстрого поиска. Это позволяет получить доступ к значению по ключу в среднем за O(1).
• Неупорядоченность: До версии Python 3.7 порядок элементов в словаре не гарантировался. Начиная с Python 3.7, словари сохраняют порядок добавления элементов.
• Изменяемость: Можно добавлять, удалять и изменять пары "ключ-значение" после создания словаря.
• Уникальные ключи: Каждый ключ в словаре может встречаться только один раз. При добавлении элемента с существующим ключом старое значение будет перезаписано.

Внутреннее устройство (в Python 3.7+):

Словарь хранит данные в двух структурах:

1. Массив записей: Содержит ссылки на объекты-ключи, хеши ключей и ссылки на объекты-значения. Этот массив плоский и используется для быстрого доступа.
2. Таблица хешей (индексный массив): Содержит индексы в массиве записей. Размер этой таблицы обычно является степенью двойки.

При добавлении пары (ключ, значен