Как коллизии превращают построение set в Python в квадратичную задачу

Привычное O(1) для set и dict предполагает, что коллизии редки. Если много ключей получают одинаковый хеш, интерпретатору приходится искать свободные ячейки и перебирать кандидатов при проверке вхождения. O(1) здесь полезная модель, а не договор с интерпретатором.

В эксперименте с подобранными целыми числами удвоение размера почти учетверяло время: построение множества из 16 000 элементов заняло 1072 мс, а из 100 000 — 45 секунд. Проверка всех элементов росла так же.

Отдельно автор измерил влияние процессорного кеша: поиск случайных строк в dict замедлялся по мере роста таблицы даже без коллизий. Это другой механизм, поэтому при неожиданной деградации стоит отдельно проверять распределение хешей и размер данных.