Dict: hash function, open addressing, perturbation probe

dict — самая важная структура данных Python. На ней построены namespaces (globals(), locals(), __dict__), kwargs, JSON-десериализация, Pandas/Polars groupby, attribute lookup, метод resolution order. Каждый раз, когда вы пишете obj.attr или d[key], под капотом работает lookdict() из Objects/dictobject.c — самые важные 200 строк CPython.

В этом уроке мы откроем эти 200 строк и пройдём по ним: hash function → probe sequence → load factor → resize. После него вы сможете объяснить, почему 'x' in big_dict — O(1) average, и почему worst-case это всё ещё O(n).

Hash table — общая идея

Hash table — структура для O(1) average lookup. Mechanism:

1. Hash function h(key) → integer (произвольный 64-битный).
2. Modulo i = h(key) mod table_size → slot index в массиве.
3. Probing при коллизии (другой key уже в том slot) — последовательный поиск свободного slot’а.

Две стратегии разрешения коллизий:

• Separate chaining: каждый slot — указатель на linked list (Java HashMap до 8). Коллидирующие keys в одной цепочке. Lookup = hash + linear scan по цепочке.
• Open addressing: при коллизии probe sequence ищет другой slot в той же таблице (Python, Ruby, Lua). Никаких pointers/chains — только массив фиксированного размера.

CPython использует open addressing с perturbation probe. Это даёт хороший cache locality (всё в одном массиве, sequential probing) и низкий memory overhead (нет per-slot pointer).

CPython hash function

Для разных типов разные __hash__ (см. Python/pyhash.c и Include/cpython/pyhash.h):

print(hash(42))                    # 42
print(hash('hello'))               # randomized — каждый запуск разный
print(hash((1, 2, 3)))             # детерминирован (если elements детерминированы)
print(hash(frozenset({1, 2})))     # детерминирован
print(hash(1.0) == hash(1))        # True — cross-type consistency

Open addressing с perturbation probe

Псевдо-код функции lookdict() (упрощённо):

static Py_ssize_t
lookdict(PyDictObject *mp, PyObject *key, Py_hash_t hash) {
    size_t mask = DK_MASK(mp->ma_keys);  // mask = size - 1
    size_t perturb = hash;
    size_t i = (size_t)hash & mask;       // initial slot

    while (1) {
        Py_ssize_t ix = dictkeys_get_index(mp->ma_keys, i);
        if (ix == DKIX_EMPTY) return DKIX_EMPTY;  // not found
        if (ix >= 0) {
            PyDictKeyEntry *ep = &DK_ENTRIES(mp->ma_keys)[ix];
            if (ep->me_hash == hash && PyObject_RichCompareBool(ep->me_key, key, Py_EQ))
                return ix;  // found
        }
        // collision: continue probe
        perturb >>= PERTURB_SHIFT;            // PERTURB_SHIFT = 5
        i = (5 * i + 1 + perturb) & mask;     // next slot
    }
}

Ключевая формула probe sequence: i = (5*i + 1 + perturb) & mask, где perturb начинается равным hash и сдвигается вправо на PERTURB_SHIFT = 5 бит каждой итерации. Разберём, почему именно так:

• 5*i + 1 — линейная конгруэнция, гарантирует прохождение всех slot’ов перед повторением (full cycle property).
• + perturb — добавляет high bits hash’а, которые & mask обычно отбрасывает на initial slot. Без этого probe sequence зависел бы только от низких бит hash’а — keys с разными high bits, но одинаковыми низкими, имели бы одинаковую probe sequence (primary clustering).
• perturb >>= 5 — каждой итерации probe «использует» ещё 5 бит hash’а из верхней половины. Через 64/5 ≈ 13 итераций perturb становится 0, и probe вырождается в чистый 5*i + 1 (всё ещё full cycle, но теперь без рандомизации).

Cite: формула из Objects/dictobject.c, PERTURB_SHIFT определён как макрос там же. Алгоритм восходит к Tim Peters (см. дискуссию на python-dev в начале 2000-х; статья «Modern Dictionaries» — Raymond Hettinger 2017).

Load factor 2/3 (USABLE_FRACTION)

CPython держит load factor ≤ 2/3 через макрос:

#define USABLE_FRACTION(n) (((n) << 1)/3)

Это означает: при dk_size = n, максимальное число валидных entries ≤ 2n/3. Для n = 8 → 5 entries; для n = 16 → 10; для n = 32 → 21. См. Objects/dictobject.c, макрос USABLE_FRACTION.

Когда insert вызвал бы load > 2/3, dict resize’ит (обычно ×2; точнее — GROWTH_RATE macro). При resize все existing keys рехешируются и распределяются в новую таблицу — это O(n) операция. Но resize происходит геометрически (раз в ~n/3 insert’ов), значит amortized cost — O(1) per insert.

Почему именно 2/3? Для open addressing средняя длина probe sequence при successful lookup ≈ 0.5 · (1 + 1/(1-α)), где α = load factor:

