**Словарь в 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 - изменяемый ``` ###