Словари Python изнутри: хеш-таблица CPython

Что на самом деле происходит внутри d[key]

Словарь Python не хранит пары "ключ-значение" в списке, где для поиска нужно проверить каждый элемент. Вместо этого он использует хеш-таблицу: массив ячеек, где место для каждого ключа вычисляется заранее, по числу.

Вот это по шагам, без формул из исходного кода C.

Шаг 1: у каждого ключа есть число

Когда вы пишете d["python"] = 3, первое, что делает Python, — превращает "python" в число с помощью функции hash(). Это число — как индекс в гардеробе: оно не хранит сам ключ, но говорит, куда его положить.

Для целых чисел всё просто: hash(5) — это почти всегда просто 5. Для строк — сложнее: Python специально делает так, чтобы хеш одной и той же строки был разным при каждом новом запуске программы. Это защита: если бы хеш строки всегда был предсказуем, кто-то мог бы специально подобрать миллион ключей с одинаковым хешем и замедлить программу до предела. Ниже можно попробовать оба варианта на реальных числах (для строк — на упрощённом примере, настоящий алгоритм Python нельзя воспроизвести между запусками — в этом и смысл).

Шаг 2: число превращается в ячейку

У таблицы есть конкретное число ячеек — всегда степень двойки (8, 16, 32...). Чтобы превратить большое число-хеш в номер одной из этих ячеек, Python берёт несколько последних битов хеша. Это очень быстрая операция — быстрее, чем деление с остатком, хотя по смыслу делает то же самое.

Шаг 3: а если ячейка занята?

Два разных ключа время от времени попадают в одну и ту же ячейку — это называется коллизией. Python не останавливается на первой попавшейся свободной ячейке подряд (это работало бы плохо), а прыгает по таблице в специальном порядке, который использует части хеша, ещё не задействованные на шаге 2. В итоге ключ довольно быстро находит свободное место, даже если таблица уже неплохо заполнена.

Шаг 4: таблица растёт сама

Если таблицу заполнить почти полностью, поиск в ней замедляется — ячеек-кандидатов на "почти пусто" уже почти не остаётся. Поэтому Python следит за заполненностью: как только таблица заполнена примерно на две трети, он создаёт новую, обычно вдвое больше, и переносит туда все ключи заново. Именно поэтому при добавлении элементов в словарь размер его внутренней таблицы время от времени скачком увеличивается — это нормально и относится к обычной работе словаря, а не к ошибке или "утечке памяти".

Интерактивная визуализация

Ниже — тот же гардероб, только по шагам. Слева-сверху доска с номерками, снизу — вешалка с записями. Нажмите «Воспр.» и посмотрите на два момента: на шаге 3 номерок оказывается занят и ключу приходится искать другой, а на шаге 6 доску целиком меняют на большую — но вешалку при этом не трогают, записи остаются в том же порядке.

Ключи здесь — обычные целые числа, и это не случайность: у целых hash(n) равен самому n, поэтому любой номер слота можно проверить в своём Python. У строк хеш при каждом запуске новый, так что такие числа проверить было бы нельзя.

Что стоит запомнить

Три вещи про словарь Python, на которые можно полагаться в реальном коде: порядок ключей сохраняется таким, каким вы их добавляли (это гарантия языка с версии 3.7); поиск, вставка и удаление работают в среднем очень быстро, почти не завися от размера словаря; и — конкретные числа вроде "заполнение на две трети" или "новый размер таблицы" — это внутренняя механика CPython, которая теоретически может отличаться в другой реализации Python. Если хочется увидеть точные формулы и код, на которых всё это основано, — в статье выше есть версия "Подробно".

Зачем это знать?

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

Практическое следствие: у CPython не одна реализация поиска по словарю, а несколько специализаций, и переключение между ними видно в цифрах. Самое наглядное доказательство — оптимизация из 3.11: если все ключи словаря строковые, интерпретатор перестаёт хранить в таблице их хеши, и sys.getsizeof(dict.fromkeys("abcdefg")) падает с 352 до 272 байт. Добавьте в такой словарь один нестроковый ключ — и таблица переходит в общий режим. Ни один из этих переходов не виден в исходном коде на Python: чтобы объяснить, почему тот же словарь вдруг стал занимать заметно больше памяти, надо знать про раскладку.

