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