Главная метрика hash-таблицы

Load factor — это отношение числа занятых слотов к общему числу слотов:

load_factor = n / capacity

Где n — количество вставленных пар, capacity — размер внутреннего массива слотов. Это главное число, по которому hash-таблица решает, не пора ли расти.

Если load factor низкий (например, 0.3), коллизий мало, lookup работает быстро. Если высокий (0.9), коллизий много, пробирование длинное, lookup замедляется. Hash-таблицы стараются держать load factor в золотом коридоре — обычно 0.5-0.75.

Зачем вообще нужен пустой запас

Можно было бы заполнять все 100% слотов. Почему нет?

Причина в математике коллизий. Чем плотнее заполнен массив, тем выше вероятность, что новый ключ попадёт в занятый слот. При load factor 0.5 в среднем нужно ~1.5 проб для open addressing. При 0.9 — уже ~5.5. При 0.95 — ~10+.

Threshold и resize

Hash-таблица определяет threshold (порог) — load factor, при достижении которого вызывается resize. Resize создаёт массив большего размера и перехеширует все ключи.

Псевдокод:

def put(self, key, value):
    if self.n + 1 > self.threshold:
        self._resize()
    # обычная вставка
    ...

def _resize(self):
    old_slots = self.slots
    self.capacity *= 4 if self.capacity < 50_000 else 2   # Python: ×4, потом ×2
    self.slots = [None] * self.capacity
    self.threshold = int(self.capacity * 0.66)
    self.n = 0
    for slot in old_slots:
        if slot is not None:
            self.put(slot.key, slot.value)

Resize стоит O(n) — нужно пересчитать хеш и переложить каждый ключ. Это дорогая операция, поэтому делается редко: после resize таблица в 2-4 раза больше, и до следующего resize пройдёт много вставок.

Python: target 2/3 load factor

Python dict таргетирует load factor 2/3 ≈ 0.66. Это значит, что при заполнении ~66% слотов происходит resize.

Конкретные числа:

# схематично — реальная имплементация в Objects/dictobject.c
INITIAL_SIZE = 8
GROWTH_RATE_SMALL = 4    # умножать на 4 для маленьких dict
GROWTH_RATE_LARGE = 2    # на 2 для больших (n > ~50K)
LOAD_FACTOR_THRESHOLD = 2 / 3

Размеры всегда степени двойки: 8, 16, 32, 64, 128, …, 65536. Это позволяет вместо медленного hash % size использовать быстрое hash & (size - 1).

# проверим, как Python меняет размер при росте
import sys
d = {}
prev_size = sys.getsizeof(d)
for i in range(1000):
    d[i] = i
    cur_size = sys.getsizeof(d)
    if cur_size != prev_size:
        print(f"n={len(d):4d}: size={cur_size} bytes")
        prev_size = cur_size

Типичный вывод (детали зависят от Python-версии, тут CPython 3.13):

n=   1: size=224 bytes
n=   6: size=352 bytes      <- resize при 5
n=  11: size=632 bytes      <- resize при ~10
n=  22: size=1184 bytes
n=  43: size=2272 bytes
n=  86: size=4448 bytes
n= 171: size=8800 bytes
n= 342: size=17504 bytes
n= 683: size=34912 bytes

Видно: resize происходит примерно каждый раз, когда n удваивается. Между resize’ами вставки работают за O(1).

Java: target 0.75 load factor

Java HashMap таргетирует load factor 0.75. Это компромисс другой:

• Чуть плотнее, чем Python — экономит ~10% памяти.
• Чуть медленнее в среднем — больше коллизий.

Почему такая разница? Потому что Java HashMap использует chaining: ему нестрашно держать load factor выше, потому что вместо длинных цепочек пробирования у него длинные списки (или деревья после Java 8). С chaining «комок» в одном bucket’е не влияет на остальные.

Почему именно 2/3, а не 0.5 или 0.9

Выбор load factor threshold — это trade-off:

Python выбрал 2/3, потому что:

1. На load factor 0.66 среднее число проб для open addressing ~2.5 — приемлемо.
2. 33% памяти впустую — терпимо.
3. Степень двойки в capacity упрощает арифметику.

Java выбрал 0.75 по схожим, но чуть более «плотным» соображениям, потому что chaining терпимее к коллизиям.

Что происходит во время resize

Resize — самая дорогая операция в hash-таблице. Поэтапно:

1. Allocate: создаётся новый массив слотов в 2-4 раза больше.
2. Rehash: каждый существующий ключ хешируется заново (хеш сам кешируется, поэтому не пересчитывается — просто hash & (new_size - 1) даёт новый индекс).
3. Copy: каждая пара переносится в новый слот.
4. Free: старый массив освобождается.

