Хеш-таблицы: хеш-функции, коллизии, открытая адресация

Хеш-таблица — самая используемая нетривиальная структура данных в мире. dict в Python, map в Go, HashMap в Java, Map в JavaScript, индексы в базах, кеши, дедупликация, таблицы символов в компиляторах, маршрутизация в веб-фреймворках. При этом «O(1) в среднем» — не магия и не гарантия: за этой строчкой стоят конкретные компромиссы, которые ломаются, если их не понимать.

Предполагается знакомство с массивами, связными списками и моделью стоимости и амортизацией — здесь всё это сойдётся в одной точке.

Зачем нужна хеш-таблица

Задача: хранить пары «ключ → значение» с быстрыми get, put, delete.

Последняя строчка — идеал: ключи от 0 до 999 → массив на 1000 ячеек и a[key]. Одно обращение к памяти, ноль сравнений. Проблема ровно одна: вселенная ключей огромна. Строки, UUID, 64-битные числа, кортежи — массив на все возможные значения не поместится ни в какую память.

Идея хеш-таблицы: взять функцию, сжимающую вселенную ключей U в диапазон индексов [0, m), и делать прямую адресацию по результату: index = hash(key) mod m. Это работает, потому что нас интересуют не все возможные ключи, а те n штук, что реально лежат в таблице, и n обычно на много порядков меньше |U|.

Цена — коллизии: разные ключи могут дать один индекс. Вся инженерия хеш-таблиц — это (а) как сделать коллизии редкими и (б) что делать, когда они всё-таки случаются.

Хеш-функция: чего мы от неё хотим

Детерминированность. Один ключ в рамках жизни таблицы обязан давать один хеш — иначе вы не найдёте то, что положили. Равномерность. Хеш должен «размазывать» ключи по диапазону близко к равномерному распределению независимо от того, как выглядят реальные данные. А реальные данные почти никогда не случайны: последовательные ID, строки с общим префиксом (user:1001, user:1002), выровненные указатели (младшие 3–4 бита всегда нули), даты. Ключевое свойство здесь — лавинный эффект (avalanche): изменение одного бита входа меняет каждый бит выхода с вероятностью примерно 1/2.

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

Согласованность hash и equals

Это не оптимизация, а инвариант корректности: если a == b, то обязательно hash(a) == hash(b) (обратное неверно и не требуется). Нарушение — источник самых мерзких багов: объект кладётся в таблицу и «исчезает», потому что при поиске считается другой хеш. В Java это контракт equals/hashCode, в Python — __eq__/__hash__ (docs.python.org), в C# — Equals/GetHashCode, в Go — правило «ключ должен быть comparable».

Отсюда второй инвариант: ключ не должен меняться, пока лежит в таблице. Изменили поле, участвующее в хеше, — элемент остался в старом бакете, и достать его нельзя (при этом он занимает память и виден при полном обходе). Именно поэтому в Python ключами могут быть только неизменяемые объекты, а у list и dict — __hash__ = None.

Как строят хеш-функции

Для целых чисел — умножение на нечётную константу и сдвиг (multiply-shift Дицфельбингера):

# Отображает w-битное целое в m-битный индекс.
# a — случайное НЕЧЁТНОЕ число из [1, 2^w): нечётность делает отображение
# биекцией по модулю 2^w, то есть не теряет информацию.
W = 64
MASK = (1 << W) - 1

def multiply_shift(x: int, a: int, m_bits: int) -> int:
    """Возвращает индекс в диапазоне [0, 2^m_bits)."""
    return ((a * x) & MASK) >> (W - m_bits)

Почему берутся старшие биты? При умножении информация «стекает» вверх: старшие биты произведения зависят от всего числа, младшие — только от младших. Наивное x % 2^k берёт ровно младшие биты и потому катастрофически плохо работает на выровненных указателях или на ID, кратных 8. Для строк — итеративное смешивание. Классика (и разумный дефолт для учебного кода) — FNV-1a:

FNV_OFFSET = 0xcbf29ce484222325
FNV_PRIME  = 0x100000001b3

