Точная формула, по которой Python dict ищет слот

В модуле 8 мы видели open addressing с linear probing: при коллизии переходим в следующий слот, потом ещё следующий, и так далее. Это простая стратегия, но она имеет фатальный недостаток — primary clustering: занятые слоты слипаются в длинные «комки», и любой новый ключ, попавший в начало комка, должен пройти его весь.

Python dict использует более хитрую формулу, которая решает эту проблему. Точнее, две формулы — одна для «дополнительного смешивания» битов хеша, другая для самого пробирования. Разберём обе.

Зачем вообще пробирование сложнее линейного

Сначала вспомним, что не так с linear probing.

# linear probing: j_next = (j + 1) % size
# если хеши: 5, 5, 5, 5, 5 — все хотят в slot 5
# раскладка: slot 5, slot 6, slot 7, slot 8, slot 9 — кластер из 5 подряд

Теперь любой новый ключ с хешем 5, 6, 7, 8, 9 после mod size попадёт в этот кластер. Каждая последующая вставка усугубляет проблему: кластер растёт, и все ключи, чьи хеши попадают в его «область влияния», должны его пройти. Это называется primary clustering.

Главное: даже если хеш-функция идеальная и хеши равномерные, после mod size ключи всё равно слипаются в кластеры из-за пробирования по соседям.

Решение Python: квадратичное пробирование с perturbation

Python dict не идёт в соседний слот. Он использует формулу:

j = (5 * j + 1 + perturb) mod size
perturb >>= PERTURB_SHIFT   # PERTURB_SHIFT == 5

Где:

• j — текущий индекс слота.
• perturb — изначально равен полному хешу ключа.
• PERTURB_SHIFT — константа 5, означает сдвиг на 5 битов вправо на каждой итерации.

Это рекурсивная формула пробирования: каждый шаг даёт новый индекс, который зависит от всех битов хеша, а не только от младших, которые использовались в первом обращении (hash & mask).

Что делает perturbation

mod size (через & mask) использует только младшие log2(size) битов хеша. Если хеши разных ключей имеют одинаковые младшие биты, но разные старшие — они попадут в один слот, хотя их хеши разные.

Perturbation решает это: после первой коллизии в формулу подключаются старшие биты хеша через perturb. Каждый сдвиг perturb >>= 5 поднимает на поверхность следующие 5 битов.

# схематическая Python-имплементация (упрощённая)
def find_slot(hash_value, key, slots, size):
    PERTURB_SHIFT = 5
    mask = size - 1
    perturb = hash_value
    j = hash_value & mask

    while slots[j] is not None and slots[j].key != key:
        j = (5 * j + 1 + perturb) & mask
        perturb >>= PERTURB_SHIFT

    return j

Через 12-13 итераций perturb становится 0 (64 битa / 5 ≈ 12 сдвигов), и формула вырождается в j = (5*j + 1) mod size. Эта остаточная формула гарантирует, что probing посетит все слоты массива до повторения — это fully cyclic последовательность для степеней двойки.

Почему именно 5*j + 1, а не j + 1

Множитель 5 — не магия, а математика. Чтобы probing посещал все слоты массива (когда perturb = 0), последовательность j -> (a*j + c) mod size должна быть полнопериодической. Условия Халла-Доббелла:

1. gcd(c, size) == 1 — здесь c=1, всегда выполнено.
2. Любое простое p, делящее size, должно делить и a - 1.
3. Если 4 делит size, должно делить и a - 1.

Для size = степень двойки и a = 5: a - 1 = 4, единственный простой делитель 2 — он делит и 4 ([ok]). Если 4 делит size, оно делит и 4 ([ok]). Условия выполнены, последовательность полнопериодическая.

С a = 1 (linear probing) условия тоже выполнены, но «5» даёт другое распределение: вместо равномерного шага по соседям делает «прыжок» через несколько слотов. Это разрушает clustering даже без perturbation.

Демонстрация: probing на коротком dict

Посмотрим, по каким слотам Python dict пробует ключ:

def probe_sequence(hash_value, size, max_steps=10):
    PERTURB_SHIFT = 5
    mask = size - 1
    perturb = hash_value
    j = hash_value & mask
    sequence = [j]
    for _ in range(max_steps):
        j = (5 * j + 1 + perturb) & mask
        perturb >>= PERTURB_SHIFT
        sequence.append(j)
        if perturb == 0 and j == sequence[0]:
            break
    return sequence

# хеш 12345 при size 8
print(probe_sequence(12345, 8))
# [1, 7, 6, 5, 4, 3, 2, 1, ...] - покрывает все 8 слотов

# хеш с тем же младшим битом, но другими старшими
print(probe_sequence(12345 + 8, 8))   # +8 не меняет младший байт mod 8
# [1, 0, 5, 2, 3, ...]  - совсем другая последовательность!

Видно: даже при одинаковом начальном слоте, последующие отличаются — потому что perturb разный. Это и есть главное достоинство схемы.

Что хранится в каждом слоте

В Python 3.13 dict использует compact representation (с 3.6). Каждая запись это:

struct PyDictEntry {
    Py_hash_t me_hash;     // 8 байт - закешированный хеш
    PyObject *me_key;      // 8 байт - указатель на ключ
    PyObject *me_value;    // 8 байт - указатель на значение
}

