Является ли сложность добавления в set всегда константной в Python

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

Знаете ли вы, что за set в CPython стоит хеш-таблица, и различаете ли средний, амортизированный и худший случай. Следом почти всегда просят объяснить, когда добавление деградирует до O(n), и почему список нельзя положить в множество.

Как отвечать

Короткий ответ: нет, не всегда. O(1) это средняя амортизированная оценка, а в худшем случае одна операция add стоит O(n). Дальше разложите, откуда берётся каждая оговорка:

• хеш-таблица с открытой адресацией: add вычисляет hash(x), по нему находит ячейку и, если она занята, пробует следующие по фиксированной схеме пробирования. При хорошем распределении хешей проб одна или две;
• коллизии: если у многих элементов совпадает хеш, каждая вставка перебирает цепочку проб и вызывает __eq__ у кандидатов. Класс, у которого __hash__ возвращает константу, превращает n вставок в O(n²);
• рост таблицы: когда таблица заполняется примерно на 60%, CPython выделяет новую, в несколько раз больше, и переносит все элементы. Такая вставка стоит O(n), но случается редко, поэтому в пересчёте на операцию выходит O(1). Это и есть амортизация;
• цена самого хеша: для int она мгновенная, строка кеширует свой хеш после первого вычисления, а кортеж пересчитывает хеш по всем элементам при каждом вызове.

Хорошо дополнить практикой: хеш строк рандомизируется при каждом запуске интерпретатора (PYTHONHASHSEED), это защита от атаки, где подбирают ключи с одинаковым хешем. Изменяемые list и dict не хешируются вовсе, поэтому в set кладут tuple или frozenset.

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

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

Путают амортизацию с коллизиями. Амортизация сглаживает редкие перестройки таблицы, а от плохих хешей не спасает: там медленной будет каждая операция.

Пишут __hash__, не согласованный с __eq__, или считают хеш от изменяемых полей. Объект, у которого поле поменялось после вставки, в множестве уже не найдётся.