def fnv1a(data: bytes) -> int:
    h = FNV_OFFSET
    for b in data:
        h ^= b                       # сначала XOR — это и есть "1a"
        h = (h * FNV_PRIME) & MASK   # затем умножение: диффузия битов вверх
    return h

FNV прост, но обрабатывает по одному байту и по современным меркам медленный. В проде используют функции, читающие по 8–32 байта за итерацию: xxHash/XXH3 — де-факто стандарт скорости (github.com/Cyan4973/xxHash); wyhash/rapidhash на 128-битном умножении; MurmurHash3 — предшественник, всё ещё живой в Java-экосистеме; SipHash-1-3 — keyed-хеш с доказуемой стойкостью к подбору коллизий, дефолт в Python, Rust, Ruby (Aumasson & Bernstein). Криптографические (SHA-256, BLAKE3) для хеш-таблиц избыточны, но нужны там, где хеш выходит наружу: content-addressable storage, Merkle-деревья.

Комбинировать хеши полей структуры через XOR нельзя: он симметричен (hash(a,b) == hash(b,a)) и обнуляется на равных полях. Используйте смешивание с константой, как boost::hash_combine: seed ^= h + 0x9e3779b97f4a7c15 + (seed << 6) + (seed >> 2), где константа — приближение 2^64/φ с хорошо перемешанными битами.

Универсальное хеширование: гарантии вместо надежд

Семейство функций H называется универсальным, если для случайно выбранной из него h и любых различных x ≠ y выполняется Pr[h(x) = h(y)] ≤ 1/m. Важно, что вероятность берётся по выбору функции, а не по распределению данных. Это меняет всё: злоумышленник не может подобрать «плохой набор ключей» заранее, потому что не знает, какую функцию мы выбрали в рантайме. Классика — семейство Картера–Вегмана: для простого p > |U| и случайных a ∈ [1,p), b ∈ [0,p) берём h(x) = ((a·x + b) mod p) mod m. Отсюда следует главный результат теории: ожидаемая длина цепочки при поиске равна 1 + α, где α = n/m — коэффициент загрузки. То есть O(1) при ограниченном α. Строгий вывод — в CLRS, гл. 11 (mitpress); практический разбор — у Торупа, «High Speed Hashing for Integers and Strings».

Коллизии неизбежны: парадокс дней рождения

По парадоксу дней рождения вероятность хотя бы одной коллизии превышает 50% уже при n ≈ 1.18·√m. Для таблицы на миллион слотов достаточно ~1180 ключей — загрузка при этом 0.1%. Вывод: «сделать хеш достаточно хорошим, чтобы коллизий не было» — не стратегия. Коллизии — нормальный режим работы, и вопрос лишь в том, как таблица их переживает.

Таксономия разрешения коллизий

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

Каждый слот хранит не элемент, а контейнер элементов. Коллизия просто добавляет элемент в список.

class ChainedHashMap:
    """Хеш-таблица методом цепочек. Бакет — питоновский список пар."""

    _MAX_LOAD = 0.75

    def __init__(self, capacity: int = 8) -> None:
        assert capacity & (capacity - 1) == 0, "ёмкость — степень двойки"
        self._buckets: list[list[tuple]] = [[] for _ in range(capacity)]
        self._size = 0

    def _index(self, key) -> int:
        # & (cap-1) вместо % cap: дешевле, но требует степени двойки
        # и ХОРОШЕГО хеша (иначе используются только младшие биты).
        return hash(key) & (len(self._buckets) - 1)

    def put(self, key, value) -> None:
        bucket = self._buckets[self._index(key)]
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)   # перезапись существующего
                return
        bucket.append((key, value))
        self._size += 1
        if self._size > self._MAX_LOAD * len(self._buckets):
            self._resize(len(self._buckets) * 2)

    def get(self, key, default=None):
        for k, v in self._buckets[self._index(key)]:
            if k == key:
                return v
        return default

    def delete(self, key) -> None:
        bucket = self._buckets[self._index(key)]
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket.pop(i)              # удаление тривиально: без tombstone
                self._size -= 1
                return
        raise KeyError(key)

    def _resize(self, new_capacity: int) -> None:
        old = self._buckets
        self._buckets = [[] for _ in range(new_capacity)]
        self._size = 0
        for bucket in old:
            for k, v in bucket:
                self.put(k, v)             # хеш пересчитывается заново

    def __len__(self) -> int:
        return self._size