При α → 1 число проб взрывается. CPython выбрал 2/3 как компромисс между memory overhead (низкий α тратит память впустую) и lookup speed (высокий α делает probes длинными). См. CLRS глава 11 для деривации формулы.

import sys
print(sys.getsizeof({}))          # 64 байт - empty dict
print(sys.getsizeof({'a': 1}))    # 184 байт - после первого insert
# (на cpython-3.12.7; точные значения см. baseline)

# Иллюстрация load factor:
import sys
d = {}
prev_size = sys.getsizeof(d)
for i in range(100):
    d[i] = i
    cur_size = sys.getsizeof(d)
    if cur_size != prev_size:
        print(f"resize at len={i+1}: {prev_size} -> {cur_size}")
        prev_size = cur_size

Видно ступеньки: resize’ы происходят при load factor ≈ 2/3.

Why amortized O(1)?

Декомпозиция для последовательности из n insert’ов:

• Дешёвых insert’ов: ~n штук, каждый O(1) (hash + probe ~3 шага + write).
• Дорогих resize’ов: log₂(n) штук (factor 2 рост), k-й resize обрабатывает ~n_k entries.
• Total work resize’ов: 1 + 2 + 4 + … + n/2 + n = 2n - 1 = O(n) (геометрический ряд).
• Total work: O(n) дешёвых + O(n) resize = O(n).
• Amortized per insert: O(n) / n = O(1).

Для lookup (без insert) — всегда O(1) average, O(n) worst-case. Worst case — все keys hash’ируются в одну bucket, probe sequence обходит всю таблицу. На практике этого не бывает, потому что:

1. Hash randomization для str/bytes (адверсариальный input не работает).
2. Perturbation (близкие hash’и идут разными probe sequences).

Когда dict break down

1. Adversarial input. Без hash randomization атакующий может составить N запросов с одинаковым hash → все коллидят → каждый lookup O(N), итого O(N²) DoS. Python-3.4+ с randomization это митигирует. Но если поставите PYTHONHASHSEED=0 (или у вас pre-3.4) — vulnerability возвращается.

2. Bad custom __hash__. Если вы переопределили __hash__ так, что он возвращает константу (return 0) — все объекты коллидят, lookup degrade’ится до O(n):

# Пример bad custom __hash__:
class Bad:
    def __init__(self, val):
        self.val = val
    def __hash__(self):
        return 0  # константа - degrade до O(n)
    def __eq__(self, other):
        return self.val == other.val

d = {Bad(i): i for i in range(10000)}  # build O(n²) - все collide
print(d[Bad(5000)])                    # lookup O(n) вместо O(1)

Контракт __hash__ должен распределять hash’и uniformly для типичного workload’а.

3. Frequent resize при large dict construction. Если вы знаете финальный размер, pre-size:

# Без pre-size: ~log2(N) resize'ов
d = {}
for k, v in big_input:
    d[k] = v

# С pre-size: 1 allocation, 0 resize'ов
d = dict.fromkeys(['k1', 'k2', ...])  # initial size ≥ N
# или
d = {k: 0 for k in big_keys}  # comprehension с known size

Cross-course context

PyDictObject использует open addressing с perturbation probe — той же идее следуют hash-based JOIN’ы в OLAP. Cross-course → ClickHouse 06/04 join-algorithms — Hash JOIN строит in-memory hash table из меньшей relation, потом потоково матчит большую: hash function + probe + load factor — всё то же самое, что в lookdict(), только в SIMD-batched варианте над 1024 ключей за раз вместо одного.

Cross-course → Storage Formats: 07/01 memory-layout — Arrow zero-copy IPC reuses immutable buffer idea: ключ Arrow Schema иммутабелен после построения, поэтому buffer’ы можно шарить между процессами без copy (mmap или shared-memory). В CPython tuple-key dict — та же история: tuple immutable → hash кэшируется → dict lookup not pay re-hash cost. Сходится через invariant immutability → cheap hash.

Ключевые выводы

1. dict = open-addressing hash table с perturbation probe. Коллизии разрешаются probe sequence в той же таблице (vs separate chaining).
2. Probe formula i = (5*i + 1 + perturb) & mask, perturb >>= PERTURB_SHIFT (5) каждой итерации. 5*i + 1 даёт full cycle; perturb рандомизирует pattern через high bits hash’а.
3. Load factor ≤ 2/3 (USABLE_FRACTION). При превышении — resize ×2 + rehash. Average probes ≈ 2 при α = 2/3 → O(1) average.
4. Lookup amortized O(1), worst-case O(n) (все keys collide). Защита: hash randomization (str/bytes), uniform distribution custom __hash__.
5. CPython hash function для разных типов: int (identity), str/bytes (SipHash randomized), tuple (XOR-mix), float (cross-type consistent). См. Python/pyhash.c.

В уроке M02-04 разберём PEP 468 compact dict layout — dk_indices + dk_entries — который экономит ~30-65% памяти и бесплатно даёт preservation of insertion order.