Модель в голове

Представьте гардероб. Разреженный массив dk_indices — это доска с номерками на стене: почти пустая, расширять её дёшево. Плотный массив dk_entries — это вешалка с самими пальто, развешанными строго в порядке поступления. Хеш говорит, какой номерок читать; номерок говорит, куда идти по вешалке.

Расширение таблицы перерисовывает доску и никогда не перевешивает пальто. Именно поэтому порядок обхода выживает при расширении — и именно поэтому это свойство изначально было побочным эффектом раскладки, а не обещанием языка:

Дословно: «сохранение порядка в этой новой реализации считается деталью реализации, и полагаться на неё не следует». Так авторы CPython описали побочный эффект компактного словаря в 3.6 — за один релиз до того, как это же поведение стало официальной частью языка.

Устройство: две таблицы вместо одной

«Разреженный» и «плотный» — это не эпитеты

Два слова, без которых дальше ничего не сойдётся.

Разреженный массив — тот, в котором свободных ячеек намеренно больше, чем нужно. Хеш-таблице с открытой адресацией это не роскошь, а условие работы: ключ ищется по формуле «взять хеш, оставить от него младшие биты, посмотреть в слот с этим номером», и если свободных слотов не останется, поиск свободного места и разрешение коллизий выродятся в перебор всей таблицы. Поэтому CPython не даёт таблице заполниться больше чем на две трети (USABLE_FRACTION) — пока удалений не было, минимум треть слотов пустует — это не потери, а рабочий запас. Что делают с этим запасом удаления, разобрано ниже, в разделе «Так растёт ли dk_indices бесконечно?».

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

Компактный словарь состоит из обоих сразу — и весь фокус в том, какой из них сделан разреженным.

Зачем вообще нужен dk_indices

До Python 3.6 массив был один. Вот та самая структура из CPython 3.5:

struct _dictkeysobject {
    Py_ssize_t dk_refcnt;
    Py_ssize_t dk_size;
    dict_lookup_func dk_lookup;
    Py_ssize_t dk_usable;
    PyDictKeyEntry dk_entries[1];
};

dk_entries здесь — и есть хеш-таблица: слот номер i — это dk_entries[i], целая запись из хеша, ключа и значения. То есть разреженным был массив 24-байтовых записей, и обязательная пустая треть стоила по 24 байта за слот.

Идея компактного словаря (письмо Реймонда Хеттингера в python-dev, декабрь 2012) в одной фразе: пусть разреженным будет дешёвый массив, а дорогой — плотным. Разреженность нужна самой хеш-таблице, а не записям, поэтому хеш-таблицу вынесли в отдельный массив маленьких целых чисел, и вся «воздушная подушка» стала стоить по одному байту за слот вместо двадцати четырёх.

Считается это прямо на пальцах. Таблица на 8 слотов, в ней 5 живых ключей:

Экономия здесь — треть. Но она не постоянная, и это стоит знать до того, как переносить расчёт на большие таблицы: слот dk_indices шире одного байта не всегда. В него надо уместить номер записи, поэтому ширина растёт ступенями — 1 байт до dk_size 255, 2 до 65 535, дальше 4 и 8 (запуск печатает эту лестницу и сверяет формулу с sys.getsizeof).

Отсюда на таблице в 65 536 слотов (43 690 записей) получается 1 572 864 байта против 1 310 704 — экономия уже 16,7 %, а не треть. Заявленные в «Что нового в Python 3.6» «на 20–25 % меньше памяти» приходятся на таблицы среднего размера: на dk_size = 256 выходит ровно 25,3 %. Чем шире индекс, тем меньше выигрыш.

А теперь ответ на вопрос «зачем эта прослойка вообще»: без неё поиск ключа стал бы линейным. dk_entries заполняется в порядке вставки, а не по хешу, — по нему нельзя вычислить, где лежит ключ, можно только перебрать все записи подряд. dk_indices — это и есть хеш-таблица: адрес слота получается из хеша одной операцией hash & mask, и в слоте сразу лежит номер нужной записи. Одно обращение вместо перебора, O(1) вместо O(n).

