Как устроено множество (set) в Python

Что проверяют

Понимаете ли вы, почему проверка x in s по множеству быстрее, чем по списку, и на чём этот выигрыш держится. Вопрос почти всегда переходит в хеш-таблицы: следом спрашивают, что можно положить в множество, почему нельзя список и что случится при коллизиях.

Как отвечать

• устройство: хеш-таблица с открытой адресацией. Коллизии разрешаются пробированием других слотов, а не списками-цепочками. У маленького множества есть встроенный массив на 8 слотов, без отдельного выделения памяти;
• рост: когда заполнение переваливает примерно за три пятых таблицы, она перестраивается на больший размер и все элементы перехешируются. Поэтому отдельная вставка иногда стоит дорого, а средняя амортизированная остаётся O(1);
• требование к элементам: объект должен быть хешируемым, то есть иметь __hash__ и согласованный с ним __eq__. list и dict не подходят, tuple из хешируемых и frozenset подходят;
• операции: add, discard (молча), remove (с KeyError), проверка вхождения в среднем O(1). Пересечение & идёт по меньшему множеству, объединение линейно по сумме размеров;
• порядок: множество не сохраняет порядок вставки, в отличие от dict начиная с 3.7. Обход определяется хешами и историей вставок, а для строк ещё и рандомизацией хеша при старте процесса, которой управляет PYTHONHASHSEED.

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

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

Где спотыкаются

Говорят «реализовано методом цепочек», путая CPython с учебной картинкой хеш-таблицы. В set открытая адресация.

Отвечают «O(1) всегда» и замолкают. Интервьюер ждёт оговорок про коллизии и про перестройку при росте.

Путают хешируемость с неизменяемостью. Свой класс без __eq__ кладётся в множество спокойно, по идентичности, а датакласс со сравнением, но без frozen=True, уже нет: Python обнуляет ему __hash__.