Python dict — внутреннее устройство и рехэширование

Общая структура (CPython 3.6+)

С Python 3.6 dict реализован как компактный хэш-массив (compact hash table). Хранилище разделено на две части:

┌─────────────────────────────────────┐
│  indices[]  — "sparse" индекс-массив│  ← хэш-таблица (разреженная)
├─────────────────────────────────────┤
│  entries[]  — "dense" массив записей│  ← плотный, по порядку вставки
└─────────────────────────────────────┘

indices[] — разреженный массив индексов

indices = [EMPTY, 2, EMPTY, 0, 1, EMPTY, EMPTY, 3]
           -1     ↑         ↑   ↑         
                  │         │   └── индекс в entries[]
                  └─────────┘

• Размер всегда степень двойки (8, 16, 32 ...)
• Тип элемента подбирается под размер: int8 / int16 / int32 / int64
• Значения: -1 (EMPTY), -2 (DUMMY/deleted), или индекс в entries[]

entries[] — плотный массив (insertion-ordered!)

Каждый элемент — структура из трёх полей:

// Objects/dictobject.c
typedef struct {
    Py_hash_t me_hash;   // кэшированный хэш ключа (Py_ssize_t)
    PyObject *me_key;    // указатель на ключ
    PyObject *me_value;  // указатель на значение
} PyDictKeyEntry;

Поиск ключа (lookup)

d["foo"]

1. hash_val = hash("foo")
2. slot = hash_val & (len(indices) - 1)   # битовая маска (быстрее mod)
3. idx   = indices[slot]
4. если idx == EMPTY → KeyError
5. если entries[idx].me_hash == hash_val
        AND entries[idx].me_key is key     # проверка по identity (быстро)
        OR  entries[idx].me_key == key     # fallback по equality (медленно)
   → нашли
6. иначе → probe (перебор следующих слотов)

Алгоритм пробинга — Perturbation probing (не linear!)

// Упрощённо из dictobject.c
perturb = hash_val;
while (True):
    slot = (slot * 5 + perturb + 1) & mask
    perturb >>= PERTURB_SHIFT   // PERTURB_SHIFT = 5
    // проверяем indices[slot]

Это не линейный пробинг и не двойное хэширование — формула гарантирует обход всей таблицы при любом размере степени 2.

Рехэширование (resize / rehash)

Когда срабатывает?

# Порог: load factor > 2/3
# Точнее: used > (size * 2) // 3
# где used = кол-во занятых + deleted (dummy) слотов

size=8  → resize при used > 5
size=16 → resize при used > 10
size=32 → resize при used > 21

Размер после resize

// minused = количество реально живых ключей
// Ищем минимальную степень двойки > minused * 4 (если dict маленький)
// или > minused * 2 (если большой, > 50000)

new_size = 8
while new_size <= minused * growth_factor:
    new_size <<= 1

Рост при маленьких dict: × 4
Рост при больших dict:   × 2

Что происходит при рехэшировании?

СТАРАЯ ТАБЛИЦА              НОВАЯ ТАБЛИЦА
indices[8]                  indices[32]   (новый пустой массив)
entries[5 записей]          entries[]     (те же объекты!)

Шаги:
1. Выделяется новый indices[] нужного размера, заполняется EMPTY
2. Проходим по entries[] (плотный массив — БЕЗ дыр!)
3. Для каждой записи: новый slot = me_hash & new_mask
4. Вставляем индекс в новый indices[] (с пробингом при коллизиях)
5. entries[] НЕ копируется — только indices[] пересчитывается!

Ключевое преимущество компактного формата: при resize не нужно перекладывать сами данные — только переиндексировать indices[]. Порядок вставки сохраняется автоматически.

Удаление (почему нет немедленного resize вниз)

d = {i: i for i in range(100)}
del d[50]  # что происходит?

indices[slot] = DUMMY (-2)   ← "надгробие", не EMPTY!
entries[idx].me_key   = NULL
entries[idx].me_value = NULL

Dummy нужен, потому что иначе цепочки пробинга разорвутся:

Вставка:  A→slot5, B→slot5(коллизия)→slot7
Удаление A: slot5=EMPTY
Поиск B:  slot5==EMPTY → KeyError!  ← НЕВЕРНО без dummy

Resize вниз происходит только при следующей вставке, если:

(used - dummy) * 4 <= size

Специальные оптимизации

Split-table для объектов классов

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

p1 = Point(1, 2)
p2 = Point(3, 4)

Экземпляры одного класса делят ОДИН indices[]+keys[]
и имеют СВОИ values[]

p1.__dict__ → keys=[shared], values=[1, 2]
p2.__dict__ → keys=[shared], values=[3, 4]

Unicode-ключи (dict с str-ключами)

Если все ключи — str, CPython использует оптимизированный lookup (lookdict_unicode), который пропускает проверку типа.

Итоговая схема

Краткая сводка