Порядок вставки при этом получился побочным эффектом: раз записи складываются в плотный массив подряд, обход этого массива и выдаёт ключи в порядке добавления. Никакой отдельной структуры для порядка в словаре нет.

Две структуры рядом

dk_indices — разреженный массив, тот самый, размер которого равен dk_size и всегда является степенью двойки. В слоте лежит не ключ и не значение, а маленькое целое число — индекс записи во втором массиве. Или одно из служебных значений: DKIX_EMPTY (−1) для пустого слота и DKIX_DUMMY (−2) для слота, из которого ключ удалили. Ширина одного слота подобрана под размер таблицы — из комментария к dk_indices в pycore_dict.h:

/* The size in bytes of an indice depends on dk_size:
   - 1 byte if dk_size <= 0xff (char*)
   - 2 bytes if dk_size <= 0xffff (int16_t*)
   - 4 bytes if dk_size <= 0xffffffff (int32_t*)
   - 8 bytes otherwise (int64_t*) */
char dk_indices[];

Вот почему «расширять доску дёшево»: словарь из восьми слотов тратит на dk_indices 8 байт, а не восемь полноценных записей. Даже при таблице на 32 тысячи слотов это два байта на слот, и только с 65 536 — четыре.

dk_entries — плотный массив самих записей, в порядке вставки. И вот что в записи лежит на самом деле:

typedef struct {
    /* Cached hash code of me_key. */
    Py_hash_t me_hash;
    PyObject *me_key;
    PyObject *me_value;
} PyDictKeyEntry;

Три поля по машинному слову — на 64-битной сборке ровно 24 байта на запись. Ключ и значение — это указатели: сами объекты живут где-то ещё в куче, словарь хранит только адреса и держит на них ссылки. А me_hash — кеш: хеш ключа считается один раз при вставке и сохраняется рядом, чтобы не вызывать hash() заново при каждом сравнении в цепочке проб и при каждом расширении таблицы.

Как эти массивы заполняются

Вставка нового ключа — это всего четыре события, и порядок у них не тот, который кажется естественным. Вот тело insert_combined_dict из dictobject.c, сокращённое до записей в память:

Py_ssize_t hashpos = find_empty_slot(mp->ma_keys, hash);
dictkeys_set_index(mp->ma_keys, hashpos, mp->ma_keys->dk_nentries);
 
if (DK_IS_UNICODE(mp->ma_keys)) {
    PyDictUnicodeEntry *ep = &DK_UNICODE_ENTRIES(mp->ma_keys)[mp->ma_keys->dk_nentries];
    STORE_KEY(ep, key);
    STORE_VALUE(ep, value);
}
else {
    PyDictKeyEntry *ep = &DK_ENTRIES(mp->ma_keys)[mp->ma_keys->dk_nentries];
    STORE_KEY(ep, key);
    STORE_VALUE(ep, value);
    STORE_HASH(ep, hash);
}
STORE_KEYS_USABLE(mp->ma_keys, mp->ma_keys->dk_usable - 1);
STORE_KEYS_NENTRIES(mp->ma_keys, mp->ma_keys->dk_nentries + 1);

Читается это так:

1. find_empty_slot ищет свободный слот в dk_indices — по хешу и, при коллизии, по последовательности проб (о ней ниже). Ключ и значение в этом поиске не участвуют вообще: слот выбирают биты хеша.
2. dictkeys_set_index пишет в найденный слот текущее значение dk_nentries — номер записи, которой ещё нет. Индекс в доску попадает раньше, чем создана сама запись.
3. Только теперь заполняется запись в dk_entries по индексу dk_nentries: два указателя, а в общем режиме ещё и хеш.
4. dk_usable уменьшается на единицу, dk_nentries — увеличивается. Первый счётчик — это остаток до расширения (USABLE_FRACTION), второй — граница заполненной части плотного массива.

Ничего больше при вставке в память не пишется. Ни ключ, ни значение никуда не копируются: STORE_KEY и STORE_VALUE сохраняют адреса уже существующих объектов и увеличивают их счётчики ссылок.

Ниже — те же четыре шага в интерактивном виде: кнопка «Воспр.» проигрывает вставку по фазам, переключатель вверху меняет раскладку записи с общей на строковую.

Второй вид записи: когда все ключи — строки

