lab05 — hash map: коллизии и разрешение

Хеш-таблица (hash map) «с нуля», без встроенного dict. Лаборатория целиком про коллизии: что это, откуда берутся и как их разрешают три способа — метод цепочек (separate chaining), линейное пробирование и двойное хеширование (open addressing). Плюс коэффициент заполнения (load factor) и авторасширение таблицы с перехешированием (rehash).

Хеш-функции реализованы вручную, длина списков считается собственной array_length из common (без встроенных len/range/dict).

Что такое хеш и индекс ячейки

Идея hash map: чтобы за O(1) находить значение по ключу, превращаем ключ в число — хеш — и по нему сразу вычисляем индекс ячейки массива: index = hash(key) % capacity. Никакого перебора, как в линейном поиске из lab04: индекс считается напрямую.

def hash_int(key: int) -> int:
    return key if key >= 0 else -key      # для чисел хеш — само число


def hash_str(key: str) -> int:
    h = 0
    for ch in key:
        h = h * 31 + ord(ch)              # полиномиальный хеш (схема Горнера)
    return h


def hash_key(key) -> int:
    if isinstance(key, int):
        return hash_int(key)
    if isinstance(key, str):
        return hash_str(key)
    raise TypeError(...)                   # таблица знает только int и str

Полиномиальный хеш строки s — это значение многочлена s[0]·31^(n-1) + s[1]·31^(n-2) + ... + s[n-1]. База 31 — нечётное простое число, на которое процессор умножает дёшево (31*h == (h << 5) - h), а нечётность снижает число совпадений хешей у похожих строк.

Откуда берётся коллизия. Хеш — большое число, а ячеек всего capacity. Свёртка % capacity неизбежно «склеивает» разные хеши в один индекс. Когда два разных ключа дают один индекс — это и есть коллизия. При capacity = 8 ключи 1, 9, 17 все дают индекс 1 (1 % 8 == 9 % 8 == 17 % 8 == 1). Коллизии неизбежны (см. парадокс дней рождения) — вопрос не «как их избежать», а «как их разрешать».

Метод цепочек (separate chaining)

Идея: каждая ячейка (бакет) — это список пар [ключ, значение]. При коллизии новый ключ просто дописывается в список того же бакета. Поиск внутри бакета — обычный перебор короткого списка.

def put(self, key, value) -> None:
    bucket = self._buckets[self._index(key)]
    for pair in bucket:
        if pair[0] == key:
            pair[1] = value               # ключ уже есть — обновляем значение
            return
    if array_length(bucket) > 0:
        self.collisions += 1              # бакет был непуст — это коллизия
    bucket.append([key, value])
    self._size += 1
    if self.load_factor() > self._max_load:
        self._resize(self._capacity * 2)

get, contains, delete работают так же: считаем индекс, дальше идём по списку бакета.

Операция	Среднее	Худшее	Когда худшее
put / get / delete	O(1)	O(n)	все ключи в одном бакете (плохой хеш)
print_map / keys / items	O(n + capacity)	O(n + capacity)	проходим все бакеты

В среднем при хорошем хеше бакеты короткие (≈ load factor элементов), и операции — O(1). В худшем случае, когда хеш-функция сваливает все ключи в один бакет, цепочка вырождается в список и поиск деградирует до O(n) — ровно как линейный поиск.

Открытая адресация: линейное пробирование

Идея: хранить все пары в одном массиве слотов, без вложенных списков. При коллизии элемент не уходит в список, а ищет другой свободный слот по последовательности проб. У линейного пробирования шаг = 1: idx, idx+1, idx+2, ... (по кругу).

while self._slots[idx] is not _EMPTY:
    slot = self._slots[idx]
    if slot is _DELETED:
        if first_tombstone == -1:
            first_tombstone = idx         # запомнили надгробие для вставки
    elif slot[0] == key:
        slot[1] = value                   # ключ уже есть — обновляем
        return
    else:
        self.collisions += 1              # слот занят чужим ключом — коллизия
    i += 1
    idx = (start + i * step) % self._capacity

get идёт по той же последовательности проб и останавливается, только встретив пустой слот _EMPTY: раз по дороге к ключу была бы вставка, ключ оказался бы раньше пустого слота.