Анализ. При универсальном хешировании ожидаемая длина цепочки — α = n/m, поиск стоит O(1 + α), то есть константу при α ≤ 0.75. Худший случай (все ключи в один бакет) — O(n). Память: O(n + m).

Достоинства: тривиальное удаление; α может спокойно превышать 1; деградация при плохом хеше плавная, а не обрывистая; легко подменить контейнер бакета деревом. Недостатки: каждый узел — отдельная аллокация (+16–32 байта заголовка и указателей), и, главное, обход цепочки — это зависимые обращения к памяти. Процессор не может их распараллелить: адрес следующего узла известен только после загрузки текущего. Один промах L3 — это ~80–100 нс, тогда как арифметика хеша — единицы наносекунд. Подробнее про локальность — в статье о модели памяти.

Открытая адресация

Никаких внешних контейнеров: все элементы лежат прямо в массиве. Если слот занят, идём по детерминированной последовательности проб h(k,0), h(k,1), ... до первого свободного.

Линейное: h(k,i) = (h(k) + i) mod m. Идеально для кэша — соседние ячейки уже в загруженной кэш-линии. Проблема — первичная кластеризация: занятые слоты слипаются в «пробки», и каждая новая коллизия удлиняет пробку, повышая вероятность попасть в неё снова. По Кнуту (TAOCP т.3, §6.4) среднее число проб при удачном поиске ≈ ½(1 + 1/(1−α)), при неудачном ≈ ½(1 + 1/(1−α)²). При α = 0.9 неудачный поиск — уже ~50 проб.

Квадратичное: h(k,i) = (h(k) + c₁i + c₂i²) mod m. Убирает первичную кластеризацию, оставляет вторичную (ключи с одинаковым h(k) идут по одной траектории). Требует аккуратных констант, иначе проба не обойдёт всю таблицу; при m = 2^k последовательность h + (i² + i)/2 гарантированно посещает все слоты.

Двойное хеширование: h(k,i) = (h₁(k) + i·h₂(k)) mod m, где h₂(k) взаимно проста с m (например, всегда нечётная при m = 2^k). Каждый ключ получает свой «шаг», траектории почти не совпадают — поведение ближе всего к идеальному равномерному хешированию (~1/(1−α) проб при промахе). Платим вторым хешем и потерей локальности.

Алгоритм поиска

Две детали, которые часто забывают. Первая: сначала сравниваем сохранённые хеши, потом ключи — полное сравнение ключей (особенно длинных строк) дорого, а сравнение 64-битных хешей отсекает почти все несовпадения за одну инструкцию, поэтому хеш хранят прямо в слоте, а не пересчитывают. Вторая: пустой слот останавливает поиск, а удалённый — нет. Это и есть корень проблемы удаления.

Удаление и tombstones

Нельзя просто обнулить слот: он может быть частью чужой цепочки проб, и её разрыв «спрячет» элементы, лежащие дальше. Классическое решение — надгробие (tombstone), метка «здесь было удалено, продолжай искать». Слот превращается в конечный автомат:

Опасность: надгробия накапливаются. Таблица, где долго чередуются вставки и удаления, может состоять из живых элементов на 10% и из надгробий на 80% — и работать так, будто заполнена на 90%. Поэтому в счётчик загрузки включают и то и другое, а при переполнении надгробиями делают рехеш той же ёмкости (это чистка, а не рост). Альтернатива — backward-shift deletion: после удаления сдвигаем назад элементы, стоящие не на своём домашнем месте, пока не встретим пустой слот или элемент с нулевым смещением. Работает только там, где цепочка проб непрерывна (линейное пробирование), зато полностью снимает проблему деградации — именно этот подход используется ниже.