У записи есть и вторая форма. Если все ключи таблицы строковые, CPython использует другую структуру:

typedef struct {
    PyObject *me_key;   /* The key must be Unicode and have hash. */
    PyObject *me_value;
} PyDictUnicodeEntry;

Поля хеша здесь нет вообще — 16 байт вместо 24. Хеш при этом не теряется: у строкового объекта он уже закеширован внутри самого объекта, так что держать вторую копию в таблице незачем. Какой из двух вариантов используется, записано в поле dk_kind (DICT_KEYS_GENERAL или DICT_KEYS_UNICODE; есть и третий, DICT_KEYS_SPLIT, — о нём ниже). Это и есть механизм экономии, о которой говорит «Что нового в Python 3.11»: sys.getsizeof(dict.fromkeys("abcdefg")) — 272 байта вместо прежних 352. Переключиться между режимами можно в визуализации выше.

Именно порядок в dk_entries и даёт словарю то, что с Python 3.7 стало официальной гарантией языка, а не деталью реализации: обход dict идёт в порядке вставки ключей.

Есть и третий вариант — split table (PEP 412, "key-sharing dictionary"): если у множества объектов одного класса одинаковый набор строковых атрибутов, они могут разделять один и тот же dk_indices/ключевую часть, а значения хранить каждый в своём ma_values. Это оптимизация для __dict__ экземпляров, а не для словарей общего назначения — в основном тексте статьи речь про обычный, "combined" словарь.

Шаг 1: от ключа к числу

Первое, что происходит при d[key] = value или d[key], — вызов hash(key). Дальше многое зависит от типа ключа:

• Для int — хеш почти всегда совпадает со значением: hash(n) == n для большинства целых (с редукцией по модулю простого числа Мерсенна 2⁶¹−1 на 64-битных сборках — см. sys.hash_info). Исключение: -1. CPython резервирует -1 как код ошибки для C-функций, возвращающих Py_hash_t, поэтому несколько его хеш-функций (для bytes, float, указателей — см. Python/pyhash.c) явно подменяют вычисленное -1 на -2. Для int действует то же соглашение: hash(-1) == -2.
• Для str (и bytes) — SipHash с seed, случайным для каждого запуска процесса (PEP 456, PYTHONHASHSEED). Какой именно вариант SipHash собран, показывает sys.hash_info.algorithm. Это осознанное решение о безопасности: до PEP 456 предсказуемый хеш строк давал классическую DoS-атаку «hash flooding» через специально подобранные ключи. Практическое следствие: hash("cpython") в двух разных запусках python3 — это, как правило, два разных числа.

Ниже — тот же самый первый шаг, key → hash(key), в интерактивном виде. Для int показано настоящее значение hash(); для str — намеренно упрощённая демонстрационная функция (не SipHash), потому что настоящий хеш строки невоспроизводим между запусками по построению.

Шаг 2: от числа к слоту

Хеш — это произвольное целое число, а таблица — массив из dk_size слотов, где dk_size всегда степень двойки. Начальный кандидат на слот — самая дешёвая операция, которая тут вообще возможна:

mask = dk_size - 1;
i = hash & mask;

& mask вместо % dk_size — обычный трюк для степеней двойки: младшие биты hash и есть остаток от деления, без деления как такового.

Коллизии: последовательность проб CPython

Два разных ключа почти неизбежно дадут одинаковый i рано или поздно. Здесь у CPython не линейное пробирование и не что-то на основе двойного хеширования из учебника — своя рекуррентная формула; вот она в виде цикла, по комментарию из dictobject.c:

perturb = hash;
i = hash & mask;
 
while (slot_at(i)->occupied) {
    perturb >>= PERTURB_SHIFT;      /* PERTURB_SHIFT == 5 */
    i = (i*5 + perturb + 1) & mask;
}

Идея: обычное линейное пробирование (i = i + 1) слишком регулярно — при частичном заполнении таблицы оно даёт длинные цепочки коллизий, коррелирующие с самим mask. Добавка perturb, которая на каждом шаге сдвигается вправо на 5 бит, постепенно "подмешивает" в последовательность проб старшие биты исходного хеша — те самые биты, которые & mask в чистом виде вообще не использует. В сумме получается псевдослучайный, но полностью детерминированный обход всех dk_size слотов.