Минус линейного пробирования — первичная кластеризация: занятые слоты слипаются в длинные подряд идущие группы, и каждая новая коллизия удлиняет кластер, замедляя пробы.

Двойное хеширование

Идея: уменьшить кластеризацию, сделав шаг пробы зависящим от ключа — тогда коллизирующие ключи расходятся по таблице по-разному, а не выстраиваются в один кластер.

def _probe_step(self, key) -> int:
    if self._probe == "linear":
        return 1
    return (self._hash2(key) % self._capacity) | 1   # нечётный шаг

Здесь критичен нюанс: чтобы проба обошла все слоты и гарантированно нашла свободный, шаг должен быть взаимно прост с capacity. Мы держим capacity степенью двойки (8 → 16 → 32 …), а шаг делаем нечётным через | 1. Любое нечётное число взаимно просто со степенью двойки — значит, последовательность проб переберёт все слоты без зацикливания. Если бы шаг мог оказаться чётным (например 4 при capacity 8), проба ходила бы по 0, 4, 0, 4, … и пропустила половину таблицы.

Удаление и надгробия (tombstone)

Это и есть главный вопрос «что происходит при коллизии» на собеседовании. В открытой адресации нельзя при удалении просто очистить слот в _EMPTY.

Пример: ключи 1 и 9 коллизируют, 1 лёг в слот 1, 9 — в слот 2. Если удалить 1, очистив слот 1 в _EMPTY, то get(9) начнёт пробу со слота 1, увидит _EMPTY и решит, что 9 нет — хотя он лежит в слоте 2. Очистка разорвала цепочку проб.

Решение — надгробие (tombstone), особый маркер _DELETED:

def delete(self, key) -> bool:
    idx = self._find_slot(key)
    if idx == -1:
        return False
    self._slots[idx] = _DELETED           # не _EMPTY, а надгробие
    self._size -= 1
    self._tombstones += 1
    return True

• get / contains проходят сквозь надгробие дальше по цепочке проб (останавливаются только на _EMPTY), поэтому 9 по-прежнему находится.
• put может переиспользовать надгробие: запоминает первое встреченное и вставляет туда, если ключа дальше не оказалось.

Надгробия со временем засоряют таблицу, поэтому они учитываются в пороге расширения, а при rehash отбрасываются (см. ниже).

Load factor и авторасширение (rehash)

Коэффициент заполнения (load factor) = size / capacity. Чем он выше, тем чаще коллизии и длиннее пробы/цепочки. Когда он превышает порог, таблица расширяется вдвое и все пары перехешируются (rehash) в новый массив — индексы пересчитываются под новый capacity, коллизии раскладываются заново.

def _resize(self, new_capacity: int) -> None:
    old = self._slots
    self._capacity = new_capacity
    self._slots = [_EMPTY] * new_capacity   # концептуально; в коде — цикл while
    self._size = 0
    self._tombstones = 0
    self.collisions = 0
    for slot in old:
        if slot is not _EMPTY and slot is not _DELETED:
            self.put(slot[0], slot[1])      # надгробия не переносим

Пороги разные: для цепочек допустим load factor 0.75 (бакет-список терпит несколько элементов), для открытой адресации порог ниже — 0.5: при заполнении выше половины пробы резко удлиняются, а таблица не должна забиться так, чтобы свободного слота не осталось вовсе. В открытой адресации в пороге учитываются и надгробия ((size + tombstones) / capacity), иначе циклы вставок-удалений забили бы таблицу надгробиями.

Счётчик коллизий

Обе структуры считают коллизии, но определение чуть разное:

• Цепочки — collisions растёт, когда новый ключ попадает в уже непустой бакет.
• Открытая адресация — collisions растёт на каждый шаг пробы, наткнувшийся на слот, занятый другим живым ключом (надгробия и обновление своего же ключа не считаются).

На одних и тех же коллизирующих ключах 1, 9, 17 (capacity 8) это хорошо видно: у цепочек 2 коллизии (оба новых ключа легли в занятый бакет), у пробирования — больше, потому что считается каждый «лишний» шаг мимо занятых слотов.

