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

Словарь в Python — это хеш-таблица.

1. Основная идея: Хеш-таблица

Словарь реализован как хеш-таблица (hash table). Это структура данных, которая для быстрого доступа к значению использует хеш-функцию ключа.

Принцип работы:

- Когда вы добавляете пару key: value, Python вычисляет хеш ключа (hash(key)).

- На основе этого хеша вычисляется индекс ячейки (слота) в памяти, куда будет помещено значение.

- При поиске значения по ключу (my_dict[key]) Python снова вычисляет хеш ключа, находит нужный слот и мгновенно возвращает значение.

Это обеспечивает среднюю сложность O(1) для операций вставки, удаления и поиска, что очень эффективно.

2. Как разрешаются коллизии (конфликты хешей)

Что если два разных ключа имеют одинаковый хеш? (hash(key1) == hash(key2)). Это называется коллизией.

Современные версии Python (начиная с ~3.6) используют эффективный алгоритм для разрешения коллизий, который сочетает в себе:

- Открытая адресация: Если вычисленный слот уже занят другим ключом, алгоритм ищет следующий свободный слот по определенной формуле ( probing ).

- Компактное представление: Сами пары "ключ-значение" хранятся в отдельном, плотно заполненном массиве. А хеш-таблица на самом деле хранит индексы этого массива.

3. Изменение размера (Resizing)

Что происходит, когда словарь растет и свободных слотов становится мало?

- Python динамически увеличивает размер внутренней хеш-таблицы (например, в 2 раза).

- Происходит rehashing — все существующие пары ключ-значение перераспределяются по новым слотам на основе их хешей.

Это относительно дорогая операция, но она происходит не при каждом добавлении элемента, а только при достижении определенного порога заполненности. Это гарантирует, что средняя производительность остаётся O(1).

4. Порядок элементов

Важное изменение в Python 3.7+: Словари сохраняют порядок добавления элементов.

Это не просто фича, а прямое следствие описанного выше компактного представления. Так как пары ключ-значение хранятся в плотном массиве в порядке добавления, то при итерации словарь просто проходит по этому массиву.

В Python 3.6 это было особенностью реализации, а начиная с Python 3.7 это официальная гарантия языка.

5. Требования к ключам

Ключами словаря могут быть только хешируемые (immutable) объекты.

- Хешируемые: int, float, str, tuple, frozenset.

- Нехешируемые (не могут быть ключами): list, dict, set.

Это требование вытекает из принципа работы: для размещения значения в таблице нужно вычислить стабильный хеш ключа. Если ключ изменяемый (мутабельный), его хеш может измениться, и тогда найти ранее сохраненное значение станет невозможно.

# Работает
my_dict = {('a', 'b'): 1}  # tuple - неизменяемый

# Вызовет ошибку TypeError: unhashable type
my_dict = {['a', 'b']: 1} # list - изменяемый