Проверьте формулу сами — таблица ниже пересчитывает реальную последовательность проб CPython для введённого hash и отмеченных как занятые слотов:

Рост таблицы: когда и во сколько раз

Хеш-таблица, заполненная под завязку, вырождается в линейный поиск — CPython не доводит до этого и держит запас. Три числа из dictobject.c полностью определяют, когда и как таблица растёт:

#define PyDict_MINSIZE 8
#define USABLE_FRACTION(n) (((n) << 1)/3)   /* resize при заполнении на 2/3 */
#define GROWTH_RATE(d) ((d)->ma_used*3)

Первая вставка выделяет таблицу на dk_size = 8, и dk_usable = USABLE_FRACTION(8) = 5 — ровно то, что описывает комментарий в исходнике: "8 allows dicts with no more than 5 active entries". Каждая успешная вставка уменьшает dk_usable на 1; когда он должен был бы стать отрицательным, перед вставкой запускается resize: новый минимальный размер — GROWTH_RATE(mp), то есть ma_used * 3, а фактический новый dk_size — ближайшая степень двойки, не меньшая этого значения. Если удалений не было, ma_used * 3 почти всегда попадает в диапазон "следующая степень двойки после удвоения", отсюда и комментарий в исходнике: "dicts double in size when growing without deletions".

Интерактивная визуализация

Пройдите по шагам шесть вставок в таблицу из 8 слотов. Обратите внимание на пробирование при коллизии на шаге 3 и на расширение на шаге 6 — массив записей копируется дословно, ни одна запись не меняет позицию.

Ключи здесь целые, а не строковые, и это сделано намеренно: hash(n) == n, поэтому каждый номер слота ниже можно проверить в своём интерпретаторе, а хеш строки невоспроизводим между запусками (см. шаг 1).

Тот же словарь целиком, если хочется убедиться самому:

import sys
 
d = {}
for k in (3, 6, 11, 1, 7):
    d[k] = "…"
print(sys.getsizeof(d))      # таблица ещё на 8 слотов
 
d[2] = "…"                   # шестая вставка пересекает порог 2/3
print(sys.getsizeof(d))      # выросла: dk_indices теперь на 16 слотов
print(list(d))               # [3, 6, 11, 1, 7, 2] — порядок вставки уцелел

Обновление и удаление: три разных пути

Про вставку нового ключа сказано всё, но d[k] = v — это ещё и обновление уже существующего ключа, а del d[k] устроен совсем иначе. Три пути ведут себя по-разному, и разница видна невооружённым глазом.

Обновление: ничего не двигается

Если поиск нашёл ключ, insertdict до создания записи вообще не доходит:

if (old_value != value) {
    uint64_t new_version = _PyDict_NotifyEvent(
            interp, PyDict_EVENT_MODIFIED, mp, key, value);
    assert(old_value != NULL);
    assert(!_PyDict_HasSplitTable(mp));
    if (DK_IS_UNICODE(mp->ma_keys)) {
        PyDictUnicodeEntry *ep = &DK_UNICODE_ENTRIES(mp->ma_keys)[ix];
        STORE_VALUE(ep, value);
    }
    else {
        PyDictKeyEntry *ep = &DK_ENTRIES(mp->ma_keys)[ix];
        STORE_VALUE(ep, value);
    }
    mp->ma_version_tag = new_version;
}
Py_XDECREF(old_value);

Переписывается одно поле — me_value, а старое значение получает Py_DECREF. Ни dk_indices, ни me_key, ни me_hash не трогаются, dk_nentries и dk_usable не меняются. Отсюда практическое следствие: присваивание существующему ключу не меняет порядок обхода. Ключ остаётся на своей позиции в dk_entries, а значит и в итерации.

Удаление: надгробие вместо записи

delitem_common трогает обе структуры. Ниже — её тело, сокращённое до записей в память:

Py_ssize_t hashpos = lookdict_index(mp->ma_keys, hash, ix);
STORE_USED(mp, mp->ma_used - 1);
mp->ma_keys->dk_version = 0;
dictkeys_set_index(mp->ma_keys, hashpos, DKIX_DUMMY);
 
