Python Set — внутреннее устройство

Основа: хеш-таблица

Структура — общая для set и frozenset

Set в Python реализован как хеш-таблица с открытой адресацией. Это означает, что все элементы хранятся в одном непрерывном массиве фиксированного размера (в памяти), а не в связном списке или дереве.

Каждая ячейка (slot) массива может находиться в одном из трёх состояний: - Пустая — никогда не использовалась - Занятая — содержит элемент - Удалённая (dummy) — элемент был, но его удалили (tombstone)

Структура хранения

Внутри каждая занятая ячейка хранит два поля: - hash — кешированное значение хеша элемента (целое число, Py_hash_t) - key — указатель на сам объект Python

Кеширование хеша критично: при операциях объединения, пересечения и поиска не нужно пересчитывать хеш заново — он уже хранится рядом с элементом.

Размер и load factor

Начальный размер таблицы — 8 слотов.

Python поддерживает коэффициент заполнения (load factor) ≤ 2/3 (т.е. не более ~66% слотов занято). Как только этот порог превышается — происходит resize.

При resize таблица перестраивается в новый массив размером: - ×4 — если сет небольшой - ×2 — если сет уже большой

Размер таблицы всегда является степенью двойки — это позволяет заменить дорогую операцию деления на быстрый битовый AND при вычислении индекса слота.

Механизм поиска слота (probing)

Вычисление начального индекса

Индекс первого кандидата вычисляется как hash & (size - 1) — битовое AND с маской, что эквивалентно hash % size, но значительно быстрее.

Разрешение коллизий — perturbation probing

Python не использует линейное или квадратичное зондирование в чистом виде. Вместо этого применяется алгоритм perturbation (возмущение):

На каждом шаге зондирования новый индекс вычисляется по формуле:

i = (i * 5 + 1 + perturb) & mask
perturb >>= 5

Переменная perturb инициализируется исходным значением хеша и постепенно сдвигается вправо на 5 бит на каждой итерации. Это гарантирует, что в конечном итоге задействуются все биты хеша, а не только младшие — что даёт гораздо лучшее распределение при коллизиях.

Компактное хранение (начиная с CPython 3.6+, для dict; для set — своя история)

В отличие от dict, который в 3.6 получил компактное разделённое хранение (индексный массив + плотный массив записей), set по-прежнему использует классическую единую хеш-таблицу — разреженный массив, где пустые слоты занимают память. Это осознанный компромисс: set оптимизирован под скорость lookup и операции над множествами, а не под порядок вставки.

Удаление элементов и dummy-слоты

При удалении элемент не обнуляется полностью — слот помечается как dummy (tombstone). Это необходимо для корректности поиска: если просто очистить слот, цепочка зондирования оборвётся, и элементы, добавленные после коллизии, станут недостижимыми.

Dummy-слоты учитываются при resize: таблица перестраивается в том числе когда накапливается слишком много tombstone-ов — они занимают место, но не несут данных.

Операции над множествами

Операции union, intersection, difference реализованы на уровне C и используют внутренние структуры напрямую, без Python-уровня итерации:

Операция Стратегия
\| union итерация по меньшему, вставка в копию большего
& intersection итерация по меньшему, проверка membership в большем
- difference итерация по левому, исключение найденных в правом
^ symmetric diff объединение двух difference

Выбор "итерировать по меньшему" — намеренная оптимизация: меньше итераций, меньше lookup-ов.

Хешируемость элементов

Set требует, чтобы элементы были хешируемыми (__hash__) и сравнимыми (__eq__). При коллизии хешей Python сначала сравнивает сами хеши (быстро, через кешированное значение), и только при совпадении вызывает __eq__ — это минимизирует дорогие объектные сравнения.

Память

Оценка потребления памяти — sys.getsizeof возвращает размер только самой хеш-таблицы, без учёта объектов-элементов. Из-за разреженности хеш-таблица занимает больше памяти, чем аналогичный список — это прямая плата за O(1) lookup.

Пустой set:       ~200 байт (8 слотов)
После resize:     размер удваивается/учетверяется ступенчато

Итого: ключевые свойства

Структура (PySetObject — общая для set и frozenset)

┌──────────────────────────────────────────┐
│ ob_refcnt           (8 байт)             │
│ ob_type → frozenset (8 байт)             │
├──────────────────────────────────────────┤
│ fill        (8 байт)  ← занятые + dummy  │
│ used        (8 байт)  ← живые элементы   │
│ mask        (8 байт)  ← capacity - 1     │
│ table*      (8 байт)  ← указатель на HT  │
│ hash        (8 байт)  ← кешированный хеш │
│ finger      (8 байт)  ← итератор-курсор  │
│ smalltable  (216 байт)← инлайн-буфер     │
│             (8 slotentries × 27 байт)    │
└──────────────────────────────────────────┘

Каждый слот (setentry):

┌──────────────────┬───────────────────┐
│ hash (8 байт)    │ key* (8 байт)     │
└──────────────────┴───────────────────┘

frozenset vs set

set frozenset
Структура памяти идентична идентична
Мутация разрешена запрещена (проверка типа)
Хешируем нет да (кешируется в поле hash)
Может быть ключом dict нет да

hash поле в PySetObject — прояснение

Как на самом деле устроено

В CPython исходниках (Objects/setobject.c) одна структура PySetObject используется для обоих типов:

typedef struct {
    ob_refcnt
    ob_type
    fill
    used
    mask
    table*
    hash        ← поле ЕСТЬ в структуре у обоих
    finger
    smalltable[8]
    weakreflist
} PySetObject;

Поле hash физически присутствует в памяти и для set, и для frozenset — потому что структура одна.

Разница в поведении, а не в структуре

set frozenset
Поле hash в памяти есть есть
Начальное значение -1 (sentinel) -1
Вычисляется когда никогда при первом вызове hash()
Кешируется нет смысла да, записывается в поле
__hash__ метод None (явно зануляет) вычисляет и кеширует

Поле hash есть в обоих объектах на уровне C-структуры, но используется только frozenset. У set оно всегда остаётся -1 и никогда не задействуется, потому что __hash__ = None на уровне типа.