> For the complete documentation index, see [llms.txt](https://kaze.gitbook.io/qa-theory/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kaze.gitbook.io/qa-theory/osnovy-programmirovaniya-na-python/kak-ustroeny-mnozhestva-i-slovari-pod-kapotom.md).

# Как устроены множества и словари под капотом?

В Python **множества (`set`)** и **словари (`dict`)** реализованы на основе **хеш-таблиц** с открытой адресацией. Это обеспечивает быстрый доступ к элементам в среднем за O(1), но под капотом происходят интересные вещи.

***

#### 1. **Хеш-таблица и хеш-функция**

* При добавлении элемента (или пары ключ–значение) Python вызывает функцию `hash()` для получения целого хеша.
* Хеш используется для вычисления индекса в массиве (обычно через побитовые операции).
* Если два объекта имеют одинаковый хеш (*коллизия*), Python ищет следующую свободную ячейку (метод открытой адресации).

***

#### 2. **Открытая адресация**

* Вместо хранения "цепочек" элементов в одной ячейке, Python просто ищет другое место в массиве по определённой схеме (linear probing).
* Это быстрее для CPU, так как данные лежат в памяти компактно.

***

#### 3. **Динамическое расширение**

* При заполнении таблицы примерно на 2/3 Python автоматически увеличивает размер массива в 2 раза.
* При расширении происходит **рехеширование** — перерасчёт позиций для всех элементов, чтобы сохранить эффективность поиска.

***

#### 4. **Словари (`dict`)**

* Хранят **ключи** и **значения** в двух разных массивах:
  * Один массив — "ключи и метаданные" (ключ + хеш).
  * Второй массив — "значения".
* Порядок вставки элементов сохраняется (с Python 3.7 — официально гарантировано).
* Доступ к значению: вычисляется хеш ключа → ищется индекс → по индексу берётся значение.

***

#### 5. **Множества (`set`)**

* Очень похожи на `dict`, но без массива значений.
* По сути, это словарь, где все значения — фиктивные (`True` или специальный объект-заглушка).

***

#### 6. **Особенности**

* **Ключи и элементы должны быть хешируемыми** — то есть иметь неизменяемый `__hash__()` и корректный `__eq__()`.
* Хеш-таблицы чувствительны к качеству хеш-функции: плохой хеш → больше коллизий → замедление.
* Памяти словари и множества используют больше, чем список, из-за пустых ячеек и метаданных.
* Удалённые элементы физически остаются в таблице как "маркеры пустоты", чтобы не ломать поиск.