PyDictKeyEntry *ep = &DK_ENTRIES(mp->ma_keys)[ix];
old_key = ep->me_key;
STORE_KEY(ep, NULL);
STORE_VALUE(ep, NULL);
STORE_HASH(ep, 0);

В слоте вместо индекса появляется DKIX_DUMMY (−2) — «надгробие». Пометить слот как пустой нельзя, и в исходнике прямо написано почему:

Если бы слот стал DKIX_EMPTY, поиск ключа, который когда-то из-за коллизии перепрыгнул через этот слот дальше по цепочке проб, останавливался бы на нём — и ключ, лежащий в словаре, перестал бы находиться.

Запись в dk_entries при этом обнуляется на месте: на её позиции остаётся дыра. И — самое важное для следующего раздела — счётчик свободной ёмкости не восстанавливается. Комментарий в исходнике объясняет и это: раз в dk_indices остаются надгробия, увеличить dk_usable нельзя, хотя живых ключей стало меньше.

Отдельно стоит запомнить последний кадр: удалить ключ и вставить его обратно — не то же самое, что обновить значение. Слот в dk_indices переиспользуется (find_empty_slot останавливается и на пустом слоте, и на надгробии), но запись создаётся новая, в хвосте, — и ключ уезжает в конец порядка обхода.

Так растёт ли dk_indices бесконечно?

Из предыдущего раздела складывается тревожная картина: каждая вставка тратит ёмкость, каждое удаление оставляет мусор и ничего не возвращает. Если долго вставлять и удалять, таблица должна пухнуть без предела.

Не должна — и вот почему. Ёмкость dk_usable действительно утекает, но когда она доходит до нуля, очередная вставка запускает пересборку, а размер новой таблицы считается от числа живых ключей — GROWTH_RATE(mp) — это ma_used * 3, и ma_used учитывает только живые. Мёртвые записи и надгробия в этот расчёт не входят и при копировании просто исчезают. Поэтому размер таблицы определяется тем, сколько ключей в словаре сейчас, а не тем, сколько операций над ним сделали.

Из этого следуют три вещи, каждую из которых легко проверить самому.

Первое: при постоянном цикле «вставил — удалил» словарь не растёт. Миллион пар вставка/удаление при сотне живых ключей меняет размер ровно один раз, в самом начале:

import sys
 
d = {i: i for i in range(100)}
prev, changes = sys.getsizeof(d), []
for i in range(1_000_000):
    d[("k", i)] = i
    del d[("k", i)]
    if sys.getsizeof(d) != prev:
        changes.append((i, prev, sys.getsizeof(d)))
        prev = sys.getsizeof(d)
 
print(len(d), changes)   # 100 [(70, 4688, 9304)]
print(sys.getsizeof(d))  # 9304 — и дальше константа

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

import sys
 
d = {i: i for i in range(1000)}
for i in range(990):
    del d[i]
print(sys.getsizeof(d))      # 36952 — удаления не вернули ничего
 
for n in range(1, 400):      # цикл вставка/удаление: живых по-прежнему 10
    d[("n", n)] = n
    del d[("n", n)]
print(sys.getsizeof(d))      # 632

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

import sys
 
d = {i: i for i in range(1000)}
for i in range(1000):
    del d[i]
print(len(d), sys.getsizeof(d))   # 0 36952 — пусто, но память занята
 
d.clear()
print(sys.getsizeof(d))           # 64 — вот теперь освободилась

Практический вывод ровно один: если из большого словаря удалили почти всё и дальше он будет жить долго, а вставок в него не предвидится — пересоберите его: d = dict(d). Если оставшиеся ключи уже не нужны, таблицу целиком освободит d.clear(). Во всех остальных случаях механизм сам себя чистит.

Кадры на Рис. 3 и Рис. 4 — не модель, а замер: состояние реального словаря, прочитанное прямо из памяти интерпретатора. Скрипт ниже воспроизводит его целиком (ctypes тут читает приватные структуры CPython — это годится для того, чтобы посмотреть, и категорически не годится для рабочего кода).

import ctypes
import sys
 