Сложность — итог

Операция	Метод	Среднее	Худшее
put / get / delete	цепочки	O(1)	O(n)
put / get / delete	открытая адресация	O(1)	O(n)
rehash (_resize)	обе	O(n)	O(n)
keys / items / печать	обе	O(n + capacity)	O(n + capacity)

Среднее O(1) держится, пока хеш-функция распределяет ключи равномерно и load factor под контролем. Деградация до O(n) — это и есть «плохой день» hash map: либо хеш сваливает всё в одну точку, либо таблицу не расширяют и она переполняется коллизиями. Поэтому в реальных hash map (включая dict в Python) так важны качественная хеш-функция и авторасширение.

Меню

menu создаёт три таблицы (цепочки, линейная адресация, двойное хеширование) и в цикле читает выбор:

Пункт	Действие
1	Добавить пару ключ=значение во все три таблицы
2	Получить значение по ключу из каждой таблицы
3	Удалить ключ из каждой таблицы
4	Напечатать все три таблицы (бакеты/слоты, надгробия, load factor)
5	Демонстрация коллизий — вставить 1, 9, 17 и сравнить раскладку
6	Демонстрация авторасширения — вставлять, пока не сработает rehash
0	Выход

Пункт 5 (demo_collisions) — прямой ответ на вопрос «что происходит при коллизии»: одни и те же коллизирующие ключи видно в одном бакете у цепочек, разложенными подряд у линейного пробирования и с разным шагом у двойного хеширования.

---

Где это в проде

Hash map — вероятно, самая используемая структура данных в проде, и под капотом она устроена ровно так, как в лабе:

• Стандартные map — это эти же решения. dict в Python — открытая адресация, map в Go — метод цепочек с бакетами по 8 элементов, HashMap в Java — цепочки с превращением длинного бакета в дерево. Везде есть load factor и rehash при росте; именно поэтому отдельная вставка иногда «дёргается» по латентности (амортизированная O(1): редкий resize — это O(n)).
• Где это работает каждый день. Группировка и агрегация логов по ключу (lab10), дедупликация, in-memory кэши (lab08), GROUP BY и hash join в БД, таблицы маршрутизации. Всё, где нужен доступ «по ключу за O(1)».
• Коллизии — это не только про скорость, но и про безопасность. Хеш-флуд (hash-flooding DoS): атакующий шлёт ключи с одинаковым хешем, все падают в один бакет, операции деградируют до O(n) и сервис ложится. Поэтому Python с версии 3.3 рандомизирует хеш строк (PYTHONHASHSEED), а многие хеш-таблицы перешли на SipHash.
• Мостик к шардированию. Индекс hash(key) % capacity отлично работает внутри одной таблицы, но hash % N по серверам ломается при изменении N — добавили ноду, и почти все ключи «переехали». Как это чинят — в lab11 (consistent hashing).

---

Параллельная реализация на Go

Обе таблицы (цепочки и открытая адресация с линейным/двойным пробированием) реализованы на Go в пакете src/golang/dsa/lab05. Ключи и значения — any (поддержаны типы int и string, как в Python).

Подводный камень переноса: знак %

В Python % всегда возвращает неотрицательный остаток, а в Go — остаток со знаком делимого. Если хеш окажется отрицательным (например, при переполнении), hash % capacity в Go может стать отрицательным и сломать индексацию. Поэтому в Go хеш считается беззнаковым (uint64) — тогда h % capacity гарантированно неотрицателен. Полиномиальный хеш строки (база 31, схема Горнера) идёт по рунам, что соответствует ord() в Python.

PythonGo

def hash_str(key: str) -> int:
    h = 0
    for ch in key:
        h = h * 31 + ord(ch)
    return h

# индекс бакета
def _index(self, key) -> int:
    return hash_key(key) % self._capacity

func HashStr(key string) uint64 {
    var h uint64
    for _, ch := range key { // range по строке даёт руны (как ord)
        h = h*31 + uint64(ch)
    }
    return h
}

// индекс бакета: беззнаковый хеш -> неотрицательный остаток
func (m *HashMapChaining) index(key any) int {
    return int(mustHash(key) % uint64(m.capacity))
}