Robin Hood hashing

Идея Педро Селиса (диссертация, 1986) изящна: при вставке, если встреченный элемент ближе к своему домашнему слоту, чем текущий вставляемый, — меняем их местами. «Отнимаем у богатых, отдаём бедным». Средняя длина пробы не меняется, но дисперсия резко падает: вместо «большинство находится мгновенно, а некоторые ищутся 50 проб» получаем «почти все находятся за 1–3 пробы». Хвост латентности (p99) становится ровным. Бонус: появляется ранний выход при промахе. Если мы дошли до элемента, чьё смещение меньше нашего текущего, — искомого ключа в таблице нет, инвариант гарантирует, что он был бы уже встречен.

class RobinHoodMap:
    """Открытая адресация + линейное пробирование + Robin Hood + backward-shift.

    Слот: None либо список [hash, key, value]. Ёмкость — всегда степень двойки.
    """

    _MAX_LOAD_NUM, _MAX_LOAD_DEN = 9, 10   # α ≤ 0.9

    def __init__(self, capacity: int = 16) -> None:
        assert capacity & (capacity - 1) == 0
        self._cap = capacity
        self._slots: list[list | None] = [None] * capacity
        self._size = 0

    def _home(self, h: int) -> int:
        return h & (self._cap - 1)

    def _dist(self, h: int, i: int) -> int:
        """Смещение элемента от домашнего слота (probe sequence length)."""
        return (i - self._home(h)) & (self._cap - 1)

    def put(self, key, value) -> None:
        if (self._size + 1) * self._MAX_LOAD_DEN >= self._cap * self._MAX_LOAD_NUM:
            self._resize(self._cap * 2)
        self._insert([hash(key), key, value])

    def _insert(self, entry: list) -> None:
        i = self._home(entry[0])
        dist = 0
        original = True          # пока несём исходный ключ, возможна перезапись
        while True:
            slot = self._slots[i]
            if slot is None:
                self._slots[i] = entry
                self._size += 1
                return
            if original and slot[0] == entry[0] and slot[1] == entry[1]:
                slot[2] = entry[2]
                return
            slot_dist = self._dist(slot[0], i)
            if slot_dist < dist:
                # Встреченный "богаче" — забираем его слот, дальше несём его.
                self._slots[i] = entry
                entry = slot
                dist = slot_dist
                original = False
            i = (i + 1) & (self._cap - 1)
            dist += 1

    def _lookup(self, key) -> int | None:
        h = hash(key)
        i = self._home(h)
        dist = 0
        while True:
            slot = self._slots[i]
            if slot is None:
                return None
            if self._dist(slot[0], i) < dist:
                return None       # ранний выход: мы "беднее" — ключа нет
            if slot[0] == h and slot[1] == key:
                return i
            i = (i + 1) & (self._cap - 1)
            dist += 1

    def get(self, key, default=None):
        i = self._lookup(key)
        return default if i is None else self._slots[i][2]

    def delete(self, key) -> None:
        i = self._lookup(key)
        if i is None:
            raise KeyError(key)
        self._slots[i] = None
        self._size -= 1
        j = (i + 1) & (self._cap - 1)
        while True:
            slot = self._slots[j]
            # Останавливаемся на пустом слоте или на элементе, стоящем дома.
            if slot is None or self._dist(slot[0], j) == 0:
                return
            self._slots[i] = slot
            self._slots[j] = None
            i = j
            j = (j + 1) & (self._cap - 1)

    def _resize(self, new_capacity: int) -> None:
        old = self._slots
        self._cap = new_capacity
        self._slots = [None] * new_capacity
        self._size = 0
        for slot in old:
            if slot is not None:
                self._insert(slot)   # хеш уже посчитан — не пересчитываем

    def __len__(self) -> int:
        return self._size

Сложность: ожидаемая O(1) на все три операции при α ≤ 0.9; память O(m) без единой дополнительной аллокации на элемент. _resize стоит O(m), но амортизируется до O(1) на вставку при удвоении — тот же аргумент, что и для динамического массива (см. амортизацию).