class DictKeys(ctypes.Structure):
    _fields_ = [("dk_refcnt", ctypes.c_ssize_t),
                ("dk_log2_size", ctypes.c_uint8),
                ("dk_log2_index_bytes", ctypes.c_uint8),
                ("dk_kind", ctypes.c_uint8),
                ("dk_version", ctypes.c_uint32),
                ("dk_usable", ctypes.c_ssize_t),
                ("dk_nentries", ctypes.c_ssize_t)]
 
class Dict(ctypes.Structure):
    _fields_ = [("ob_refcnt", ctypes.c_ssize_t),
                ("ob_type", ctypes.c_void_p),
                ("ma_used", ctypes.c_ssize_t),
                ("ma_version_tag", ctypes.c_uint64),
                ("ma_keys", ctypes.POINTER(DictKeys)),
                ("ma_values", ctypes.c_void_p)]
 
def state(d):
    obj = Dict.from_address(id(d))
    keys = obj.ma_keys.contents
    size = 1 << keys.dk_log2_size
    base = ctypes.addressof(keys) + ctypes.sizeof(DictKeys)
    slots = list((ctypes.c_int8 * size).from_address(base))
    return (f"used={obj.ma_used} size={size} usable={keys.dk_usable} "
            f"nentries={keys.dk_nentries} bytes={sys.getsizeof(d)}\n  {slots}")
 
d = {1: 1, 2: 2, 3: 3}
print("три вставки  ", state(d))
d[1] = 100
print("обновление   ", state(d))   # счётчики не изменились
del d[2]
print("удаление     ", state(d))   # в слоте 2 появилось -2, usable прежний
d[2] = 22
print("вставка назад", state(d), list(d))   # [1, 3, 2] — ключ уехал в конец

У O(1) есть худший случай, и он O(n)

Всё, что выше сказано про пробирование, держится на одном допущении: хеши разбросаны. Если они не разбросаны, механизм не ломается — он вырождается, и вырождается ровно в перебор.

Измеряется это не секундомером, а счётчиком: сколько раз словарь позвал __eq__ за один поиск (bench/dict/hash_collisions.py).

Число сравнений равно числу ключей — это O(n) буквально, а не «медленнее». И число это от машины не зависит вовсе: считается сам алгоритм.

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

Время приложено как иллюстрация, не как утверждение о вашей машине: от n = 16 к n = 4096 плохой хеш подорожал примерно в 250 раз (в опубликованном прогоне — в 257,7, на повторных выходило от 240 до 290), нормальный — в 1,0. Числа сняты на 3.13.7.

Отдельно — цена самого протокола, без всяких коллизий. Хеш int и str считает код на C; у пользовательского класса __hash__ — это вызов функции Python на каждом поиске:

int                                        45,4 нс
str (кеш хеша в объекте)                   37,1 нс
объект без __hash__/__eq__ (по id)         35,5 нс
объект с __hash__/__eq__ на Python        143,6 нс

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

Строка про int медленнее str не опечатка и объясняется тем, о чём статья уже писала выше: словарь со строковыми ключами идёт по специализированной lookdict_unicode, а с целыми — по общей lookdict; вдобавок у строки хеш посчитан один раз и лежит в самом объекте.

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

Под капотом: история версий

На порядок вставки стало можно полагаться не в одном релизе, а в двух — разнесённых ровно на один:

Что из этого — гарантия языка, а что — деталь реализации

Стоит разделять два уровня:

• Гарантия языка (можно полагаться в проде): словари сохраняют порядок вставки — с Python 3.7 это часть спецификации, а не побочный эффект (см. changelog 3.7). Ключом может быть любой хешируемый объект — int, str и не только.
• Деталь реализации CPython (может измениться в другой версии или в PyPy/GraalPy): конкретные числа 8 / ⅔ / ×3, формула PERTURB_SHIFT = 5, само разделение на dk_indices/dk_entries, key-sharing dict из PEP 412, отказ от хранения хешей для строковых ключей в 3.11. Код, который явно завязан на эти числа (а не просто на публичное поведение словаря), — красный флаг при код-ревью.

Чем измерено

Числа этой статьи получены этими скриптами. Каждый открывается прямо отсюда — вместе с записью прогона: на чём считали, что получилось и с каким разбросом.

• bench/dict/dict_bench.py
• bench/dict/hash_collisions.py