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

В 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__().

• Хеш-таблицы чувствительны к качеству хеш-функции: плохой хеш → больше коллизий → замедление.

• Памяти словари и множества используют больше, чем список, из-за пустых ячеек и метаданных.

• Удалённые элементы физически остаются в таблице как "маркеры пустоты", чтобы не ломать поиск.