Cuckoo hashing: O(1) в худшем случае для поиска

У ключа есть ровно два возможных места: h₁(k) и h₂(k). Поиск — два обращения к памяти, всегда, детерминированно. Вставка: кладём в первое место; если занято — выселяем жильца и рекурсивно пристраиваем его в альтернативный слот; зациклилась цепочка выселений — полный рехеш с новыми хеш-функциями. Pagh & Rodler (Cuckoo Hashing, 2001) доказывают: при α < 0.5 для двух функций ожидаемая амортизированная вставка — O(1). Три-четыре функции или бакеты по 4 слота поднимают допустимую загрузку до 0.9+. Применяют cuckoo там, где нужен предсказуемый худший случай чтения: сетевое оборудование, таблицы потоков, in-memory индексы. Цена — рвотная вставка возле порога загрузки и необходимость двух независимых хешей.

Коэффициент загрузки и рехеширование

α = n/m — единственный параметр, которым вы реально управляете.

• Рост — умножением, а не сложением. m *= 2 даёт амортизированную O(1); m += 100 — O(n) на вставку в среднем.
• При m = 2^k берите старшие биты хеша или прогоняйте его через финализатор — Java исторически делает h ^ (h >>> 16) именно поэтому. Простое число терпимее к посредственному хешу, но % на простом — это деление (~20–40 циклов против 1 для &). Компромисс — libdivide или степень двойки плюс финализатор.
• Сжатие при удалении опасно: наивная реализация даёт дребезг (вставка → рост → удаление → сжатие → вставка → …). Порог сжатия должен быть сильно ниже порога роста: сжимать при α < 0.25, расти при α > 0.75.
• Знаете размер заранее — преаллоцируйте: make(map[K]V, n), new HashMap<>(n/0.75f + 1), HashMap::with_capacity(n). Это убирает все промежуточные рехеши.

Инкрементальное рехеширование

Классический рехеш — O(n) за один раз, то есть латентный шип: таблица на 10 млн ключей рехешится сотни миллисекунд, и всё это время сервис стоит. Решение — переносить по чуть-чуть при каждой операции, как в dict.c в Redis (исходник): две таблицы и курсор миграции. Инварианты схемы: чтение проверяет обе таблицы, запись идёт только в новую, а фоновый таймер добивает миграцию, даже если запросов нет. Похожая идея — в ConcurrentHashMap и в LSM-деревьях (см. персистентные и конкурентные структуры).

SwissTable: state of the art

Самая влиятельная реализация последнего десятилетия — абсеиловские Swiss Tables (abseil.io, доклад Мэтта Кулукундиса на CppCon 2017). Оттуда её взяли Rust (hashbrown, ставший стандартным HashMap) и Go 1.24 (go.dev/blog/swisstable). Суть — разделение хеша на две части и отдельный массив метаданных: H1 (старшие биты) определяет номер группы из 16 слотов, H2 (младшие 7 бит) кладётся в однобайтовые control bytes, лежащие отдельно и плотно.

Одной SIMD-инструкцией (_mm_cmpeq_epi8 + movemask) сравниваем искомый H2 со всеми 16 control-байтами группы за один такт и получаем битовую маску кандидатов. Настоящий ключ читаем только для них; вероятность ложного совпадения тега — 1/128, поэтому в среднем на поиск приходится меньше одного лишнего сравнения ключей. Что это даёт:

• метаданные всей группы — одна кэш-линия, а «толстые» слоты с ключами трогаются редко;
• та же маска мгновенно отвечает на «есть ли в группе пустой слот» — вставка тоже быстрая;
• удаление ставит DELETED только если в группе нет пустых слотов, иначе слот сразу EMPTY — надгробия почти не копятся.

Идея переносима: даже без SIMD отдельный массив однобайтовых тегов резко сокращает число обращений к записям.

Compact dict в CPython

