Коллизии неизбежны — что делать

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

Hash-таблица должна уметь хранить несколько пар в одном слоте и при lookup’е находить нужную. Есть две принципиально разные стратегии:

1. Chaining — в каждом слоте хранится связный список (или дерево) всех ключей с этим хешем.
2. Open addressing — каждый слот вмещает одну пару, при коллизии ищем следующий свободный слот по детерминированной формуле.

Это главный архитектурный выбор при реализации hash-таблицы. Java HashMap и Go map используют chaining. Python dict и Rust HashMap — open addressing. Каждый выбор имеет свои pro и contra.

Chaining: связные списки в слотах

Идея: каждый слот хранит указатель на список всех элементов с этим хешем. При коллизии новый элемент просто добавляется в этот список.

# схематическая Python-имплементация (упрощённая)
class ChainedHashMap:
    def __init__(self, size=16):
        self.size = size
        self.slots = [[] for _ in range(size)]   # каждый слот — list

    def put(self, key, value):
        idx = hash(key) % self.size
        bucket = self.slots[idx]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)   # обновление
                return
        bucket.append((key, value))         # вставка нового

    def get(self, key):
        idx = hash(key) % self.size
        for k, v in self.slots[idx]:
            if k == key:
                return v
        raise KeyError(key)

Java HashMap делает то же самое, с одной оптимизацией: если в bucket’е накапливается больше 8 элементов, связный список превращается в сбалансированное дерево (red-black). Это спасает от деградации до O(n) при патологических коллизиях — становится O(log n).

Pro chaining

1. Простая логика: вставка всегда работает (даже когда load factor = 1.5).
2. Никогда не нужно resize’ить в момент вставки — список просто растёт.
3. Удаление простое: убрать элемент из списка.
4. Tolerant к высокому load factor: можно запихнуть n=2*capacity и работает (хуже, но работает).

Contra chaining

1. Cache-unfriendly: каждый узел списка — отдельный malloc, размещён в случайной части heap. CPU prefetcher не угадывает следующий узел.
2. Memory overhead: на каждую пару нужно ~16-32 байта на указатель + аллокация узла.
3. Лишний indirection: чтобы прочитать значение, нужно сначала dereference указатель на bucket, потом обойти список.

Open addressing: пробирование

Идея: один слот = одна пара. При коллизии ищем следующий свободный слот по формуле пробирования. Если массив заполнен — resize.

# схематическая упрощённая имплементация
class OpenAddressedMap:
    def __init__(self, size=8):
        self.size = size
        self.slots = [None] * size

    def put(self, key, value):
        idx = hash(key) % self.size
        while True:
            slot = self.slots[idx]
            if slot is None or slot[0] == key:
                self.slots[idx] = (key, value)
                return
            idx = (idx + 1) % self.size   # linear probing

    def get(self, key):
        idx = hash(key) % self.size
        while True:
            slot = self.slots[idx]
            if slot is None:
                raise KeyError(key)
            if slot[0] == key:
                return slot[1]
            idx = (idx + 1) % self.size

Это linear probing — простейшая форма пробирования: при коллизии идём в следующий слот. Реальный Python dict использует более хитрую формулу с perturbation (увидим в модуле 9), но идея та же.

Pro open addressing

1. Cache-friendly: все данные в одном непрерывном массиве. CPU prefetch’ит следующие слоты.
2. Меньше памяти: нет указателей, нет аллокаций узлов. На пару нужно столько, сколько занимает слот (16-32 байта на 64-битной машине).
3. Меньше indirection: данные читаются прямо из массива, никаких dereferences.

Contra open addressing

1. Нужно resize’ить раньше: при load factor больше 2/3 (Python) или 0.5-0.75 деградация наступает быстро.
2. Сложное удаление: нельзя просто очистить слот, иначе lookup сломается. Используют tombstone маркер.
3. Кластеризация: linear probing накапливает «комки» занятых слотов, что увеличивает число проб.

Где быстрее на практике

Современный CPU сильнее всего страдает от cache miss: доступ к L1 кешу — 1 ns, к RAM — 100 ns. Разница в 100 раз. Поэтому cache locality часто важнее теоретической сложности.

Open addressing выигрывает там, где данные помещаются в кеш или последовательно prefetch’ятся. Chaining выигрывает там, где load factor высокий и таблица плотно набита.

В типичных условиях (load factor 50-66%) open addressing в 3-5 раз быстрее chaining’а из-за cache locality. Это и есть главная причина, почему Python dict — open addressing.

Память: tradeoffs

Память тоже отличается принципиально:

Chaining (Java HashMap), 1M ключей:
- Массив указателей: 1.33M × 8 = ~10 MB
- Node объекты: 1M × ~48 байт (key, value, next, hash) = ~48 MB
- Итого: ~58 MB

Open addressing (Python dict), 1M ключей:
- Слоты: 1.5M × 24 байта (hash, key, value) = ~36 MB
- Итого: ~36 MB

Open addressing экономит ~40% памяти на хеш-таблице. На больших датасетах это значимо.

Но! Python dict дополнительно использует compact representation с 3.6+ — два массива вместо одного: индексная таблица (плотная) + entries (плотный массив пар). Это экономит ещё 20-25% памяти. Об этом — в модуле 9.

Resize: оба подхода

И chaining, и open addressing требуют resize при переполнении. Логика одинакова:

1. Создать новый массив (обычно в 2 раза больше).
2. Перехешировать все ключи и положить в новые слоты.
3. Освободить старый массив.

Стоимость resize O(n) на размер таблицы. Но в chaining можно работать с большим load factor (до 1.0+), а в open addressing — нужно начинать resize при 0.66-0.75. Поэтому chaining делает resize реже, но open addressing работает быстрее между resize’ами.

Что выбирают реальные библиотеки

Попробуй сам

Реализуйте простую open-addressing hash-таблицу и сравните её с Python dict:

class SimpleHashMap:
    def __init__(self, size=8):
        self.size = size
        self.slots = [None] * size
        self.n = 0

    def put(self, key, value):
        if self.n / self.size > 0.66:
            self._resize()
        idx = hash(key) % self.size
        while self.slots[idx] is not None and self.slots[idx][0] != key:
            idx = (idx + 1) % self.size
        if self.slots[idx] is None:
            self.n += 1
        self.slots[idx] = (key, value)

    def get(self, key):
        idx = hash(key) % self.size
        while self.slots[idx] is not None:
            if self.slots[idx][0] == key:
                return self.slots[idx][1]
            idx = (idx + 1) % self.size
        raise KeyError(key)

    def _resize(self):
        old = self.slots
        self.size *= 2
        self.slots = [None] * self.size
        self.n = 0
        for slot in old:
            if slot is not None:
                self.put(slot[0], slot[1])

# теперь сравните
import time

m = SimpleHashMap()
start = time.perf_counter()
for i in range(100_000):
    m.put(i, i * 2)
print(f"SimpleHashMap: {(time.perf_counter()-start)*1000:.0f} ms")

d = {}
start = time.perf_counter()
for i in range(100_000):
    d[i] = i * 2
print(f"Python dict:   {(time.perf_counter()-start)*1000:.0f} ms")

Ожидаемо: Python dict в 10-20 раз быстрее, потому что:

• Реализован на C, не на Python.
• Использует perturbation вместо linear probing — меньше кластеризации.
• Имеет compact representation.

Но архитектурно оба используют open addressing — это та же идея.

В следующем уроке разберём load factor — главную метрику hash-таблицы. Что происходит при достижении 2/3, почему Python именно 2/3, а не 0.75, как Java.