Множества и словари в Python не работают за O(1)

Сентябрьская заметка Даниэля Лемира за 2026 год берёт убеждение о том, что dict и set в Python работают за константное время, и разрушает его двумя разными способами. Первый - специально подобранная атака, ломающая академическую оценку сложности. Второй вообще не требует противника и куда полезнее на практике.

Намеренные коллизии

Хеш-таблица исходит из предположения, что коллизии случаются редко. Тщательный подбор ключей делает их тотальными:

M = (1 << 61) - 1
values = [i * M for i in range(1, n + 1)]
s = set(values)                       # insertions
count = sum(v in s for v in values)   # checks

В самой заметке не объясняется, почему выбрана именно эта константа. Причина в том, что в 64-битных сборках CPython хеширует целые числа по модулю простого числа Мерсенна 2^61 - 1. В итоге любое число, кратное M, даёт нулевой хеш, и все n ключей попадают в одну и ту же цепочку проб. В отличие от строк, к целым числам не применяется рандомизация хешей, поэтому данный набор коллизий одинаков при каждом запуске.

На Apple M4 Max с Python 3.14 (медиана трёх прогонов) создание множества заняло 4.8 мс при n = 1,000, 15.5 мс при 2,000, 65.5 мс при 4,000, 257 мс при 8,000 и 1,072 мс при 16,000. Каждое удвоение размера примерно учётверяет время. Проверка наличия элементов подчиняется той же кривой (1,066 мс при 16,000), а при 100,000 элементов построение занимает 45 секунд.

Без коллизий, но всё равно не константа

Во втором эксперименте строится dict из миллиона случайных 16-символьных строк в целые числа, после чего каждый ключ запрашивается в перемешанном порядке. Лемир сравнивает его с fastconstmap - неизменяемой мапой для заранее известных ключей, которая опрашивается пакетами через get_many_into. Этот метод записывает значения в принадлежащий вызывающей стороне array("Q"), поэтому под каждый ключ не создаётся отдельный объект Python.

Условия сравнения смещены в пользу dict. Для поиска используются те же строковые объекты, из которых он строился, а строка в Python кеширует свой хеш после первого вычисления. Поэтому dict вообще не тратит время на хеширование, тогда как fastconstmap заново хеширует каждый ключ.

При переходе от наименьшей мапы к наибольшей dict замедляется в девять раз в расчёте на ключ - без смены алгоритма и без каких-либо аномальных коллизий. Объяснение Лемира упирается в память: ключи, их строковые объекты и целочисленные объекты обходятся примерно в 116 байт на запись, поэтому при миллионе записей обращения не попадают в кэш. fastconstmap требует около 9 байт на ключ и остаётся в кэше намного дольше.

Суть

O(1) - это модель хеш-таблицы, а у реального железа есть иерархия памяти, которую эта модель игнорирует. Таблица, помещающаяся в кэш CPU, работает быстро; выпадающая в RAM - медленнее; уходящая на диск - ещё медленнее. Уже по одной этой причине ни одна хеш-таблица не может быть по-настоящему константной по времени. Предупреждение Лемира касается не столько Python, сколько того, как полезная учебная модель превращается в веру, сохраняющуюся вопреки фактам.

Тот же разрыв между моделью и памятью проявляется в golang-maps-swiss-tables, где переписывание map в Golang было в первую очередь оптимизацией локальности данных и лишь во вторую - сменой алгоритма, и где выигрыш в 30% на микротестах сжимается до 1.5%, когда поведение кэша в реальных программах берёт верх. golang-green-tea-gc показывает, насколько легко измерить подобный эффект не на том уровне кэша, а false-sharing-alignment-128 - это многопоточный вариант того же урока: производительность зависит от того, где именно лежат байты.