Другой известный дизайн — «компактный словарь» Раймонда Хеттингера, вошедший в Python 3.6. Данные лежат в плотном массиве вставок, а хеш-таблица хранит лишь индексы в него:

indices:  [None, 1, None, None, 0, None, 2, None]        # разреженный, int8/16/32
entries:  [(h_a,'a',1), (h_b,'b',2), (h_c,'c',3)]        # плотный, порядок вставки

Два следствия. Экономия памяти: разреженная часть хранит маленькие целые, а не 24-байтные записи (~30–50%). И словарь бесплатно стал упорядоченным по вставке, что в 3.7 закрепили как гарантию языка (обсуждение в python-dev, код — Objects/dictobject.c). Разрешение коллизий там не линейное, а рекуррентность j = (5j + 1 + perturb) mod 2^k, где perturb сдвигается вправо на каждой итерации: это подмешивает старшие биты хеша и разрушает кластеры.

HashDoS: когда коллизия становится уязвимостью

В 2003 году Кросби и Уоллах показали (DoS via Algorithmic Complexity Attacks), что детерминированная и публично известная хеш-функция — это вектор атаки. Механика: фреймворк парсит POST-форму или JSON в хеш-таблицу; атакующий заранее считает тысячи ключей с одинаковым хешем и шлёт их одним запросом. Все падают в один бакет, вставка n элементов превращается из O(n) в O(n²), и запрос на пару сотен килобайт съедает секунды CPU. В 2011 году это массово выстрелило (CVE-2011-4815 и родственные) по PHP, Java, Python, Ruby, Node.js. Защиты, применяемые сегодня:

1. Рандомизированный seed на процесс. Python включает PYTHONHASHSEED по умолчанию с 3.3 (PEP 456); Go рандомизирует seed каждой карты — поэтому порядок итерации там намеренно случаен.
2. Keyed-хеш — SipHash для строковых ключей: медленнее xxHash, но подобрать коллизию без знания ключа вычислительно невозможно.
3. Деградация бакета в дерево. Java HashMap при длине цепочки ≥ 8 и ёмкости ≥ 64 перестраивает бакет в красно-чёрное дерево, ограничивая худший случай O(log n) (JDK-8023463). Про такие деревья — в статье о сбалансированных деревьях.
4. Лимит на число параметров запроса — грубо, но эффективно как первая линия.

Вывод: если ключи приходят извне, хеш обязан быть рандомизированным или keyed. Внутри процесса, для доверенных данных, берите самый быстрый некриптографический.

Trade-offs: как выбирать

Последние две строки часто решающие. Стабильность ссылок: в цепочках узел живёт по своему адресу, пока его не удалили, и указатель остаётся валидным после рехеша; в открытой адресации рехеш перемещает всё, и сохранённые указатели с итераторами становятся мусором. Именно поэтому std::unordered_map в C++ обязан по стандарту использовать цепочки — и именно поэтому он медленнее absl::flat_hash_map. Худший случай: для интерактивных сервисов важен не средний, а p99.9.

Типичные ошибки