# измерим время resize
import time
import sys

d = {}
sizes = []
times = []
prev_capacity = 0

for i in range(10_000_000):
    start = time.perf_counter_ns()
    d[i] = i
    elapsed = time.perf_counter_ns() - start

    cur_capacity = sys.getsizeof(d)
    if cur_capacity != prev_capacity:
        sizes.append(i)
        times.append(elapsed)
        prev_capacity = cur_capacity

# здесь times[k] — время вставки, которая вызвала k-й resize
# обычно резко больше типичных 50-100 ns

На M-class CPU resize 1M ключей занимает ~30-50 ms — заметно. Между resize’ами обычная вставка ~80 ns. Если измерить latency каждой отдельной вставки, видны редкие всплески — это resize’ы.

Pre-sizing: оптимизация для горячих случаев

Если вы заранее знаете, что положите 1M ключей, можно создать dict «нужного размера» сразу, чтобы избежать всех resize’ов:

# Python: нет прямого API на pre-size, но можно через dict.fromkeys
# или просто создать ёмкий dict через {}.fromkeys(range(1_000_000))

# а вот в Java и Go pre-sizing явный:
# Java: new HashMap<>(initial_capacity, load_factor)
# Go:   make(map[K]V, initial_size)

В Python для pre-sizing есть пара трюков:

# 1. для маленьких dict — создавайте сразу с данными
d = {f"key_{i}": i for i in range(1_000_000)}

# 2. для динамического роста — никаких чудес, dict сам справится
# resize'ы amortized O(1)

# 3. dict.fromkeys — создаст dict с N пустых значений
d = dict.fromkeys(range(1_000_000), None)

В DE pre-sizing полезен, когда вы строите большой lookup-table из известного источника и хотите минимизировать latency-всплесков.

Compact dict с Python 3.6

Python 3.6+ использует compact representation: вместо одного массива слотов — два:

• Indices: маленький массив int8/int16/int32 (зависит от capacity), хранящий индекс в entries или -1 (пусто).
• Entries: плотный массив пар (hash, key, value) в порядке вставки.

Старый dict (до 3.6):
slots = [
    (hash, key, value),     <- slot 0
    None,                   <- slot 1 (пустой)
    (hash, key, value),     <- slot 2
    None,
    ...
]
sparse, тратит память на None

Новый compact dict (3.6+):
indices  = [2, -1, 0, -1, 1, -1, -1, -1]   <- 8 байт (int8)
entries  = [(h1, k1, v1), (h2, k2, v2), (h3, k3, v3)]   <- плотный массив

Это экономит 20-25% памяти на dict + даёт ещё один бонус: порядок вставки сохраняется автоматически (entries — в порядке вставки). Именно поэтому с 3.7 порядок ключей в dict гарантирован.

Попробуй сам

import sys
import time

# 1. Постройте таблицу размеров dict при росте
d = {}
prev_size = sys.getsizeof(d)
boundaries = [(0, prev_size)]
for i in range(10_000):
    d[i] = i
    cur_size = sys.getsizeof(d)
    if cur_size != prev_size:
        boundaries.append((len(d), cur_size))
        prev_size = cur_size

print("n: size_bytes")
for n, s in boundaries:
    print(f"{n:5d}: {s} bytes")

# 2. Измерьте латенси каждой вставки на 1M ключах
n = 1_000_000
d = {}
latencies = []
for i in range(n):
    start = time.perf_counter_ns()
    d[i] = i
    latencies.append(time.perf_counter_ns() - start)

# найдите самые долгие
import heapq
top_10 = heapq.nlargest(10, enumerate(latencies), key=lambda x: x[1])
print("\nТоп-10 самых медленных вставок (i, latency_ns):")
for i, lat in top_10:
    print(f"  i={i}: {lat} ns")

# обычно: ~5-7 редких всплесков по 30-100 ms — это resize'ы

# 3. Pre-allocated dict — сравните скорость
n = 1_000_000

# наивно
start = time.perf_counter()
d = {}
for i in range(n):
    d[i] = i
print(f"Empty dict: {(time.perf_counter()-start)*1000:.0f} ms")

# pre-allocated через comprehension
start = time.perf_counter()
d = {i: i for i in range(n)}
print(f"Comprehension: {(time.perf_counter()-start)*1000:.0f} ms")

В следующем модуле мы залезем внутрь Python dict — посмотрим на perturbation, точную формулу probing, что такое индексная таблица в compact representation, и почему dict с одинаковыми хешами деградирует в O(n^2).