И отдельно — массив индексов в эти entry, размер которого зависит от capacity:

• capacity <= 256: индексы int8 (1 байт)
• capacity <= 65536: индексы int16 (2 байта)
• capacity <= 2^32: индексы int32
• Иначе int64

Полная схема compact dict:

indices:  [-1, 2, -1, -1, 0, -1, 1, -1]   <- sparse, 1 байт каждый
entries:  [
    (h0, k0, v0),    <- запись 0, key 'alice'
    (h1, k1, v1),    <- запись 1, key 'bob'
    (h2, k2, v2),    <- запись 2, key 'carol'
]

probing теперь идёт по массиву indices, не по entries. При совпадении индекса берём entries[indices[j]] и сравниваем ключ. Это даёт локальность кеша для probing — массив индексов компактный (1-2 байта на слот), весь помещается в L1.

Почему сравнение хеша — первое

В каждом entry первое поле — me_hash. Это закешированный хеш. При сравнении ключей Python сначала проверяет хеши, и только если хеши совпали, дёргает __eq__:

# в C код выглядит примерно так:
if entry.me_hash != hash_to_find:
    continue   # хеши разные — точно не наш ключ
if entry.me_key is key_to_find or eq(entry.me_key, key_to_find):
    return entry.me_value

Это критическая оптимизация:

1. Сравнение 8-байтных int — ~0.5 ns.
2. Вызов __eq__ для строк — десятки наносекунд (нужно сравнить байт за байтом).
3. Вызов __eq__ для custom объектов — может быть очень дорогой.

При коллизии в probing большинство кандидатов отсеиваются по хешу мгновенно, и __eq__ вызывается только на финальном правильном слоте. Без кеша хеша lookup был бы в разы медленнее.

is-проверка идёт первой, как ещё одна быстрая отсечка: если в качестве ключа передан тот же объект, что лежит в dict (например, sys.intern’ed строки или маленькие int), не нужно даже сравнивать хеши.

Эксперимент: probing подсчёт

Сколько проб в среднем нужно для lookup в полностью заполненном dict?

# создадим dict с известным числом ключей и измерим
import time

n = 100_000
d = {i: i for i in range(n)}

# каждый lookup — успешный
start = time.perf_counter()
for i in range(n):
    _ = d[i]
elapsed = time.perf_counter() - start

print(f"{n} lookups: {elapsed*1000:.1f} ms")
print(f"per lookup: {elapsed*1e9/n:.0f} ns")
# typically: ~50-80 ns per lookup

50-80 наносекунд на lookup. Что туда входит:

• ~5 ns: hash(key) — для int это тождество, тут почти бесплатно.
• ~2 ns: индексация массива.
• ~3-5 ns: сравнение хеша.
• ~5-10 ns: сравнение ключей (для int — простое равенство).

Если probing не нужен (load factor низкий, прямое попадание), хватает 1 шага. Реальный Python dict с load factor 50-66% делает в среднем 1.5-2.5 шага probing на lookup.

Попробуй сам

# 1. Реализуйте probe_sequence как выше и посмотрите, как меняются
#    последовательности при разных хешах
def probe_sequence(hash_value, size, max_steps=20):
    PERTURB_SHIFT = 5
    mask = size - 1
    perturb = hash_value & ((1 << 64) - 1)
    j = perturb & mask
    sequence = [j]
    for _ in range(max_steps):
        j = (5 * j + 1 + perturb) & mask
        perturb >>= PERTURB_SHIFT
        sequence.append(j)
    return sequence

print(probe_sequence(0, 16))         # [0, 1, 6, 15, 12, ...]
print(probe_sequence(16, 16))        # [0, 1, 6, 15, ...] — другой perturb, другая последовательность!
print(probe_sequence(2**32, 16))     # тоже другая

# 2. Сравните с linear probing
def linear_sequence(hash_value, size, max_steps=20):
    mask = size - 1
    j = hash_value & mask
    return [(j + i) & mask for i in range(max_steps)]

print(linear_sequence(0, 16))    # [0, 1, 2, 3, 4, 5, 6, ...]
print(linear_sequence(16, 16))   # [0, 1, 2, 3, ...] — ОДИНАКОВАЯ С 0! cluster!

# 3. Постройте dict с N ключами и измерьте среднее число проб
# (это потребует доступа к C API; в Python из коробки нельзя точно)

# 4. Измерьте время lookup для dict разных размеров
import time
for n in [100, 10_000, 1_000_000]:
    d = {i: i for i in range(n)}
    # warmup
    for i in range(min(n, 1000)):
        _ = d[i]
    start = time.perf_counter()
    for i in range(min(n, 100_000)):
        _ = d[i]
    elapsed = time.perf_counter() - start
    print(f"n={n}: {elapsed*1e9/min(n, 100_000):.0f} ns per lookup")

# Ожидаемо: 50-80 ns независимо от размера (это и есть O(1))

В следующем уроке разберём resize и rehashing — что именно происходит, когда dict перезапускает таблицу. Измерим стоимость на больших dict и посмотрим, как amortized analysis скрывает дорогие операции.