1. Мутабельный ключ. Положили объект, изменили поле, участвующее в хеше, — элемент потерян навсегда, но продолжает занимать память. Ключ должен быть иммутабелен, или хеш считается только по иммутабельной части.
2. hashCode без equals (или наоборот) — таблица работает «через раз». Используйте record/@dataclass(frozen=True)/data class, где оба метода генерируются согласованно.
3. Хеш «по одному полю» у составного ключа. Ключ (user_id, date), а хеш считается только от user_id — формально корректно, но все записи одного пользователя коллидируют. Тихая деградация до линейного поиска.
4. hash(x) % 2^k с плохим хешем. Берутся только младшие биты. Классика — хеш объекта как адрес в памяти: младшие 3–4 бита всегда нули из-за выравнивания, и вы используете лишь каждый 8–16-й бакет.
5. Полагаться на порядок итерации. В Python 3.7+ он гарантирован (порядок вставки), в большинстве языков — нет. Go специально рандомизирует его, чтобы вы на него не заложились.
6. Мутация таблицы во время итерации. Рехеш посреди обхода — это UB или ConcurrentModificationException. Соберите ключи в список, потом изменяйте.
7. Игнорирование стоимости самого хеша. Хеш длинной строки — O(len). Таблица с ключами по 4 КБ не будет O(1) ни в каком практически полезном смысле. Кешируйте хеш в объекте (как String в Java) или интернируйте ключи.
8. Не тот тип структуры. Нужны запросы диапазона, min/max, порядок, префиксный поиск — хеш-таблица не подходит принципиально: она уничтожает информацию о порядке. Идите к BST или к префиксным деревьям.
9. Хеш-таблица там, где хватило бы вероятностной структуры. Если нужен ответ только «видели ли мы это» и допустимы ложноположительные — Bloom filter займёт в 10–20 раз меньше памяти.
10. Одна общая таблица под глобальным мьютексом. Точка сериализации всего сервиса. Шардируйте (sync.Map, ConcurrentHashMap, DashMap) — детали в статье о конкурентных структурах.

Как это выглядит в проде

Полезно посмотреть, как это устроено в конкретных языках трека — например, map в Go или Dictionary<K,V> в C#. И отдельно стоит помнить: хеширование — базовый приём распределённых систем. Consistent hashing для шардирования (Karger et al., 1997), rendezvous hashing, хеш-партиционирование в Kafka и Spark — та же математика равномерности, только «бакет» здесь — узел кластера.

Мини-итог

• Хеш-таблица = прямая адресация по массиву + функция сжатия вселенной ключей + план на коллизии.
• «O(1) в среднем» держится на трёх опорах: хорошая (лучше — рандомизированная) хеш-функция, ограниченный α, амортизированный рост удвоением. Выньте любую — получите O(n).
• Коллизии неизбежны. Выбор: цепочки (простота, стабильные ссылки, терпимость к плохому хешу) против открытой адресации (локальность, память, скорость).
• Открытая адресация требует решить вопрос удаления: надгробия или backward-shift. Robin Hood при этом выравнивает хвост латентности, SwissTable добавляет SIMD по массиву тегов, compact dict экономит память и даёт порядок вставки.
• Ключи недоверенного происхождения требуют рандомизированного или keyed-хеша — иначе HashDoS.
• Хеш-таблица уничтожает порядок. Нужны порядок, диапазоны, префиксы — берите дерево или trie.

Источники

• CLRS, гл. 11 «Hash Tables» — универсальное хеширование, строгий анализ: mitpress.mit.edu
• Knuth, TAOCP vol. 3, §6.4 «Hashing» — исходный анализ линейного пробирования · Sedgewick & Wayne, Algorithms, гл. 3.4: algs4.cs.princeton.edu
• Thorup, High Speed Hashing for Integers and Strings: arxiv.org/abs/1504.06804
• Pagh & Rodler, Cuckoo Hashing: itu.dk
• Herlihy, Shavit & Tzafrir, Hopscotch Hashing: csail.mit.edu
• Celis, Robin Hood Hashing (диссертация): cs.uwaterloo.ca
• Crosby & Wallach, DoS via Algorithmic Complexity Attacks: usenix.org
• Aumasson & Bernstein, SipHash: aumasson.jp
• Abseil Swiss Tables: abseil.io · Go 1.24: go.dev/blog/swisstable · hashbrown: github.com/rust-lang/hashbrown
• CPython dictobject.c: github.com/python/cpython · xxHash: github.com/Cyan4973/xxHash

Что дальше

Хеш-таблица платит за скорость полной потерей порядка: она не умеет отвечать на «дай все ключи от A до B», «дай минимальный», «дай следующий за X». Как только эти вопросы появляются в требованиях — нужна структура, сохраняющая упорядоченность.

Следующая статья: Деревья и бинарные деревья поиска — как из простой рекурсивной идеи получается структура с O(log n) на поиск, вставку, удаление и на все порядковые запросы сразу, и почему без балансировки она вырождается в связный список.

Общая карта трека — в обзоре.